python求和(dict.值（））给出错误的结果？

Question

尊敬的烟囱换热器

我在试图计算python字典中的值之和时遇到了一个奇怪的结果。如果我的字典超过了一定的大小，下面的函数：sum(dict.values())似乎给出了错误的结果。结果似乎突然变得毫无原因地否定了。我在Windows7上使用Python2.7。（我为我的编码风格提前道歉）。在

请注意，我在处理https://projecteuler.net/problem=72时遇到了这种行为，但我不是在寻求帮助来获得答案，我只是被内置函数的行为所迷惑。（我也很抱歉在公共论坛上发布了部分解决方案，如果你不想得到任何提示，请现在就把目光移开）。在

该程序的目标在ProjectEuler链接（如上）中进行了说明，但我将尝试简要解释我的代码：

第一个函数使用一个erathenes筛来生成一个素数列表，使用一个修改过的筛子在指定范围内生成{composite_number:[prime_factor_list]}的字典。在

第二个函数尝试计算n/d形式的分数，其中n<；d和d<；=1000000。这个问题说明我应该只计算约化的真分数，所以这个函数的大部分是关于剔除可约分数的。我的策略是循环使用1和d-1之间的每个分子，并丢弃不合适的分母。对于素数，这很简单，对于非素数，我接近于一个有效的解决方案，但仍多次丢弃一些值。在这篇文章中，重要的细节是我统计计数的方式：

最初我使用了一个简单的计数器（将count初始化为0，然后根据需要递增），但是决定改为使用字典。令我惊讶的是，这两种方法得到的结果不同，但只有当上限（d）超过一定的大小时。我更深入地探索，设法找出了计数出现分歧的确切时刻。底部附近的if 88000 < i < 88055:行标识dict值总和开始与简单计数不同的点。对于i=88032以下的值，该值是相同的，但是当i=88033时，这些值会发生显著的差异：

from collections import defaultdict

def primeset(limit):
    pr = [0]*(limit+1)
    for i in range(2,limit+1):
        j = i
        i += j
        while i <= limit:
            pr[i] = 1
            i += j
    primes = [k for k in range(2,limit+1) if pr[k] == 0]
    composites = defaultdict(list)
    for p in primes:
        q = p
        p += q
        while p <= limit:
            composites[p].append(q)
            p += q
    return primes, composites


def method2(limit):
    primes, composites = primeset(limit)
    prf = {}
    count = 0
    count += limit-1
    count += (limit-2)/2
    prf[1] = limit-1
    prf[2] = (limit-2)/2    
    for i in primes:
        if i != 2:
            tally = limit-i-(limit/i)+1
            count += tally
            prf[i] = tally
    for i in composites:
        tally = limit-i
        for item in composites[i]:
            tally -= (limit/item-i/item)
        count += tally
        prf[i] = tally
        if 88000 < i < 88055:
            print i, count, tally, sum(prf.values())
    return count, prf

result, index = method2(88547)

print result,sum(index.values())

我想我做了一些非常愚蠢的事情，但我觉得我不得不把它放在那里，以防真的有什么不对劲。在

谨致问候

Answer 1

您遇到了整数溢出的问题，在Python中不应该发生这种情况。你有一个32位的机器，所以最大的正整数是（2^31-1）。一旦计算量超过这个值，Python应该自动切换到使用long进行计算，而long不受它所能支持的数字大小的限制。我只有64位机器，但是同样的事情也适用，除了最大整数是（2^63-1）。你可以从外壳上看出你有一个很长的，因为L是印在数字后面的。下面是我的示例：

>>> 2**62 - 1 + 2**62  # This is max int
9223372036854775807
>>> 2**63  # This is a long
9223372036854775808L
>>> num = 2**62 - 1 + 2**62
>>> num
9223372036854775807
>>> num+1
9223372036854775808L
>>> d = {1:2**62,2:-1,3:2**62}
>>> sum(d.values())
9223372036854775807
>>> d = {1:2**62,2:-1,3:2**62,4:1}
>>> sum(d.values())
9223372036854775808L

在我的例子中，在64位机器上的Linux上使用Python2.7，这一切都如预期的那样工作。在

现在我用Spyder运行同样的东西，但得到了错误的答案：

^{pr2}$

当我做普通加法时，它是正确的，但是字典里的这个和给出了错误的答案。这不是字典特有的，只是求和函数。清单也是一样：

>>> list = [2**62, -1, 2**62, 1]
>>> sum(list)
-9223372036854775808

因此，该问题与Spyder中的sum（）函数无关，并且在32位和64位计算机上都会发生。在

真正的答案是Spyder会自动导入numpy。Numpy有自己版本的sum函数。它的描述如下：“使用整数类型时，算术是模块化的，溢出时不会引发错误。”您使用的是sum版本，它导致了问题。如果您不想使用该总和，可以将以下内容放在文件顶部：

from __builtin__ import sum

这将导致使用sum的内置版本，您将得到正确的答案。在

为了弄清楚这笔钱不是从我以为的地方来的，我可以用以下方法：

>>> import inspect
>>> inspect.getmodule(sum)
<module 'numpy.core.fromnumeric' from '/usr/lib/python2.7/dist-packages/nump/core/fromnumeric.pyc'>