浮点数就行了。它们设计得体,标准化程度高,在性能和精度之间提供了很好的折衷。他们大部分时间都工作得很好。直到有一天,他们突然不再这么做,没有人知道为什么。
对我来说,那一天到来了,我在Taubin估计器中遇到了一个错误。陶宾平滑需要一个三角形网格,一对称为λ和μ的幻数,花一点时间思考,它会使输入网格平滑。它还可以确保网格不会缩小到一个完美平滑但相当乏味的球体或一个点。
第一个幻数λ介于0和1之间。当它为0 - 时什么都不会发生,当它为1 - 时也不会发生任何好事。应该介于两者之间。没有人真的知道如何选择这个数字,但一个有经验的工程师至少可以做出一个有经验的猜测。
第二个魔术数字管理收缩补偿。这是一个在绝对值上略大于λ的负数。也没有人知道如何挑选,但这一次,即使是一个有经验的猜测也是一个挑战。
这就是你需要估算师的原因。为你挑选μ的东西。我们有一个。它被窃听了。我就是那个修好它的人。
第一天的调查表明,估算者实际上是完全正确的。调查的第二天显示,覆盖该漏洞的测试也是正确的。调查的第三天带来了一个有希望的假设,即整个故事只是一场噩梦,解开谜团所需的一切就是醒来。第四天早上否定了这个假设,让我完全不知所措。
幸运的是,我有一个比我聪明的朋友,他建议把输入弄得模糊一点,然后看看会发生什么。我做到了。然后发生了一些事。这个错误并没有消失,但是μ改变了很多。与输入中的微小变化不成比例。太棒了!
我们可以预期计算会有一些误差。这很好,我们从传感器获得输入数据,而它们首先嵌入了一些错误。我们把成品模型打印出来,而且打印机的精度也很有限,所以一个小小的错误不会让任何人心烦意乱。只要误差很小,一切都是好的。但如果它不是呢?
事实证明,在我的例子中,一个完全正确的算法的计算误差约为1。不是1e-16或1e-5,而是1。只有1。因此,如果你预计μ在某种程度上接近-0.7%,而估计者说它是0.3%,那么它实际上是正确的。在其误差范围内仍是一个正确的估计。
好的,所以造成麻烦的不是计算错误本身,而是意想不到和不可预测的错误。不过,我们能预测到吗?
嗯,我们当然可以。对于这一点,有一个完整的数值误差分析领域,但让我们诚实地说,大多数时候我们使用的是我们的直觉。那么我们的直觉到底有多好呢?
我提议玩个游戏来找出答案。让我们用一个三次方程解算器。这是一个相对复杂的计算,有一个非常简单的方法来验证它的精度。我们将首先选取一些根,然后为这些根生成三次方程。然后,我们将通过计算使立方求解器找到我们的根。每个根的原始值和计算值之间的差异将是我们的可测量误差。这个误差除以原始值就是我们的相对误差。
//查找ax^3+bx^2+cx+d=0std::array<;double,3>;root_for_cubic(std::array<;double,4>;abcd){DOUBLE PI=STD::ATAN(1.)*4;DOUBLE A1=ABCD[1]/ABCD[0];DOUBLE a2=ABCD[2]/ABCD[0];DOUBLE A3=ABCD[3]/ABCD[0];DOUBLE Q=(A1*a1-3.*a2)/9;DOUBLE sq=-2。*std::sqrt(Q);双r=(2.*a1*a1*a1-9.*a1*a2+27.。*a3)/54.0;双z=r*r-q*q*q;std::array<;double,3>;root;if(z<;=0.){Double t=std::acos(r/std::sqrt(q*q*q);root[0]=sq*std::cos(t/3)-a1/3;root[1]=sq*std:cos((t+2.*Pi)/3.)-A1/3;Root[2]=sq*std::cos((t+4.*Pi)/3.)-A1/3.;}Else{root[0]=power(std::sqrt(Z)+std::ABS(R),1./3.);root[0]+=q/root[0];root[0]*=(r<;0.。)?1:-1;ROOTS[0]-=A1/3;ROOTS[1]=std::numeric_limits<;double>;::quiet_NaN();ROOTS[2]=std::numeric_limits<;double>;::quiet_NaN();}返回根;}//查找根的多项式系数a、b、c和d std::Array<;Double,4>;Cubic_For_Root(std::Array<;Double,3>;Xs){return{1.//其中一个应该设置为常量,-(xs[0]+xs[1]+xs[2]),+(xs[0]*xs[1]+xs[1]*xs[2]+xs[2]*xs[0]),-(xs[0]*xs[1]*xs[2])};}。
现在,如果我们选择根为1、2和3,则生成的方程式将为:
嗯,是的。在这个简单的方程式上,没有任何误差。计算工作无懈可击。因此,让我们开始让情况变得更糟吧。
下面的滑块允许您选择对数刻度的间隔。间隔可能从10-12开始,到10-12结束。不可能预测精确的错误,直到一个数字,所以您应该选择一个适当的间隔来覆盖错误*。。当然,您也可以选择整个间隔。这一估计保证是正确的。而且完全没用。←
让我们假设我们有0.001、2、3和3支头发的根。那么,在您看来,立方求解器的最大相对误差属于哪个区间?
它被测量为3.3675e-08,所以估计在e-8和e-7之间将是绰绰有余的。
现在,让我们让我们的根在规模上更加多样化。1E-6、2和3E6怎么样?
它明显大于1。由于它是一个相对误差,这意味着最小根值的误差大于值本身。所以计算现在基本上是有用的。
虽然我们谈论的是一个合成案例,只是为了测试我们的解算器,但它非常接近真实世界的数字。考虑一下你是一个拥有多个亿万富翁的人,你想把你的净资产和几美分放在一个立方方程式中。10&;air sp000&;air sp000&;air sp000和a 0.01在大小上与我们的合成案例的词根具有相同的差异。差别很大,但也不是不可接受的。
误差比最小根值大得多。它甚至比第二个最小的根值还要大。从本质上说,我们得到的输出比我们期望计算的值更多的噪音。
请注意,计算仍然正确。当然,在一定的误差范围内。只有这个差额的规模才会使计算变得毫无用处。
坏的不是错误本身。错误无处不在。每一种测量装置都有其误差,每一台3D打印机和每台铣床都有其最高精度。错误没有问题。
人们以多种方式处理错误。在计量学中,测量值加上绝对误差。你不能说外面的温度是10°,你要说它是10°&&;头发0.5°。这可能看起来是多余的,因为这对于外面的天气来说是一个小错误,但在其他一些上下文中,这个错误可能会变得非常严重。如果你在测量体温,1度的差值就足以区分病人和完全健康的人。在这种情况下,您不能承受整整1度的误差。
如果您写下了此输入错误,则可以通过计算来查看所产生的错误是否仍然可以容忍。要做到这一点,您需要将测量的数字交换为间隔。一个有误差的数字变成一个区间:10°&;air sp±&;air sp0.5°变成[9.5,10.5]°。
因此,通过间隔,您可以适应输入错误。您可以在整个计算过程中拖动它,并查看它如何处理具有其自身错误的其他值。最后,您将在某个间隔内获得计算值,此间隔的大小将指示输出错误。但计算本身的误差又如何呢?
当我们不能将运算结果存储在我们保存操作数的相同类型中,并且我们被迫丢弃一些数据时,就会发生计算错误。让我们假设我们有Python风格的“无限”长度整数。这意味着,如果我们的计算只包括加法、减法和乘法,我们就不会面临任何计算错误。
当然,有了除法,事情就有点不同了。例如,我们不能以整数形式存储16,所以我们必须将其截断为16。在这种情况下,整个小数部分就成了我们的错误。
我们可以用整数对来表示有理数。这将解决划分问题。然而,这类有理数虽然不会累积误差,但会累积数字。它的位数越多,计算速度就越慢。在某种程度上,它可能会变得不切实际地变得缓慢。就像不可控的误差一样,不可控的大小也成了问题。
我们想要一个折衷方案。某些实体可控制地增长错误,但仍以恒定速度运行。例如,我们可以通过合并两个概念来得到它:区间和有理数。
比方说,我们想把一个数字写成十分之一的区间。我们可以最直观地做到这一点,去掉第一个数字之后的所有数字。
就像我们可以对小数做这件事一样,我们可以对任何有理数做这件事。我们可以把它放在由有限个整数组成的一对有理数之间。在这种情况下,每个整数都在[0,1,...,99]范围内。
好吧,这不完全是真的。如果这个数字大于99,那么我们不能真的把它存储在我们的小有理数中,但我们可以通过将0除数分配给它的上界来说它大于99。当然,这只是一个卑鄙的黑客行为,但让我们就这样算了吧。
现在,如果我们想要同时容纳输入误差和计算误差,我们所要做的就是用它的有限有理数来表示输入区间。该区间的有限有理下界和同一区间的有限有理上界。
这个实体 - 是一对有限的有理数界,表示一个实数及其输入误差和表示误差。在实体大小保持不变的情况下,它还会显式增加计算误差。
GitHub上提供了实现示例。请注意,这只是一个概念证明,并不是最好的可能的解决方案,既不是错误最小化,也不是速度方面的最佳解决方案。
在最不合适的时候,计算误差可能会成为一个问题。当错误成为问题时,有理数和区间都是浮点数的众所周知的替代方案。
有理界限是这两种思想的融合产物,允许您以一致的方式管理测量误差和计算误差,而不会对性能造成太大影响。