数字

测试 Microsoft Cloud Numerics 的数学函数

Stuart Brorson
Alan Edelman
Ben Moskowitz

 

假设您需要执行数学计算。 例如，假设您需要知道的 34 ° 正弦值。 您将怎么办？ 您可能转向计算器、 计算机或一些其他智能设备。 您的设备上键入"sin(34)"，你得到的答案往往采用 16 十进制数字的精度。 但是你怎么知道你的答案是正确的呢？

我们太习惯于从我们没有人认为有关答案是否正确的电子玩意儿获得数学问题的答案 ！ 几乎每一个人总以为我们的机器给我们正确的答案。 然而，对于软件质量工程师小集，正确性不能想当然 ； 这份工作就是获得正确的答案。 本文介绍了如何测试新的 Microsoft 云数字数学库中的数学函数。

最科学和工程计算使用浮点运算。 IEEE 标准化在 1985 年的浮点数学的基本工作原理。 标准的一个关键特征是它不承认了所有的数字可以表示计算机上。 虽然实数集是无限的不可数名词，IEEE 浮点数的集是一定有限和可数，因为浮点数字的数值表示形式使用固定的数量的位数。 IEEE 浮点数的建设意味着它们也是理性的所以常用号码，如 π 并不完全正确，表示和操作使用它们，如 sin(x)，并不确切。

此外，不同于用整数，IEEE 浮点数字之间的间距是本地统一的但它随对数增加的数量规模本身。 中描述了这对数方面图 1，实数行上显示已运作其中的 IEEE 浮点数的统一块位置。 在图中，由垂直线条表示有效大块的浮点数 （嵌入式实数行中）。 请注意，有效的浮点数之间的距离增加了对数为 x 的规模增加。 两个相邻的浮点数字之间的距离通常称为最精密单位在去年的地方 (汽油) 中，并作为调用内置函数提供 eps(x) 许多常见的数学程序中。 间距的后果是变化的少数几个接近于 0 已添加到相对较大的数字，如 1 时没有影响。

图 1 的示意图的浮点数字网格

除了编纂浮点数字的格式，IEEE 标准提供了有关如何准确地从最基本的数学运算返回必须严格指导。 例如，IEEE 标准指定的从四个算术运算返回 （+、-，＊ 和 /) 必须"最佳四舍五入，"即返回的答案必须最接近 "数学上正确"的结果。 虽然这项规定最初遇到了一些阻力，现在返回 best-rounded 的结果发生在硬件，显示它已成为如何司空见惯。 更有趣的是，IEEE 浮点规范还要求平方根函数返回 best-rounded 的结果。 这是有趣的因为它打开了大门的两个问题："如何准确地可以非理性函数计算使用 IEEE 浮点表示形式？"和"如何您应该测试函数实现的准确性吗？"

准确函数计算

哪些因素可以计算精度的？ 现实是我们应该想遇到不准确之处，舍可以发生在任何算法中的步骤。 这些错误可能复合，尽管有时他们也可能取消。 在实践中，算法设计器必须学会包含数值计算的固有的不准确性和住在一起。

您可以单独计算错误分为两个类别的因素：

1. 用于执行计算的算法的相关因素。 尤其是，这意味着算法的稳定性本身和敏感，因此，一轮关闭错误。 贫困、 不稳定的算法往往会返回不太准确的结果，而一个良好、 稳定的算法将返回更准确的结果。
2. 函数本身固有的性质和其投入的域。 计算使用 （而不是无限） 有限数量的双边投资条约时可实现的任何函数执行准确性的理论极限。 原因是舍就像计算错误的来源和函数本身的行为确定此错误是放大还是减毒作为计算所得的输入和输出。 例如，计算附近奇异函数的值，为零或快速振荡可能不太准确在这些点比计算的函数，在相同的输入域缓慢而异。 当谈到这个内在的身心健康准确性，我们谈到如何"也有条件"的功能是。

因此，测试精度的函数执行涉及验证算法返回准确的结果，理论上可能。 通过在其输入的每个函数的空调设立了理论上的可能性的限制。 要把它放另一种方式，使用浮点数计算结果，引入了两种可能的错误的来源：我们可以通过使用良好，避免的错误稳定算法 （因子 1），和错误，是难以避免，因为它们相关函数的行为在其投入 (因子 2)。

在数值分析的空调概念量化由所谓"条件数，"函数对在其投入变化的敏感性的措施。 根据正在审议 （例如，投入，标量与矩阵等等数） 函数的确切性质，有大量的复杂表达式的条件数。 最简单的情况是可微函数的一个变量，如 1 / x， x 2， sin(x) 或任何其他您可能遇到的高中代数函数。 在这种简单例子中函数的条件数 f 由于：

方程 1

我们会将此作为方程 1 晚。 始终，表示法作为 f'(x) 函数的导数是指种。 大条件数 （Kf >> 1) 指示到相对扰动的高灵敏度，而小的条件数目 （Kf < = 1) 指示的功能是对扰动相对不敏感。 直觉上，你可以看到，如果函数具有奇异性 — — 即，该函数吹起来，如 1 / x 附近 x = 0 — — 衍生品将捕获此效果，并返回大条件数。

例如，请考虑该函数种 = 1/(1-x)。 此函数显然遇难后 （即，变成无限） 在 x = 1。 衍生品是 f'(x) = 1 /(1-x) 2。 这插入公式 1 和消除条款给此函数的条件数：

条件数 Kf (x) 转到无穷大周围 x = 1，意味着涉及此函数计算将敏感的舍入误差等扰动时 x 达 1. 因为种 吹起来的 x → 1，此行为预期。 此外，条件数 Kf (x) 转至 0 时 x 是接近于 0。 这表明使用此函数的计算将无动于衷扰动时 x → 0。 这是直观的有意义，因为种 趋向于 1 时一个常量值 x 比 1 小得多。

测试功能精度

那么什么呢数学功能看起来像一个实际测试？ 假设我们要测试我们的标量函数的实现 y = 种，其中 x 是输入和 y 是返回的输出值。 鉴于一个浮点值，输入 x，测试需要三个项目：

1. 由下测试，该函数计算的值 y计算 = f计算 (x)。
2. "数学上真正的"结果。 假定我们有 oracle 能够告诉我们，确切、 数学上正确的答案。 然后轮到该值最近的浮点值 （因此，它可以表示计算机上）。 调用此值 ytrue = ftrue (x)。
3. 测试的宽容。 对于一些函数，此误差可以是 0，这意味着，ycomputed 是完全相同的数学上真正的价值，ytrue 作为。 例如，浮点规范任务功能 sqrt () 返回在于给出确切的答案最接近的浮点值 (即 best-rounded)。 然而，在一般情况下，我们不能指望所有职能，以其精确值 best-rounded 逼近的回报率。 因此，测试公差必须纳入有关多少错误允许在从返回的信息种。 公差可能取决于该函数的详细信息的说明种，以及输入的确切值 x。

这些成分，与我们的函数实现的准确性被视为可接受 （也就是说，通过我们测试） 如果

|ycomputed - y true | < tol (f ； x)

凡公差取决于两个输入值后 x 和函数 f 本身的行为。

话说，这个方程表示该函数通过了测试，是否返回的值不同于"真实"的值按量小于测试公差 （允许错误）。 请注意，|ycomputed - y true |是绝对错误的计算。

通过创建大量的躺在该函数，通过下测试函数运行这些值的输入域中输入值执行功能测试，在此形式主义和比较函数输出 ybest-rounded （数学上真） 值，计算 ytrue。 应选择输入的值来覆盖该函数的有效的输入域的所有有关部分。

在这一点上，测试人员有两个问题需要回答：函数的"真实"的结果是什么？ 又是一个合理的容差吗？

回答第一个问题，所要做的最简单的事情是要使用"无限精度"数学软件包创建用于测试的输入/输出对。 此程序包不会使用 32 位或 64 位浮点数计算值。 相反，它使用的数值表示形式 — — 或更好，一种符号表示 — — 的一个数字，可运载能力计算任意大的数，通过计算速度而计算的位数。 几个商用数学软件包实现无限精度数学。 此外，许多无限精度数学库可以插入到共同的语言。 在现代的速度使用无限精度数学的能力是最近的创新，并使这种类型的测试方便。 这些资源的任何足以创建用于测试函数的浮点实现所谓的"金值"对。

放在一起 — — 获取测试公差

一旦我们有金色的价值观，我们需要回答的其他问题：什么是合理的测试容忍？ 获取正确的测试公差是关键的组件的测试。 如果公差是不切实际地小，功能从未将传递及其检测、 即使最佳算法用于计算它。 另一方面，如果测试容忍太大，这意味着允许的误差是大于它需要，该函数会通过测试，即使该算法有故障。

先前定义的条件数是确定可接受错误允许在功能测试的关键。 可以重新排列的条件数的表达式来读取：

方程 2

我们会将此作为方程 2 晚。 如果我们确定 ∆x 作为一个浮点数和下一步之间的距离，此表达式告诉我们多少输出的种 将跳随着我们从一个浮点数 x 它的邻居， x + ∆x。 传统上，计算机数字领域花费的 ∆x 函数 eps(x)，任何两个相邻的浮点数字之间的间距。 请注意，因为网格间距为非常数 （见图 1）， eps(x) 是一个函数的 x。 （如前面所提到，一个浮点数和其最近的邻居之间的距离也与有关无铅汽油 — — 由最低有效位代表的规模。）

接下来，我们要求我们的测试中的输出错误 y计算 -y为 true，则将低于一些多跳的。 也就是说，我们问这个问题，在 C 是一个常量：

凭直觉，此表达式捕获以下想法：如果 x 在浮点网格上，在输出中的变化使得一步应不大于方程 2。 准确的函数种将通过仅条件数，从派生并没有更多的金额更改它的输出。 因此，输出计算期间发生的扰动种应小于造成迈出一步浮点网格上的变化。 该常量 C 是"蒙混因素"。很明显，作为 C 的增加，允许的公差与它会增加。 我们因此可以作为允许功能错误解释此常数，在理论上的最低。 在实际测试中， C 采用 1 和 10，我们将解释为允许错误，表示在 ULPs 之间的整数值。

最后，使用条件数的定义，我们可以重新排列的方程公开测试宽容的方式：

|y计算 -ytrue | ≤ C | f'(x) | eps(x) = 公差

这是我们所需的测试 — — 它是必须满足的准确执行的函数的表达式种 进行任何输入 x。 换句话说，这是用来验证标量数学函数的表达式。 请注意此表达式应举行为所有有效的输入值 true x。

解决最后一个问题是，"什么是正确的值的 C ，在测试中使用？"因为我们解释 C 的无铅汽油，允许的错误数为 C 是订单 1 的整数。 我们设置 C 入手初始 C 值 （通常为 10） 和运行测试。 如果测试通过，减少 C 1 和运行测试再测试。 重复此过程，降低 C 值之前，则测试失败。 然后选择的值 C ，最后允许要传递 （但始终保持人体循环来保证合理） 的测试。 这一进程的目标是关闭 （同时仍然允许要通过测试的函数） 通过尽可能多的大门所以你可以放心，尽可能严格地测试函数。 乖函数通常需要 C 之间 1 和 3，但更复杂的函数的值可能需要较大 C 传递的值。 我们发现需要很少的函数实现 C > 10 来传递，当我们找到需要的函数和 C > 10，它往往信号一次优的实现。

从一次软件测试的角度 C 确定函数测试 （和测试通过），我们知道任何后续的测试失败是因为东西在函数中执行已改变 — — 可能恶化的 （例如，回归已经发生）。 当然，权衡算法设计中可能要求它是值得给予一些可宽延时间上 C 如果回归很小 （例如，速度与准确性的权衡比较）。 同样，经过改进的算法，这是值得，看看 C 可以进一步收紧。 在任何情况下，软件测试的一个作业将成为管理测试公差所开发软件的其余部分。

黄金的价值判断和超越

在我们前面讨论过的测试方法，我们使用预计算的输入/输出对散布在整个输入域下测试功能。 我们称这种类型的测试黄金价值测试，意味着无限精度测试 oracle 提供了已知的是高度精确的金色输入/输出对。 对可以存储在一个文件中，并读入测试程序，它在执行时。 作为黑框的方法来测试功能的准确性，这种做法很好工作。 但是，其他类型的函数测试还提供验证函数的行为的重要途径。 其他测试包括：

• 特殊值测试：许多函数返回已知、 精确理论值的某些输入，如 cos(0) = > 1, sin(π) => 0 和 gamma(1/2) = √π，为例子。 在特殊值测试中，已知固定的投入美联储向下测试，函数和函数返回到已知的结果进行比较。 当然，如 π 无理数不会准确地在浮点网格上撒谎，因为浮点相近的对这些数字，必须测试和一个非零值，用于正弦和测试公差 （如前面计算） 用于验证计算结果。
• 标识测试：许多函数服从对某个已知的域，则所有输入的身份。 例如， (x) 偕 ^2 + cos (x) ^2 = = 1 所有输入 x。 另一个是 arcsin(x) = =-i 日志 （我 ＊ x + sqrt (1-x 2))。 标识测试和特殊值测试之间的区别是标识测试是真正对任意输入的而特别值测试只是如此为某一特定的输入值。 因此，标识测试验证函数之间的关系。

你必须小心身份测试。 一方面，一些恒等式是不好的条件。 例如，中间结果可能会增长，即使最终的结果适度规模会很大。 在这种情况下，在计算中的中间步骤期间发生的小的允许错误会导致杂散测试失败。 此外，许多功能 （例如，反三角函数） 是在复杂平面多值。 身份的左边和右边双方返回正确的值，躺在复平面中的不同黎曼工作表时，盲目使用标识测试可能会导致虚假测试失败。 测试人员必须认真起草身份测试，以避免这两个问题。

• 逆测试：这涉及到计算函数组成及其逆和验证结果相同的输入的测试。 例如，对于积极的 x 我们可以测试 log(exp(x)) = x。 你可能认为这是一个特殊的身份测试、 案也的确如此。 但是，因为这么多的函数有逆 — — 和数学一致性要求一个函数组成及其逆返回原始输入 — — 我们使用一个不同的测试类别来验证，其功能和其逆的行为相一致的方式。 同样也适用于标识测试 （如空调或返回躺在黎曼的不同工作表） 的解释适用于逆测试。
• 系列求和测试：几乎所有的先验函数对一些输入域承认一系列扩张。 在系列求和测试中，我们比较到测试中显式总和系列所返回的值根据测试函数所返回的值。 你可能认为作为一种标识测试系列求和。 然而，走进创建良好系列求和测试的考虑因素是类似跨职能 （例如，稳定和趋同标准）。 因此，我们认为这种类型的测试是在概念上不同的标识测试的。
• 分式展开：此外可能对使用分式扩大已知域求的某些功能。 当这种扩大存在时，它可能会聚比一系列笔要快得多。 因此，对于某些函数，系列求和测试可能会替换分式扩张。
• 测试 （也称为基于模型的测试） 构造的值：在构造的值测试中，您创建测试本身内功能简单、 可验证正确执行。 这种类型的测试一定不会适用于标量数学函数。 然而，数学不错包并不限于解析函数集。 例如，考虑如地板、 天花板、 国防部、 向量的串联运算符函数等。 每个函数可能通过编写实现使用电脑的基本语言构造函数的代码进行测试。 例如，地板、 天花板和可能使用强制转换运算符，将浮点值转换为一个整数，然后将转换结果建模功能的各种数字印章回浮点数 （带一些简单的数学执行以模仿正在审议函数的确切行为）。 这种类型的一个好处是测试的模型执行通常微不足道，因此可通过检查核实。
• 错误检测：这些测试确保无效的输入返回清理错误使得程序员能够清楚、 快速地了解问题得到妥善处理。 例如，当在实数，工作 sqrt(x) 应返回有用的错误 （或 NaN) 如果 x < 0. 已知一些输入的错误导致计算机崩溃，如果他们不处理不当，并测试员的工作是要确保这不会发生。

这些类型的测试的好处是正确性的它们提供使用仅本身的数学函数交叉检查。 因为这些方法使用数学自我一致性测试的基础，他们"已知良好"，并不依赖于使用第三方软件的数值计算。

验证方法

欣赏的条件数公差优势的一种方法是检查用于验证其输入域中有奇异的标量数学函数的公差。 例如，常见三角函数 tan 和棉被是奇异在无限的实数线沿线点。 如果固定、 恒公差被用于精度验证，这些函数将失败，他们为输入值接近奇异的测试或测试公差一定会有这么大的测试不会有效。 与条件数的公差，我们可以验证的标量函数的内一小撮 ULPs 函数的整个输入域上。 示图 2 是传递我们发现在资格的职能在 Microsoft 云数字产品分发过程的无铅汽油值的示例。 也就是说，这些都无铅汽油值相应的功能，通过其测试。

图 2 传递无铅汽油的值

功能	输入的域	传递无铅汽油	评论
Atan2	实数	1	两个输入、 四象限反正切值
婴儿床	实数	3
Coth	复杂的数字	3
Cuberoot	实数	2
Ellipe	X 这种真实数字，0 ≤ x ≤ 1	4	椭圆积分 E
Ellipk	X 这种真实数字，0 ≤ x ≤ 1	6	椭圆积分 K
Expm1	实数	3	-1 Exp(x)
灰度系数	实数	3
Log	实数	3
Log	复杂的数字	3
Log1p	实数	1	Log(1+x)
Log1p	复杂的数字	1	Log(1+x)
防扩散安全倡议	实数	6	防扩散安全倡议功能 — — 衍生的伽玛函数
Sqrt	实数	0	IEEE 规范要求此以"最佳四舍五入"
Tan	实数	1
双曲正切	实数	4
双曲正切	复杂的数字	4

从示例中得出结论， 图 2 是特殊的功能实现使用精确到内少量的 ULPs 的算法。 最糟糕的情况提出了在图 2 有错误少于 6 ULPs，它对应于 log10(2^6) = 1.8 错误号的顺序最低位数字中的小数位数。 为双精度浮点，这对应于 1.3323e 相对误差-015。

先进的测试

审查，严格的测试方法已成功应用在 Microsoft 云数值型数学包中使用的算法的验证。 使用该函数的条件数从派生的测试公差使我们能够识别并正确不正确的函数的实现中，甚至当错误发生只在最后几位数字的函数的返回。 固定的测试公差不能提供也不会引起杂散失败 （例如，近函数奇异) 的严格测试。 我们测试所涉及的大部分使用的预计算使用无限精度数学软件包的金色值输入/输出值，然后存储在测试时读取的文件。 除了使用金值，我们也在使用各种不同的数学身份验证我们的函数的行为我们函数实现上执行交叉检查。

我们相信微软云计算数字的用户可以使用其数学与统计库函数的数组并有信心使用先进的软件测试的做法职能已被审核彻底。

有关详细信息，我们鼓励您阅读的浮点数学，"什么每计算机科学家应该知道有关浮点算术，"这是可用在大卫 · 戈德堡的经典描述 bit.ly/vBhP9m 和其他网站。

斯图尔特 Brorson 是微软在马萨诸塞州剑桥的 Microsoft 书呆子中心 他加入微软公司收购交互式超级，开发软件允许用户运行数学时和矩阵运算在并行超级计算机上。为了好玩，Brorson 喜欢黑客电子和玩周围波士顿爱尔兰提琴。

Ben Moskowitz 是专门从事测试基于数学的项目在 Microsoft 微软。他已经贡献的云数字和规划求解基金会、 优化包和 2011 年荣获 Visual Studio 灯塔奖的平台版本。 下班，他花时间和他的妻子，照顾他们居住在城市的山羊。

艾伦 · 德曼 教授数学和计算机科学与人工智能实验室在麻省剑桥麻省理工学院的一名成员 爱德曼教授赢得了众多奖项数值分析、 并行计算和随机矩阵理论的工作。他是交互式的超级计算的创始人、 是朱莉娅项目的创办人之一、 学会了很多从 Velvel 格汉和大量参加了浮点数学问题数值数学联合会.

衷心感谢以下技术专家对本文的审阅： Paul Ringseth