最大のウッダル数を計算するこの関数の場合 n = 64
そしてwoodallためのアルゴリズムはWであり、N = N⋅2 N - 1
for (int n = 1; n <= 64; ++n)
{
a[n - 1] = (n * (exp2(n))) - 1;
}
しかしn
、47を超えると、結果が間違ってしまい- 1
、の結果を忘れているように見えn * (exp2(n))
ます。
これが、icout
が経由する値の場合の出力です。
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
...後は正しくありません
fora[]
はunsignedlongintです
- 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;
}
exp2(n)
を返しますdouble
。
IEEE754(浮動小数点型の非常に一般的な仕様)では、2の52乗までの正確な整数のみが得られます。その後、近似値が得られます。
式全体が暗黙的な型変換によるものn * (exp2(n))) - 1
であるdouble
ため、52番目のウッダル数の前に問題が発生します。計算上の癖により、問題を引き起こすのは-1です。もう一方の項が2の累乗の適切な倍数であるため、精度を損なうことなく倍数として表すことができます。これが、2番目のスニペットが機能する理由ですが、最初のスニペットは機能しません。
64ビットのシステムではint
、2の63乗で整数の制限(および未定義の動作)に達します。
あなたの最善の策は、おそらく連続するウッダル数の漸化式を使用して、純粋にunsigned
算術でウッダル数を生成することです(との関係<<
と2の累乗に注意してください)。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加