为什么我计算 woodall 数的程序在 n >47 后产生错误结果？

Question

对于此函数，最多计算 n = 64

的 woodall 数

woodall 的算法是 W_n = n ⋅ 2ⁿ - 1

for (int n = 1; n <= 64; ++n)
{
    a[n - 1] = (n * (exp2(n))) - 1;
}

但是在 n 大于 47 之后，结果是错误的，因为它似乎忘记了 - 1 n * (exp2(n)) 的结果。

如果我 cout 通过

得到值，那么输出是这样的

std::cout << i << ":\t" << std::setprecision(32) << a[i - 1] << std::endl;

...之前是正确的

n
45:     1583296743997439
46:     3236962232172543
47:     6614661952700415
48:     13510798882111488
49:     27584547717644288
50:     56294995342131200

...之后不正确

对于 a[] 是一个无符号长整型

如果我将 - 1 操作分离到它自己的 for 循环中，该函数会产生正确的结果：

for (int n = 1; n <= 64; ++n)
{
    a[n - 1] = (n * (exp2(n)));
}


for (int n = 1; n <= 64; ++n)
{
    a[n - 1] = a[n - 1] - 1;
}

Answer 1

exp2(n) returns一个double.

在 IEEE754（浮点类型的一个非常常见的规范）中，它只会给你精确的整数，直到 2 的 52 次方。之后你得到近似值。

由于隐式类型转换，整个表达式 n * (exp2(n))) - 1 是 double，因此您在第 52 个 Woodall 数字之前观察到问题。 由于计算上的怪癖，导致问题的是 -1。碰巧另一个项是 2 的幂的适当倍数，这使得它可以表示为 double 而不会损失精度！ 这就是你的第二个代码段工作但你的第一个代码段不工作的原因。

在 64 位系统上 int，您将达到 2 的 63 次方的整数限制（和未定义的行为）。

你最好的选择是纯粹用 unsigned 算法生成伍德尔数（注意 << 和 2 的幂之间的关系），甚至可能对连续的伍德尔数使用递归关系。

Answer 2

double 有精度限制。不过，它确实使用二进制基数来工作，这意味着大多数以二进制零位结尾的数字都可以准确表示，exp2(int).

的倍数就是这种情况。例如

50 * exp2(50)就是56294995342131200，十六进制就是C8000000000000。即使位数超出了double的精度限制，也能准确表示。但是，如果我尝试从该数字中求和或减去 1，则情况不再如此。

double 不能表示 56294995342131199 也不能表示 56294995342131201，所以当您尝试这样做时，它只会四舍五入到 56294995342131200.

这就是您的 - 1 位失败的原因，当您尝试执行此操作时，它仍在作为 double 进行操作。在执行此减法之前，您必须将表达式的其余部分转换为 int64_t。

但另一种解决方案是根本不使用 exp2()。由于我们使用的是整数，您可以简单地使用按位运算来执行相同的任务。 (1 << n) 将产生与 exp2() 相同的结果，除了它现在是整数格式，因为你只是将它乘以 n，你实际上可以只做 (n << n)。

当然，这样还是会断线。 int64_t只能容纳2⁶³-1和uint64_t2⁶⁴-1这样大的数，应该当迭代器到达 n = 57.

附近时中断

为什么我计算 woodall 数的程序在 n >47 后产生错误结果？

Why is my program for calculating the woodall numbers producing wrong results after n >47?

c++

math

icc