6

そんなこと知ってる、

(a*b)%m = ((a%m)*(b%m))%m

しかし、オーバーフローの可能性があります。簡単にするために、整数のサイズが 2 ビットであると仮定します。a = 2 (つまり 10 2 ) かつ b = 2 (つまり 10 2 )、m = 3 (つまり 11 2 ) の場合、a%m と b%m は 2 になり、乗算後の答えは 4 (つまり100) は整数サイズに収まりません。2-lsb を 4 から考えると、最終的な答えは 0 になります。しかし、実際の答えは 1 です。

この状況を回避するにはどうすればよいですか?

4

2 に答える 2

4

m-1二乗が整数型に収まらない場合は、長い乗算を実行する必要があります。2ビットの例では、2ビットの数値を1ビットの数値のペア(上位ビットと下位ビット)に分割し、4つのペアすべてを乗算することを意味します(高と高、高と低、低と高、低)低によって)個別に。次に、各ペアの結果の modmを取得し (それらが表す実際の位置、つまり、4、2、または 1 に注意してください)、結果の mod を追加できますm

于 2015-02-01T05:39:17.943 に答える
1

多くの小さなプロセッサの C 実装では、オーバーフロー/アンダーフローの数学演算の結果を直接チェックできます。

もう 1 つの方法は、基になる int サイズ IE の 2 倍の長さの受信フィールドを使用して、int サイズを 2 にし、4 バイトの結果フィールドを使用することです。(おそらく long long int によって) または両方の数値を double フィールドに転送し、乗算してから int に戻します (ただし、結果の精度 (最下位桁) が不正確になる場合があります。

もう 1 つの方法は、math.h ライブラリから適切な関数を使用することです。

別の方法は、配列を使用して長い乗算を使用することです。これはhttp://www.cquestions.com/2010/08/multiplication-of-large-numbers-in-c.htmlからコピーされました

#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#include<string.h>
#define MAX 10000

char * multiply(char [],char[]);
int main(){
    char a[MAX];
    char b[MAX];
    char *c;
    int la,lb;
    int i;
    printf("Enter the first number : ");
    scanf("%s",a);
    printf("Enter the second number : ");
    scanf("%s",b);
    printf("Multiplication of two numbers : ");
    c = multiply(a,b);
    printf("%s",c);
    return 0;
}

char * multiply(char a[],char b[]){
    static char mul[MAX];
    char c[MAX];
    char temp[MAX];
    int la,lb;
    int i,j,k=0,x=0,y;
    long int r=0;
    long sum = 0;
    la=strlen(a)-1;
    lb=strlen(b)-1;

    for(i=0;i<=la;i++){
            a[i] = a[i] - 48;
    }

    for(i=0;i<=lb;i++){
            b[i] = b[i] - 48;
    }

    for(i=lb;i>=0;i--){
        r=0;
        for(j=la;j>=0;j--){
            temp[k++] = (b[i]*a[j] + r)%10;
            r = (b[i]*a[j]+r)/10;
        }
        temp[k++] = r;
        x++;
        for(y = 0;y<x;y++){
            temp[k++] = 0;
        }
   }

   k=0;
   r=0;
   for(i=0;i<la+lb+2;i++){
        sum =0;
        y=0;
        for(j=1;j<=lb+1;j++){
            if(i <= la+j){
                sum = sum + temp[y+i];
            }
            y += j + la + 1;
        }
        c[k++] = (sum+r) %10;
        r = (sum+r)/10;
   }
   c[k] = r;
   j=0;
   for(i=k-1;i>=0;i--){
      mul[j++]=c[i] + 48;
   }
   mul[j]='\0';
   return mul;

}

上記のコードのサンプル出力:

最初の数字を入力してください: 55555555

2 番目の数字を入力してください: 3333333333

2 つの数の乗算:

185185183314814815

大きな数の乗算のロジック

私たちが c で知っているように、非常に大きな数を格納できるようなデータ型はありません。たとえば、次の式を解きたいとします。

55555555 * 3333333333

上記の式の結果は、long int や long double の範囲を超える非常に大きな数値になります。次に問題は、そのような大きな数を c に格納する方法です。

解決策は非常に簡単です。つまり、配列を使用します。上記のプログラムは、配列に格納する通常の変数にデータを格納する代わりに、通常のロジックを使用して 2 つの数値を乗算するのと同じロジックを使用しています。

于 2015-02-01T06:18:16.827 に答える