7

2 つの任意の長さの整数を正確に乗算するアルゴリズムはありますか? 私が使用している言語は、64 ビットの符号なし整数の長さに制限されています (最大整数サイズは 18446744073709551615)。現実的には、各数値を分割し、符号なし 64 ビット整数を使用して何らかの方法で処理し、それらを文字列にまとめることができるようにすることでこれを実行できるようにしたいと考えています (これにより、乗算結果の問題が解決されます)。保管所）。

何か案は？

4

7 に答える 7

13

ほとんどの言語には、これを行う関数またはライブラリがあり、通常は Bignum ライブラリと呼ばれます ( GMPが適しています)。

自分でやりたい場合は、紙の上で長い掛け算をするのと同じ方法で行います。これを行うには、数値を含む文字列を操作するか、ビット演算を使用してバイナリで実行します。

例：

  45
 x67
 ---
 315
+270
----
 585

またはバイナリで：

   101
  x101
  ----
   101
  000
+101
------
 11001

編集:バイナリで実行した後、基数 10 の数値を含む文字列の代わりにビット演算を使用してコーディングする方がはるかに簡単 (そしてもちろん高速) になることに気付きました。バイナリ乗算の例を編集してパターンを示しました。下の数値の 1 ビットごとに、上の数値を追加し、1 ビットの位置を左にビットシフトして変数に入れます。最後に、その変数には製品が含まれます。

積を格納するには、2 つの 64 ビット数が必要で、そのうちの 1 つが積の最初の 64 ビットで、もう 1 つが積の 2 番目の 64 ビットであると想像してください。2 番目の数値のビット 63 から最初の数値のビット 0 までの加算を実行するコードを作成する必要があります。

于 2008-10-11T00:00:13.460 に答える
4

GMPのような既存のbignumライブラリを使用できない場合は、コンピュータとのバイナリ乗算に関するWikipediaの記事を確認してください。これには、優れた効率的なアルゴリズムがいくつかあります。

于 2008-10-11T09:56:37.920 に答える
3

最も簡単な方法は、スクールブック メカニズムを使用して、任意のサイズの数値をそれぞれ 32 ビットのチャンクに分割することです。

ABCD * EFGH (各チャンクは 32 ビット、合計 128 ビット)
の場合、9 dword 幅の出力配列が必要です。Out[0..8] を 0 に設定

H * D + out[8] => 64 ビットの結果。
下位 32 ビットを out[8] に格納し、上位 32 ビットをキャリーとして取得します
次: (H * C) + out[7] + キャリー
再び、下位 32 ビットを out[7] に格納し、上位 32 ビットを使用しますH*A + out[4] + キャリーを実行した後のキャリーとして 32 ビットの場合、キャリー
がなくなるまでループを続ける必要があります。

次に、G、F、E で繰り返し
ます。G の場合、out[8] の代わりに out[7] から開始します。

最後に、大きな整数を数字に変換します (これには、「大きな数を 1 つの単語で割る」ルーチンが必要です)。

于 2008-10-11T05:27:26.090 に答える
1

これが私のC言語のコードです。古き良き乗算方法

char *multiply(char s1[], char s2[]) {
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    int i, j, k = 0, c = 0;
    char *r = (char *) malloc (l1+l2+1); // add one byte for the zero terminating string
    int temp;

    strrev(s1);
    strrev(s2);
    for (i = 0;i <l1+l2; i++) {
        r[i] = 0 + '0';
    }

    for (i = 0; i <l1; i ++) {
        c = 0; k = i;
        for (j = 0; j < l2; j++) {
            temp = get_int(s1[i]) * get_int(s2[j]);
            temp = temp + c + get_int(r[k]);
            c = temp /10;
            r[k] = temp%10 + '0';

            k++;
        }
        if (c!=0) {
            r[k] = c + '0';
            k++;
        }
    }

    r[k] = '\0';
    strrev(r);
    return r;
}
于 2013-08-03T19:25:39.980 に答える
1

はい、事実上数字の文字列であるデータ型を使用してそれを行います（通常の「文字列」が文字列であるように）。これを行う方法は、言語に大きく依存します。たとえば、Java は BigDecimal を使用します。どの言語を使用していますか?

于 2008-10-10T23:57:18.537 に答える
1

これは宿題として出されることが多いです。小学校で学んだアルゴリズムが機能します。実際のアプリケーションでこれが必要な場合は、ライブラリを使用してください (いくつかは他の投稿で言及されています)。

于 2008-10-10T23:59:03.883 に答える