一个更快更准确的总数
今天的客座博主是Christine Tobler,她是MathWorks的一名开发人员,从事核心数值函数的工作。
数字问题的总和
X = 1 + 1e-16 + 1e-16
x = 1
Y = 1 + (1e-16 + 1e-16)
y = 1.0000
x - y
ans = -2.2204 e-16
所以结果是
总和
命令取决于输入相加的顺序。的
总和
命令从最直接的实现开始:从第一个数字开始,然后逐个相加。我已经实现了
sumOriginal
在这篇文章的底部。
但我们遇到了一个问题:对于单一精度,结果有时是非常错误的:
sumOfOnes = sumOriginal(ones(1e8, 1, 1))“单一”))
sumOfOnes =单身16777216
这是怎么回事?问题是,对于这个数字,舍入错误大于1,正如我们通过调用
每股收益
每股收益(sumOfOnes)
Ans = single 2
因此,再加一个1,然后四舍五入到单个精度返回相同的数字,因为精确的结果向下四舍五入以适应单个精度:
sumOfOnes + 1
Ans =单身
当
总和
用于计算一个大数组的平均值,因为计算的平均值可能比输入数组的所有元素都要小。
计算和的不同方法
现在我们已经在MATLAB中有了一个线程版本的和,我们可以并行地计算一个数组的几个块的和,然后最后把它们加起来。事实证明,这个版本没有同样的问题:
numBlocks = 8;
sumInBlocks(的(1 e8, 1“单一”), numBlocks)
Ans =单个100000000
我们在MATLAB中做了这个改变
总和
即使是非线程的情况,它也解决了这种情况和其他类似的情况。但请记住,尽管这在许多情况下是一个改进,但它不是一个完美的算法,仍然不能总是给出正确的答案。我们可以修改将输入分割成的块的数量,但并非所有的结果都很好:
sumInBlocks(的(1 e8, 1“单一”), 4)
Ans =单个67108864
sumInBlocks(的(1 e8, 1“单一”), 128年)
Ans = single 99999832
让我们看看另一种情况,在这种情况下,我们不只是对数字1求和(仍然每次都对相同的数字求和,因为这样更容易与精确的值进行比较)。我们将在这里查看结果的相对误差,这比我们得到准确的整数更相关:
X = repmat(single(3155), 5419.4, 1); / /计算结果
exactSum = 3155 * 54194;
numBlocks = 2。^ (0:9)
err = 0 (1, length(numBlocks));
为i = 1:长度(numBlocks)
err(i) = abs(sumInBlocks(x, numBlocks(i)) - exactSum) / exactSum;
结束
重对数(numBlocks犯错)
包含(块的数量)
ylabel (' sumInBlocks函数的相对错误')
因此,在选择精确的区块数量时,肯定有一种平衡行为,上面的图仅代表一个数据集。
还有其他可能的算法来计算这个和,我在底部包含了一些链接。一些更复杂的情况将导致计算时间的减慢,这将给没有遇到上述精确度问题的情况带来负担。
我们之所以选择这种“按块计算”的算法,是因为这样做可以使求和变得更快。这是通过循环展开完成的:不是一次添加一个数字,而是同时添加几个数字到单独的运行总数中。我包含了一个实现
sumLoopUnrolled
在下面。
顺便说一下,我并没有明确给出选择
numBlocks
我们做了,因为我们不想让任何人依赖它——毕竟,未来它可能会再次改变。
更改总和
在R2017b中,我们首先发布了这个新版本的
总和
,只适用于单精度数的情况。对于单个数据的大数组,所有的实际问题都被解决了,同时功能甚至变得更快了。然而,我们也从一些对行为改变不满意的人那里得到了一些反馈;虽然新的行为给出了好的或更好的结果,但他们的代码依赖于旧的行为,适应新的行为是痛苦的。
虽然我们不想因为害怕打破依赖而陷入永远无法改进功能的困境,但我们肯定希望更新过程尽可能地轻松。一般来说,我们的目标是运行到运行的再现性:如果一个函数以相同的输入被调用两次,输出将是相同的。然而,如果机器、操作系统或MATLAB版本(以及其他外部环境)发生变化,这也会在舍入误差范围内改变MATLAB返回的确切值。例如,为了提高性能,矩阵乘法的输出通常会发生变化。但随着
总和
因此,更多的人开始依赖它的确切行为,这超出了我们的预期。
所以在做了这个改变之后
总和
对于单个值,我们等待了几个版本来评估客户对更改的反馈。在R2020b中,我们为所有其他数据类型添加了相同的行为。这一次,我们加了
发行通知
它描述了性能的提高,并提到了“兼容性考虑”。虽然我们仍然有一些反馈认为这是一个不方便的改变,但它比第一个情况要少。
关于准确计算和的参考文献
- 尼克•海厄姆"什么是随机四舍五入",来自7/7/2020的博客文章。
- 布兰查德,皮埃尔,尼古拉斯·j·海厄姆,和西奥·玛丽。“一种快速、准确的求和算法。”SIAM科学计算杂志42岁的没有。3 (2020): A1541-A1557。
辅助函数
函数s = sumOriginal (x)
s = 0;
为2 = 1:长度(x)
S = S + x(ii);
结束
结束
函数s = sumInBlocks(x, numBlocks)
len =长度(x);
blockLength = cell (len / numBlocks); / /块长度
s = sumOriginal (x (1: blockLength));
iter = blockLength;
而iter <莱恩
s = s + sumOriginal(x(iter+1:min(iter+blockLength, len)));
iter = iter + blockLength;
结束
结束
函数s = sumLoopUnrolled (x)% #好< DEFNU >
% numBlocks == 4的循环展开示例。为了简单起见,我们假设
x的长度能被4整除。
%
%注意,使用内置的代码与右边的技术是更快的
%编译器标志。在这样的MATLAB代码中并不一定会更快。
s1 = 0;
s2 = 0;
s3 = 0;
s4 = 0;
为2 = 1:4:长度(x)
S1 = S1 + x(ii);
S2 = S2 + x(ii+1);
S3 = S3 + x(ii+2);
x = x + x(ii+3);
结束
S = s1 + s2 + s3 + s4;
结束
版权所有:The MathWorks, Inc.
|
评论
要留下评论,请点击在这里登录到您的MathWorks帐户或创建一个新帐户。