总结一下int overflow(？)python的列表

Question

让我们考虑一个大整数列表,例如:

def primesfrom2to(n):
    # http://stackoverflow.com/questions/2068372/fastest-way-to-list-all-primes-below-n-in-python/3035188#3035188
    """ Input n>=6, Returns a array of primes, 2 <= p < n """
    sieve = np.ones(n/3 + (n%6==2), dtype=np.bool)
    sieve[0] = False
    for i in xrange(int(n**0.5)/3+1):
        if sieve[i]:
            k=3*i+1|1
            sieve[      ((k*k)/3)      ::2*k] = False
            sieve[(k*k+4*k-2*k*(i&1))/3::2*k] = False
    return np.r_[2,3,((3*np.nonzero(sieve)[0]+1)|1)]

primesfrom2to(2000000)

我想计算其总和,预期结果是142913828922.但如果我这样做:

sum(primesfrom2to(2000000))

我得到1179908154,这显然是错的.问题是我有一个int溢出,但我不明白为什么.让我解释一下.考虑这个测试代码:

a=primesfrom2to(2000000)
b=[float(i) for i in a]
c=[long(i) for i in a]
sumI=0
sumF=0
sumL=0
m=0
for i,j,k in zip(a,b,c):
    m=m+1
    sumI=sumI+i
    sumF=sumF+j
    sumL=sumL+k
    print sumI,sumF,sumL
    if sumI<0:
        print i,m
        break

我发现第一个整数溢出发生在[i = 20444] = 225289

如果我做:

>>> sum(a[:20043])+225289
-2147310677

但如果我这样做:

>>> sum(a[:20043])
2147431330
>>> 2147431330+225289
2147656619L

发生了什么？为什么这么不同的行为？为什么不能自动切换到long类型并给出正确的结果？

Answer 1

查看结果的类型.你正在总结一个numpy数组,它正在使用numpy数据类型,它可能会溢出.当你这样做时sum(a[:20043]),你会得到一个numpy对象(某种类型int32或类似物),当它被添加到另一个数字时会溢出.当您手动输入相同的数字时,您正在创建一个int可以自动升级到的内置Python long.Numpy数组不能像Python内置类型那样自动提升,因为在创建数组时必须修复数组类型(及其内存布局).这使得操作更快,但代价是灵活性.

您可以通过使用不同的数据类型(例如np.int64)来代替它来解决问题np.bool.但是,这取决于你的数字有多大.一个简单的例子:

# Python types ok
>>> 2**62
4611686018427387904L
>>> 2**63
9223372036854775808L

# numpy types overflow
>>> np.int64(2)**62
4611686018427387904
>>> np.int64(2)**63
-9223372036854775808

您的示例在64位Python上正常工作,所以我猜您使用的是32位Python.如果你可以使用64位类型,你将能够超越你找到的限制,但正如我的例子所示,如果你的数字变得非常巨大,你最终也会溢出64位整数.