ACM通信gydF4y2Ba

实践gydF4y2Ba

小数据计算:正确的计算器算术gydF4y2Ba

Hans-J。波姆gydF4y2Ba
ACM通讯，2017年8月，第60卷第8期，44-49页gydF4y2Ba
10.1145 / 2911981gydF4y2Ba
评论gydF4y2Ba

计算机通常使用浮点运算来进行数值计算，gydF4y2Ba^{一个gydF4y2Ba}通常表示IEEE 754标准指定的数字。数字表示为gydF4y2BaM × bgydF4y2BaegydF4y2Ba,在那里gydF4y2BabgydF4y2Ba是基础,gydF4y2Ba米gydF4y2Ba是固定位长的长度分数(gydF4y2Ba尾数gydF4y2Ba)，左边有一个隐含的“小数点”，以及gydF4y2BaegydF4y2Ba是指数。为常规IEEE“双精度”浮点数的基础gydF4y2BabgydF4y2Ba是2，还有尾数gydF4y2Ba米gydF4y2Ba长度为53位(大约16位十进制数字)。对于硬件计算器，我们可以使用gydF4y2BabgydF4y2Ba= 10，带有12位尾数。gydF4y2Ba^bgydF4y2Ba

从大规模的科学计算问题到袖珍计算器，浮点表示法被广泛使用。它们在计算速度和足够的准确性之间提供了一个伟大的折中方案，通常可以提供有意义的结果。一个53位的尾数通常可以在最终结果中提供10到15个十进制数字的精度，而现代处理器通常可以在每个周期中执行多个浮点操作。gydF4y2Ba

但是传统的浮点运算仍然是一种折衷。结果可以很快计算出来，但通常只有精确到有意义的程度。通常从舍入到53位的精度损失是不明显的，因为我们通常是在测量的物理量上进行计算，这些物理量一开始就不太准确，而且通常设计良好的算法不会使这些传入的测量误差过于复杂。但这些“通常”的限定词都不能去掉，而且算法并不总是设计得很好。gydF4y2Ba

我们大多数人都熟悉浮点编程的一些危险。例如，我们可能已经观察到，这个循环gydF4y2Ba

对于(x = 0.0;X != 10.0;X += 0.1){…｝gydF4y2Ba

通常无法终止。但我们愿意处理这些问题，并编写更仔细的代码，以获得高性能的数值计算。gydF4y2Ba

但有时性能，至少在传统意义上，真的不重要。计算器通常以操作较少的表达式为目标，可能是这类应用程序的典型示例。当计算器实际上是一个运行在拥有4个2GHz处理器核心的智能手机上的应用程序时，情况尤其如此。在这种环境中，用户也不太可能考虑如何制定算法来优化浮点精度属性。gydF4y2Ba

即使对计算器来说，浮点数的危险也会延伸到最后一位少了几个数字。例如，如果我们尝试计算:gydF4y2Ba

这显然等于0，在任何标准计算器上，结果只是一个错误消息。问题是1 + 10gydF4y2Ba^16gydF4y2Ba四舍五入为1。减去1，得到0而不是10gydF4y2Ba^16gydF4y2Ba．这通常被称为“灾难性抵消”:我们减去两个几乎相等的数字，有效地放大输入错误，产生的结果只有很少或没有有意义的数字。然后减去10gydF4y2Ba^16gydF4y2Ba，结果是一个负数，现在可以准确地表示。取负数的平方根会产生错误。有关这些方面的更有趣和更微妙的示例，请参阅题为“固定精度失败”的侧栏。gydF4y2Ba

在其他情况下，我们确实得到了正确的答案，但前16位数字未能揭示结果的有趣属性。我们可能想知道一个有理数的小数展开式什么时候会重复。或者我们可能想知道拉马努金常数(gydF4y2BaegydF4y2Ba^163gydF4y2Ba)的整数。这些往往是“数学”问题而不是“物理”问题。但我们怀疑，学校使用计算器的很大一部分就是为了这个目的。gydF4y2Ba

回到顶部gydF4y2Ba

超越机器浮点数的空间gydF4y2Ba

也许传统计算器算术最严重的问题是，它训练我们甚至不去尝试某些问题。gydF4y2Ba

每节微积分课都教我们用有限差分近似导数。我们通常可以非常精确地，用(f(x + h) f(x))/h来近似f'(x)，只要h足够小，例如，由于e的导数gydF4y2Ba^xgydF4y2Ba是egydF4y2Ba^xgydF4y2Ba，我们应该期望(egydF4y2Ba^{1 + hgydF4y2Ba}egydF4y2Ba^1gydF4y2Ba)/h计算为gydF4y2BaegydF4y2Ba，如果我们使用gydF4y2BahgydF4y2Ba= 10gydF4y2Ba^{1000gydF4y2Ba}．gydF4y2Ba

当然，这在普通计算器上是行不通的。的表情gydF4y2BaegydF4y2Ba1 + hgydF4y2Ba而且gydF4y2BaegydF4y2Ba1gydF4y2Ba同意比计算精度更多的数字，分子计算为零，产生0而不是e的“导数”。gydF4y2Ba

事实上，有限精度的概念似乎已经深入人心，以至于很少有人会尝试这样的事情。当我们提出这个建议时，人们通常会感到惊讶。gydF4y2Ba

对于使用机器浮点的数值微分，在h的选择上有一个微妙的权衡，这可能远远超出了一个试图在计算器上检查公式的高中生的专业知识。然而，这样的计算没有理由不成立，即使是gydF4y2BahgydF4y2Ba= 10gydF4y2Ba^{1000gydF4y2Ba}．标题为“计算器上的导数”的边栏进一步介绍了这个示例。gydF4y2Ba

回到顶部gydF4y2Ba

我们的出发点gydF4y2Ba

Android开源项目一直包含一个相对简单的计算器应用程序。这是Pixel手机和许多其他android设备上的默认计算器。历史上，其他一些第三方Android计算器也扩展了相同的源代码库。这个计算器被设计得尽可能简单，主要针对非技术用户而不是工程师。它一直提供“科学计算器”功能，包括三角函数等。但重点是简单的用例和符合Android用户界面指南。gydF4y2Ba

在Android 6.0棉花糖之前的版本中，计算器内部使用“arity”表达式求值库。gydF4y2Ba^cgydF4y2Ba计算器使用这个库计算传统的中缀表达式。常规语法经过了适度的扩展，允许省略后面的括号和其他一些快捷方式。实际计算使用双精度机器浮点数。gydF4y2Ba

计算器将结果四舍五入为比底层算术提供的16位数更小的十进制数字。这降低了一个具有有限十进制展开的数字(如12.34)，但具有无限二进制展开的数字将显示为12.399999999的概率。但是，在没有删除足够多的数字和删除太多数字之间存在着不可避免的紧张关系。后者要么会为中间结果引入额外的错误，要么会迫使计算器显示与内部表示显著不同的结果。两者都可能带来令人不快的意外。在网上搜索“Android计算器bug”，可以看到一些结果。这些抱怨的性质也证实，大多数用户不愿意容忍数值分析师所期望的那种浮点问题。gydF4y2Ba

回到顶部gydF4y2Ba

计算器给出的准确答案gydF4y2Ba

我们的目标是将Android计算器中的算术评估引擎替换为不受浮点舍入错误影响的引擎。我们希望至少确保所显示的最终答案不会在最终显示的数字中相差一个或多个。gydF4y2Ba

这可以用“构造实算术”来实现。gydF4y2Ba^{dgydF4y2Ba，gydF4y2BaegydF4y2Ba}每个子表达式不是为每个中间结果计算固定数量的数字，而是按照确保最终结果足够精确所需的精度计算。gydF4y2Ba

假设我们想要计算+，计算器显示有10个数字。我们将两者都计算为11位，将它们相加，并将结果四舍五入为10位。和精确到11分之一以内gydF4y2Ba^thgydF4y2Ba数字，四舍五入在11中最多增加5个错误gydF4y2Ba^thgydF4y2Ba数字，结果保证精确到小于1的10gydF4y2Ba^thgydF4y2BaDigit，这是我们的目标。gydF4y2Ba

其他操作的实现稍微复杂一些。乘到小数点后10位可能涉及到将一个参数求值为5位。如果它是0，我们将另一个参数求值为5位数。如果两者都是0,0是一个可接受的答案。一旦我们有了一个非零参数，我们就可以对另一个参数所需的数字数量得到一个合理的严格限制，并使用它来重新计算初始非零参数到正确的精度。gydF4y2Ba

一些函数，比如平方根，可以很容易地用牛顿迭代求出所需的精度。通用超越函数可以用泰勒级数求值，注意求足够多的项，以保证有足够的精度，以保证最后一位的误差界限。gydF4y2Ba

已经探讨了构造实数的一些详细表示。gydF4y2Ba^{fgydF4y2Ba，gydF4y2BaggydF4y2Ba，gydF4y2BahgydF4y2Ba，gydF4y2Ba我gydF4y2Ba}

我们从一个现有的Java库开始，gydF4y2Ba^jgydF4y2Ba根据需要稍微加强。该库用类CR Java对象表示实数gydF4y2Ba从()gydF4y2Ba方法。呼叫gydF4y2Ba从(gydF4y2BangydF4y2Ba）gydF4y2Ba,在那里gydF4y2BangydF4y2Ba通常是负的，产生精确到2的近似值gydF4y2Ba^ngydF4y2Ba．返回的实际结果隐式地乘以2gydF4y2Ba^ngydF4y2Ba，这样它就可以表示为整数。例如，如果gydF4y2Ba三个gydF4y2Ba那么，3是建设性的真实表示吗gydF4y2Ba三。从(3)gydF4y2Ba会得到24吗，也就是3乘以2gydF4y2Ba^3.gydF4y2Ba或8。这将是唯一可接受的答案，因为结果总是有一个< 1的误差。gydF4y2Ba

的子类的一个实例，用于在此表示中添加两个数字gydF4y2BaCRgydF4y2Ba，实现如下:gydF4y2Ba

类add_CR扩展CR {gydF4y2Ba
CR op1;CR op2;gydF4y2Ba
.．.gydF4y2Ba
保护BigIntegergydF4y2Ba
Appr (int p) {gydF4y2Ba
返回规模(op1.appr (p 2)。gydF4y2Ba
add (op2.appr (p 2)), 2);gydF4y2Ba
｝gydF4y2Ba
｝gydF4y2Ba

在这里gydF4y2Ba规模(…， n)gydF4y2Ba乘以2gydF4y2Ba^ngydF4y2Ba并舍入到最接近的整数，确保最终舍入误差为½。参数被计算为两个额外的位，确保每个位的误差为<¼。gydF4y2Ba

真正的实现缓存了最高精度的预先求值，因此重新计算表达式的精度位数基本上是免费的。gydF4y2Ba

基于构造实数算法的计算器并不新鲜。我们用作基础的库包含一个基本的Java applet计算器。WolframAlpha似乎也使用了类似的技术。gydF4y2Ba^kgydF4y2Ba然而，我们有两个额外的，之前未被满足的目标:gydF4y2Ba

1. 计算器作为一种通用工具，例如平衡支票簿和计算技巧，以及对数学不熟悉的用户保持可用性是至关重要的。我们希望行为普遍优于机器浮点数。gydF4y2Ba
2. 我们希望以一种直观的方式将具有非终止十进制表示的数字表示为无限对象，而不是显式地输入结果精度。gydF4y2Ba

我们现在集中讨论这些问题。gydF4y2Ba

回到顶部gydF4y2Ba

可滚动结果gydF4y2Ba

由于我们必须能够产生任意精度的答案，我们还可以让用户指定她想要的精度，并使用该精度来驱动评估。在我们的计算器中，用户通过滚动结果来指定所请求的精度，这与主要基于触摸的用户界面所期望的一样。gydF4y2Ba^lgydF4y2Ba

为了尽可能地保持无限结果的错觉，我们在后台预先计算出更高精度的结果，只要我们显示出计算出的大约数字。每次计算的额外数字的数量比我们到目前为止计算的数字要多一点，所以用户滚动得越远，我们重新计算的块就越大，计算的代价就越高。这通常成功地隐藏了几千位的滚动延迟，即使用户使用“投掷”手势来快速滚动。gydF4y2Ba^米gydF4y2Ba

指示位置。gydF4y2Ba我们希望用户能够一眼看出当前显示的是结果的哪一部分。gydF4y2Ba

传统计算器通过使用科学计数法来解决显示非常大或非常小的数字这一模糊类似的问题。我们对初始显示使用相同的方法。gydF4y2Ba^ngydF4y2Ba如果用户输入“1÷3×1020”，计算乘以10的20次方gydF4y2Ba^thgydF4y2Bapower，则结果可能显示为3.3333333333E19。在这个版本的科学记数法中，小数点总是显示在最有效数字的右边。gydF4y2Ba

一旦小数点被滚动出显示器，这种科学计数法就没有帮助了;它告诉我们小数点相对于最高位的位置，但是最高位已经看不见了。我们通过切换到一种不同的科学记数法来解决这个问题，在这种记数法中，我们将显示的数字解释为一个整数，右边有一个隐含的小数点。我们假设可以显示33333333333E9或33333333333乘以10，而不是显示3.3333333333E19gydF4y2Ba^9gydF4y2Ba．事实上，我们只在正常的科学计数法小数点不可见时才使用这种格式。如果我们将上面的结果向左滚动两位数字，我们实际上会看到……33333333333E7。这告诉我们显示的结果非常接近于以33333333333乘以10结尾的整数gydF4y2Ba^7gydF4y2Ba．这两种形式的科学记数法很容易通过是否有小数点和开头的省略号来区分。gydF4y2Ba

舍入与滚动。gydF4y2Ba通常，我们期望计算器尝试舍入到最接近的可显示结果。如果实际计算结果是0.6666666666666667，并且我们只能显示10位数字，那么我们期望的结果显示为，例如0.666666667，而不是0.666666666。对我们来说，这有一个缺点，当我们向左滚动结果以查看更多数字时，右边的“7”将变成“6”。那就有点不幸了。如果实际结果正好是0.99999999999，并且我们一次只能显示10个字符，那么我们将看到初始显示为1.00000000。当我们滚动查看更多数字时，我们会依次看到……000000E-6，那么……000000E-7，以此类推，直到……00000E-10，但突然，99999E-11。如果我们向后滚动，屏幕将再次显示0。我们认为这会非常混乱，因此尝试截断到零，而不是四舍五入。gydF4y2Ba

当我们滚动时，之前显示的数字仍然有可能发生变化。但我们计算的数字总是比实际需要的多，所以这是极不可能的。gydF4y2Ba

由于我们的目标是在最后显示的数字中严格小于1的错误，因此我们永远不会，例如，将恰好为2的答案显示为1.9999999999。这就涉及到最后一处的误差正好是1，这对我们来说太大了。gydF4y2Ba

---

也许传统计算器算术最严重的问题是，它训练我们甚至不去尝试某些问题。gydF4y2Ba

---

事实证明，只有一种情况下显示会在9秒和0之间切换:真实结果中一个长但有限的9秒序列(大于20个)最初可以显示为以0结尾的略大的数字。随着我们滚动，0变成了9。当我们立即回滚时，数字仍然显示为9s，因为计算器缓存了最著名的结果(尽管目前没有重启)。gydF4y2Ba

我们防止在滚动过程中9变成0。如果我们生成一个以9s结尾的结果，我们的错误界限意味着真实结果严格小于(绝对值)我们通过增加最后一个显示数字得到的值(以0结尾)。因此，我们永远不会被迫返回生成0，并明确地确保我们总是继续生成9，并且9永远不会变成0。gydF4y2Ba

回到顶部gydF4y2Ba

应对不确定性gydF4y2Ba

计算器本质上是将数字表示为计算近似值的程序。这种表示有很多不错的属性，比如永远不会显示不正确的结果。它有一个固有的弱点:两个数的精确相等从根本上是不可判定的。我们可以计算这两个数的越来越多的数字，如果它们在最后一个计算的数字中相差超过1，我们就知道它们不相等。但如果这两个数字实际上是相同的，这个过程就会永远持续下去。gydF4y2Ba

这仍然改进了浮点算术——相等性很容易确定，但是关于由浮点值近似的真正数学实数的相等性告诉我们的就更少了。gydF4y2Ba

这种平等的不可预测性确实产生了一些有趣的问题。如果我们把一个数除以gydF4y2BaxgydF4y2Ba，计算器就会计算出越来越多的数字gydF4y2BaxgydF4y2Ba直到它找到一些非0的1。如果gydF4y2BaxgydF4y2Ba实际上是零，这个过程将永远持续下去。gydF4y2Ba

我们使用两种互补的技术来处理这个问题:gydF4y2Ba

1. 我们总是在后台运行数值计算，在那里它们不会干扰用户交互，以防它们花费很长时间。如果它们确实花了很长时间，我们会暂停它们，并通知用户计算已经中止。这种情况不太可能是偶然发生的，除非用户输入了定义不清的数学表达式，比如除零。gydF4y2Ba
2. 正如我们将看到的，在许多情况下，我们使用一个额外的数字表示，它允许我们确定一个数字恰好为零。尽管这很容易处理大多数情况，但并非万无一失。如果用户输入“1÷0”，我们立即检测到除零。如果用户输入“1÷(gydF4y2Ba^2gydF4y2Ba我们暂停了。gydF4y2Ba

回到顶部gydF4y2Ba

眼睛看不见的零gydF4y2Ba

我们计算器的原型，就像数学家一样，将所有计算结果视为无限个对象，有无限个数字可以滚动。如果实际的计算结果恰好是2 1，结果最初显示为1.00000000，用户可以根据自己的需要继续滚动该结果右侧的数千个零。尽管在数学上是合理的，但事实证明，这是不受欢迎的，有几个很好的原因，第一个原因可能比其他原因更严重:gydF4y2Ba

1. 如果我们计算$1.23 + $7.89，结果将显示为9.1200000000或类似的结果，这是出乎意料和令人困惑的。gydF4y2Ba
2. 许多用户认为1+2的结果是一个有限的数字，并且发现能够在右边滚动大量的零是令人困惑的。gydF4y2Ba
3. 由于计算器无法判断一个数字是否将被滚动，因此它不能将任何结果视为短到允许使用更大的字体。gydF4y2Ba

这些问题在很大程度上是通过将表达式求值为不仅是一个构造实数，而且是表示为(分子，分母)对的有理数来解决的。如果计算涉及无理数，或者有理数表示太大，则后者不可用。gydF4y2Ba

这允许我们判断一个结果是否具有有限十进制表示，如果是，小数点右侧有多少位数字。我们只看最低的分数。如果分母有一个质因数而不是2或5，小数展开显然是无穷大的;无论乘多少次10都不能把这个分数变成整数。否则分母可以因式分解为2gydF4y2Ba^ngydF4y2Ba5gydF4y2Ba^米gydF4y2Ba小数点右边的非零位数是gydF4y2Bamax (gydF4y2Bam, ngydF4y2Ba）gydF4y2Ba．gydF4y2Ba

如果扩展是有限的，我们就会阻止滚动超过那个点。我们还防止滚动小数点左侧的大量尾随零。这通常会给我们留下一个短的不可滚动的结果，为此我们可以使用更大的字体。与浮点情况不同的是，这种短而大的字体结果总是精确的，并且永远不能归因于一个仅仅接近于短十进制表示的数字。gydF4y2Ba

然而，在另一个方向上，这是容易出错的。例如，我们不计算1÷(的有理数表示。gydF4y2Ba^2gydF4y2Ba÷)，因此仍然可以滚动该结果的任意多个0。gydF4y2Ba

结果的底层分数表示也用于直接检测，例如，除零，这大大降低了普通用户看到超时的可能性。gydF4y2Ba

回到顶部gydF4y2Ba

回顾gydF4y2Ba

这里描述的计算器可以通过谷歌Play Store获得，也是Android 6.0 Marshmal-low及更高版本发布的默认计算器。gydF4y2Ba

对计算器的最初评估喜欢一些不相关的UI和功能更改，但没有注意到算术上的更改。gydF4y2Ba^ogydF4y2Ba我们显然成功地保证了准确性不影响正常使用。gydF4y2Ba

计算器现在在合理表示可用时向用户公开它。事实证明，这本身就是一个有用的功能，尽管它是出于其他考虑。gydF4y2Ba

反馈相当积极。但它连同我们自己的经验也提出了一些改进建议:gydF4y2Ba

• 滚动搜索结果产生的兴趣远远超过了更细微的精度改进。后者似乎只是因为没有错误报告而被承认。因此，另一种类型的性能实际上很重要:用户在滚动30,000个数字时确实注意到迟缓。然后我们切换到性能更好的高斯-勒让德算法。gydF4y2Ba
• 计算器表达式的语义比我们意识到的更加微妙和有争议。50+10%等于50.1还是55?如果是后者，50×5%是什么?如果2是一个有效的表达式，那么2呢?gydF4y2Ba
• 我们的计算器的最新版本明确地跟踪有理数倍数和其他一些常见的无理数常数。这让我们可以计算一个有理数的结果gydF4y2Ba罪gydF4y2Ba(/6)在弧度模式，因为我们已经做了gydF4y2Ba罪gydF4y2Ba(30°)。gydF4y2Ba

回到顶部gydF4y2Ba

致谢gydF4y2Ba

计算器的UI设计和实现当然依赖于其他几个人的贡献，最著名的是Justin Klaassen。gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

回到顶部gydF4y2Ba

数字图书馆是由计算机协会出版的。版权所有©2017 ACM, Inc.gydF4y2Ba