python - 为什么 NumPy 在对零填充数组求和时会给出不同的结果？

Question

我计算了一个数组和同一数组的零填充版本的总和:

import numpy as np

np.random.seed(3635250408)

n0, n1 = int(2**16.9), 2**17

xx = np.random.randn(n0)
yy = np.zeros(n1)
yy[:n0] = xx

sx, sy = np.sum(xx), np.sum(yy)

print(f"sx = {sx}, sy = {sy}") # -> sx = -508.33773983674155, sy = -508.3377398367416
print(f"sy - sx:", sy - sx)  # -> sy - sx: -5.68434188608e-14
print("np.ptp(yy[:n0] - xx) =", np.ptp(yy[:n0] - xx)) # -> 0 

为什么我没有得到相同的结果？

有趣的是，我能够在 Mathematica 中显示类似的效果。我正在使用 Python 3.6(支持 MKL 的 Anaconda 5.0)和 Numpy 1.13.3。也许，这可能是 MKL 问题？

更新:@rich-l 和@jkim 注意到舍入问题可能是原因。我不相信，因为添加零不应该改变 float (问题出现在调查那个大小的数据集时 - 偏差明显更大)。

Answer 1

浮点运算是 not associative :

In [129]: ((0.1+0.2)+0.3) == (0.1+(0.2+0.3))
Out[129]: False

所以添加项的顺序会影响结果。 numpy.sum通常使用 pairwise summation .当数组的长度为 less than 8 时，它恢复为简单求和(从左到右)或 when summing over a strided axis .

由于成对求和递归地将序列分成两组，因此添加零填充会影响序列被划分的中点，因此更改值的添加顺序。而且由于浮点算术不是关联的，零填充会影响结果。

例如，考虑

import numpy as np

np.random.seed(3635250408)
n0, n1 = 6, 8
xx = np.random.randn(n0)
# array([ 1.8545852 , -0.30387171, -0.57164897, -0.40679684, -0.8569989 ,
#         0.32546545])

yy = np.zeros(n1)
yy[:n0] = xx
# array([ 1.8545852 , -0.30387171, -0.57164897, -0.40679684, -0.8569989 ,
#         0.32546545,  0.        ,  0.        ])

xx.sum()和 yy.sum()不是相同的值:

In [138]: xx.sum()
Out[138]: 0.040734223419930771

In [139]: yy.sum()
Out[139]: 0.040734223419930826

In [148]: xx.sum() == yy.sum()
Out[148]: False

自 len(xx) < 8 , xx 中的值从左到右求和:

In [151]: xx.sum() == (((((xx[0]+xx[1])+xx[2])+xx[3])+xx[4])+xx[5])
Out[151]: True

自 len(yy) >= 8 , pairwise summation用于计算 yy.sum() :

In [147]: yy.sum() == (yy[0]+yy[1]+yy[2]+yy[3])+(yy[4]+yy[5]+yy[6]+yy[7])
Out[147]: True

---

相关的 NumPy 开发者讨论:

• numpy.sum is not stable

• implementation of pairwise summation

• implementing a numerically stable sum

numpy.sum不使用 Kahan也不是 Shewchuk 求和(由 math.fsum 使用)。我相信这些算法会在您提出的补零问题下产生稳定的结果，但我还不够专业，无法确定。