13

私はプログラミング言語に取り組んでおり、今日、階乗関数(再帰)をコンパイルできるポイントを得ましたが、整数の最大サイズのために、取得できる最大はfactorial(12)です。任意の最大サイズの整数を処理するためのいくつかの手法は何ですか? この言語は現在、コードを C++ に変換することで機能します。

4

7 に答える 7

18

32 ビット以上が必要な場合は、64 ビット整数 (long long) の使用を検討するか、GNU MPなどの任意精度の数学ライブラリを使用または作成します。

于 2008-11-21T21:41:18.900 に答える
5

独自の任意精度ライブラリをロールする場合は、Knuth の半数値アルゴリズム、彼の最高傑作の第 2 巻を参照してください。

于 2008-11-21T23:03:11.137 に答える
3

これを言語に組み込む場合 (おそらく学習目的で)、おそらく小さな BCD ライブラリを作成すると思います。BCD 番号をバイト配列内に格納するだけです。

実際、今日の巨大なストレージ機能を使用すると、各バイトが数字 (0 ～ 9) を保持するバイト配列を使用することができます。次に、独自のルーチンを作成して、バイト配列の加算、減算、乗算、除算を行います。

(除算は難しいものですが、どこかでコードを見つけることができると思います。)

Java のような疑似コードをいくつか提供できますが、現時点では C++ をゼロから作成することはできません。

class BigAssNumber {
    private byte[] value;

    // This constructor can handle numbers where overflows have occurred.
    public BigAssNumber(byte[] value) {
        this.value=normalize(value);
    }

    // Adds two numbers and returns the sum.  Originals not changed.
    public BigAssNumber add(BigAssNumber other) {
        // This needs to be a byte by byte copy in newly allocated space, not pointer copy!
        byte[] dest = value.length > other.length ? value : other.value;         

        // Just add each pair of numbers, like in a pencil and paper addition problem.
        for(int i=0; i<min(value.length, other.value.length); i++)
            dest[i]=value[i]+other.value[i];

        // constructor will fix overflows.
        return new BigAssNumber(dest);
    }

    // Fix things that might have overflowed  0,17,22 will turn into 1,9,2        
    private byte[] normalize(byte [] value) {
        if (most significant digit of value is not zero)
            extend the byte array by a few zero bytes in the front (MSB) position.

        // Simple cheap adjust.  Could lose inner loop easily if It mattered.
        for(int i=0;i<value.length;i++)
            while(value[i] > 9) {
                value[i] -=10;
                value[i+1] +=1;
            }
        }
    }
}

追加のオーバーフローを一般的な方法で処理するために、1 バイトに多くの余裕があるという事実を利用します。減算にも使用でき、乗算にも役立ちます。

于 2008-11-21T22:46:14.180 に答える
1

C++ でそれを行う簡単な方法はありません。GNU Multiprecisionなどの外部ライブラリを使用するか、Python などの任意の大きな整数をネイティブにサポートする別の言語を使用する必要があります。

于 2008-11-21T21:42:31.597 に答える
0

独自の言語を実装していて、任意の長さの数値をサポートしたい場合は、キャリー/ボローの概念を持つターゲット言語を使用します。しかし、深刻なパフォーマンスへの影響 (例外など) を伴わずにこれを実装する HLL は存在しないため、アセンブリで確実に実装します。おそらく単一の命令 (x86 の JC のように) でオーバーフローをチェックし、それを処理します (x86 の ADC のように)。これは、任意の精度を実装する言語にとって許容できる妥協点です。次に、オーバーロードを利用してより洗練された出力を得ることができれば、通常の演算子の代わりにアセンブリで記述されたいくつかの関数を使用します。しかし、生成された C++ がターゲット言語として維持可能 (または維持されることを意味する) であるとは思いません。

または、必要以上のベルとホイッスルを備えたライブラリを使用して、すべての番号に使用してください。

ハイブリッド アプローチとして、独自のミニ ライブラリをローリングする代わりに、アセンブリのオーバーフローを検出し、オーバーフローの場合はライブラリ関数を呼び出します。

于 2008-11-21T23:46:04.653 に答える
0

他の投稿者は、これを行うライブラリへのリンクを提供していますが、これを言語に組み込もうとしているようです。私の最初の考えは、本当にそれをする必要があるのですか? 他の人が示唆しているように、ほとんどの言語はアドオンライブラリを使用します。

コンパイラを作成していて、この機能が必要であると仮定すると、アセンブリ内の任意の大きな値に対して整数算術関数を実装できます。

たとえば、単純な (ただし最適ではない) 実装では、数値は 2 進化 10 進数として表されます。算術関数は、鉛筆と紙で計算する場合と同じアルゴリズムを使用できます。

また、これらの大きな整数には特殊なデータ型を使用することを検討してください。そうすれば、「通常の」整数は標準の 32 ビット演算を使用できます。

于 2008-11-21T21:53:35.253 に答える
0

私の好ましいアプローチは、32ビットintに現在のint型を使用することです（または、同じアルゴリズムを引き続き使用できる限り、内部でlong longなどに変更することもできます）。オーバーフローすると、自分で作成したものか、外部ライブラリを使用しているかにかかわらず、bignumとして保存するように変更してください。ただし、算術演算ごとにオーバーフローをチェックする必要があるように感じます。算術演算のオーバーヘッドは約2倍です。どうすればそれを解決できますか？

于 2008-11-21T22:11:21.413 に答える