c++ - 为什么我的 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))的结果.

以下是如果 i 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)返回 double .

在 IEEE754(浮点类型的一种非常常见的规范)中，它只能为您提供 2 的 52 次方以内的精确整数。此后您将获得近似值。

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

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

您最好的选择是纯粹在 unsigned 中生成伍德尔数。算术(注意 << 和 2 的幂之间的关系)，甚至可能对连续的 Woodall 数使用递归关系。