使用 ECLiPSe Prolog 的 lib(ic)
我从 David H. Bailey, "Resolving numerical anomalies in scientific computation." 偶然发现了以下问题Unum book 提到了我。事实上,这只是其中的一部分。首先,让我用 (is)/2
来表述这个方程。 。 此外,请注意,所有这些十进制数字都以基数 2 float (包含 IEEE)精确表示:
ECLiPSe Constraint Logic Programming System [kernel]
...
Version 6.2development #21 (x86_64_linux), Wed May 27 20:58 2015
[eclipse 1]: lib(ic).
...
Yes (0.36s cpu)
[eclipse 2]: X= -1, Y = 2, Null is 0.80143857*X+1.65707065*Y-2.51270273.
X = -1
Y = 2
Null = 0.0
Yes (0.00s cpu)
所以这真正 0.0(根本没有舍入)。但现在与 $=
相同代替is
:
[eclipse 3]: X= -1, Y = 2, Null $= 0.80143857*X+1.65707065*Y-2.51270273.
X = -1
Y = 2
Null = 2.2204460492503131e-16__2.2204460492503131e-16
Yes (0.00s cpu)
此区间不包含 0.0。我知道区间算术通常有点过于近似,如下所示:
[eclipse 4]: 1 $= sqrt(1).
Delayed goals:
0 $= -1.1102230246251565e-16__2.2204460492503131e-16
Yes (0.00s cpu)
但至少等式成立!然而,在第一种情况下,不再包括零。显然我还没有明白一些事情。我也尝试过eval/1
但没有效果。
[eclipse 5]: X= -1, Y = 2, Null $= eval(0.80143857*X+1.65707065*Y-2.51270273).
X = -1
Y = 2
Null = 2.2204460492503131e-16__2.2204460492503131e-16
Yes (0.00s cpu)
Null
的原因是什么?不包括0.0
?
(在 @jschimpf 令人惊讶的答案后编辑)
这是本书第 187 页的引文,我将其解释为数字被精确表示(现在划过)。
Use a {3,5}, environment, the one that can simulate IEEE single precision. The input values are exactly representable. ...
{-1, 2}
...
That did the job, computing the exact answer with fewer than half the bits used by ...
否则第 184 页的陈述成立:
...
0.80143857 x + 1.65707065 y = 2.51270273
这些方程看起来确实很简单。假设精确的十进制输入,该
block 引用>
系统可以通过x = -1和y = 2精确求解。这是通过 SICStus 重新检查的
library(clpq)
:| ?- {X= -1,Y=2, A = 80143857/100000000, B = 165707065/100000000, C = 251270273/100000000, Null = A*X+B*Y-C}. X = -1, Y = 2, A = 80143857/100000000, B = 33141413/20000000, C = 251270273/100000000, Null = 0 ? yes
所以 -1, 2 是精确解。
<小时/>精确的表述
这是一个在输入系数中不存在舍入问题的重新表述,但解仍然只是 -∞...+∞。因此基本正确,但不可用。
[eclipse 2]: A = 25510582, B = 52746197, U = 79981812, C = 80143857, D = 165707065, V = 251270273, A*X+B*Y$=U,C*X+D*Y$=V. A = 25510582 B = 52746197 U = 79981812 C = 80143857 D = 165707065 V = 251270273 X = X{-1.0Inf .. 1.0Inf} Y = Y{-1.0Inf .. 1.0Inf} Delayed goals: 52746197 * Y{-1.0Inf .. 1.0Inf} + 25510582 * X{-1.0Inf .. 1.0Inf} $= 79981812 80143857 * X{-1.0Inf .. 1.0Inf} + 165707065 * Y{-1.0Inf .. 1.0Inf} $= 251270273 Yes (0.00s cpu)
最佳答案
这里有几个问题共同造成了困惑:
除了声明之外,示例中的三个常量 不有双 float 的精确表示。
最初的示例不涉及舍入,这是不正确的。
第一个示例中看似正确的结果实际上是由于 幸运的是舍入错误。其他计算顺序给出不同的结果。
准确的结果,给定最接近的双浮点表示 常数确实不为零,而是 2.2204460492503131e-16。
区间运算只有在输入时才能给出准确的结果 是准确的,但这里的情况并非如此。常数必须是 扩大到包含所需小数的区间。
像 lib(ic) 提供的关系算术本质上就是这样做的 不保证特定的评估顺序。由于这个原因,四舍五入 错误可能与功能评估期间遇到的错误不同。 然而,对于给定的常数,结果是准确的。
下面将进行更详细的介绍。正如我将演示一些 使用 ECLiPSe 查询点,先简单介绍一下语法:
两个 float 用双下划线分隔,例如
0.99__1.01
表示具有下限和上限的区间常数,在本例中 1附近的数字。两个整数之间用一个下划线分隔,例如
3_4
表示具有分子和分母的有理常数,在此 情况四分之三。
为了演示第 (1) 点,请将浮点表示形式转换为 0.80143857 变为有理数。这给出了精确的分数 3609358445212343/4503599627370496,很接近,但不相同, 到预期的小数 80143857/100000000。 float 因此,表示方式不准确:
?- F is rational(0.80143857), F =\= 80143857_100000000.
F = 3609358445212343_4503599627370496
Yes (0.00s cpu)
下面显示了结果如何取决于评估顺序 (上面第 3 点;请注意,我已通过以下方式简化了原始示例 去掉不相关的乘法):
?- Null is -0.80143857 + 3.3141413 - 2.51270273.
Null = 0.0
Yes (0.00s cpu)
?- Null is -2.51270273 + 3.3141413 - 0.80143857.
Null = 2.2204460492503131e-16
Yes (0.00s cpu)
顺序依赖性证明存在舍入误差(第 2 点)。对于熟悉浮点运算的人来说,实际上很容易看出
添加 -0.80143857 + 3.3141413
时,0.80143857
的两位精度
在调整操作数的指数时迷失方向。事实上它是
这个幸运的舍入错误给了OP看似正确的结果!
实际上,第二个结果相对于 常量的浮点表示。我们可以证明这一点 通过使用精确的有理算术重复计算:
?- Null is rational(-0.80143857) + rational(3.3141413) - rational(2.51270273).
Null = 1_4503599627370496
Yes (0.00s cpu)
?- Null is rational(-2.51270273) + rational(3.3141413) - rational(0.80143857).
Null = 1_4503599627370496
Yes (0.00s cpu)
由于加法是通过精确的有理数完成的,所以现在的结果是
与顺序无关,并且因为 1_4503599627370496 =:= 2.2204460492503131e-16
,
这证实了上面获得的非零浮点结果(第 4 点)。
区间算术在这里有何帮助?它的工作原理是通过计算
包围真值的间隔,这样结果总是
输入准确。所以至关重要的是
输入区间(ECLiPSe 术语中的有界实数)包含
期望的真实值。这些可以通过编写它们来获得
显式向下,例如0.80143856__0.80143858
;
通过从精确的数字进行转换,例如使用有理数
真实(80143857_100000000)
;或者通过指示解析器自动
将所有 float 扩大到有界实数区间,如下所示:
?- set_flag(syntax_option, read_floats_as_breals).
Yes (0.00s cpu)
?- Null is -0.80143857 + 3.3141413 - 2.51270273.
Null = -8.8817841970012523e-16__1.3322676295501878e-15
Yes (0.00s cpu)
?- Null is -2.51270273 + 3.3141413 - 0.80143857.
Null = -7.7715611723760958e-16__1.2212453270876722e-15
Yes (0.00s cpu)
现在两个结果都包含零,并且很明显 结果的精度取决于评估顺序。
关于prolog - lib(ic) 的精确解,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/31058929/