6

n番目のフィボナッチ数を見つけるために私が書いたコードは次のとおりです。

unsigned long long fib(int n)
{
    unsigned long long u = 1, v = 1, t;

    for(int i=2; i<=n; i++)
    {
        t = u + v;
        u = v;
        v = t;
    }

    return v;
}

アルゴリズムは非常に高速に実行されますが、n>93 になると出力が狂い始めます。unsigned long long の 64 ビットサイズが原因だと思います/知っています。私はC ++を初めて使用しますが、これを回避してfib(9999)のような答えを得る方法はありますか?

ありがとう

4

2 に答える 2

14

http://gmplib.org/

GMP は、符号付き整数、有理数、および浮動小数点数を操作する任意精度演算用の無料ライブラリです。GMP が実行されるマシンで使用可能なメモリによって暗示されるものを除いて、精度に実質的な制限はありません。GMP には豊富な機能セットがあり、機能には通常のインターフェイスがあります。

GMP の主な対象アプリケーションは、暗号アプリケーションと研究、インターネット セキュリティ アプリケーション、代数システム、計算代数研究などです。

于 2010-06-26T23:50:24.917 に答える
4

bigint ライブラリを使用します。Web にはたくさんあります (例:こことここ)。

編集: 独自のロールを作成することは、予想よりもはるかに困難です。算数は難しい部分ではありません。結果を10進数形式で出力しています。

于 2010-06-26T23:52:00.990 に答える