numpy 大整数失败

Question

我最近在处理一些项目欧拉问题

最小倍数

问题 5

2520是能被1到10的每个数整除无余数的最小数

能被 1 到 20 的所有数整除的最小正数是多少？

我写的代码很好用

def factor_finder(n, j=2):

    factor_list = []

    if n == 2:
        return [2]
    elif n == 3:
        return [3]
    else:
        while n >= j * 2:
            while n % j == 0:
                n = int(n / j)
                factor_list.append(j)
            j += 1

    if n > 1:
        factor_list.append(n)

    return factor_list



def smallest_multiples(n):

    from functools import reduce

    factor_list = []
    final_list = []

    for i in range(2, n + 1):
        factor_list += factor_finder(i)
    # print(factor_list)

    for i in set(factor_list):
        l1 = []
        l2 = []
        for j in factor_list:
            if j == i:
                l1.append(j)
            else:
                if len(l1) > len(l2):
                    l2 = l1
                    l1 = []
                else:
                    l1 = []
        # print(l2)
        final_list += l2
    # print(final_list)

    return (
        np.array(final_list).cumprod()[-1],
        reduce((lambda x, y: x * y), final_list),
    )

结果是：

%时间

smallest_multiples(1000)

CPU 次：用户 5 微秒，系统：0 纳秒，总计：5 微秒挂墙时间：32.4 微秒

(-4008056434385126912, 7128865274665093053166384155714272920668358861885893040452001991154324087581111499476444151913871586911717817019575256512980264067621009251465871004305131072686268143200196609974862745937188343705015434452523739745298963145674982128236956232823794011068809262317708861979540791247754558049326475737829923352751796735248042463638051137034331214781746850878453485678021888075373249921995672056932029099390891687487672697950931603520000)

我的问题是为什么 numpy.cumprod() 无法得到正确的数字。我认为 numpy 是非常重要的数字工具。有人可以给我一些想法吗？

Answer 1

数值分析不是数论。正确性不是唯一的目标，但必须与效率进行权衡。任意精度数（如大整数）速度很慢，因此 numpy 默认使用固定长度的整数。当它们变得太大时，它们就会溢出。你可以指示 numpy 使用任意精度的整数，但你会失去它的大部分速度：

np.arange(1, 100).prod() # fast but wrong
# 0
np.arange(1, 100, dtype=object).prod() # slow but correct
# 933262154439441526816992388562667004907159682643816214685929638952175999932299156089414639761565182862536979208272237582511852109168640000000000000000000000

Answer 2

问题是数字达到了一个大小，这意味着它不再可以用 Python 中的整数表示。如果你看 here，你会看到 int 的最大大小约为 19 位（即 63 位 + 符号位的 2^63），然后进入溢出。 Numpy 基于 C，它使用固定精度来实现更快的计算，但它受到 64 位整数的限制并且会溢出。 numpy 中的一些函数甚至通过转换为浮点数来进行可以容纳更多数字的计算来防止这种情况。

如果你告诉 numpy 使用 "object" 作为你的数据类型，会有显着的时间损失，但它会让你使用你在 Python 中习惯的任意精度。对于您的代码，它看起来像：

return (
    np.cumprod(final_list, dtype="object")[-1],
    reduce((lambda x, y: x * y), final_list),
)

More about overflow in numpy.

numpy 大整数失败

numpy large integer failed

python

numpy

biginteger

最小倍数

问题 5