Wie kann ich einen Überlauf bei der modularen Multiplikation vermeiden?

Question

Ich weiß, dass,

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

Aber es eine Möglichkeit des Überlaufes ist. Zur Vereinfachung wird angenommen, dass die Größe der Ganzzahl 2 Bits ist. Wenn a = 2 (dh 10) und b = 2 (dh 10), m = 3 (dh 11), dann a% m und B% m ausfallen 2 sein, und nach der Multiplikation ist die Antwort 4 (dh 100), die nicht in die Ganzzahl passt. Die endgültige Antwort ist 0, wenn 2-lsbs von 4 betrachtet werden. Aber die tatsächliche Antwort ist 1.

Was soll ich tun, um diese Situation zu vermeiden?

Answer 1

Wenn m-1 Quadrat nicht in Ihren Integer-Typ passt, müssen Sie eine lange Multiplikation durchführen. Für Ihr Zwei-Bit-Beispiel bedeutet das, dass Sie Ihre Zwei-Bit-Zahlen in Paare von Ein-Bit-Zahlen (ein High-Bit und ein Low-Bit) aufteilen und alle vier Paare multiplizieren (hoch zu hoch, hoch zu niedrig, niedrig zu hoch, niedrig) von niedrig) individuell. Sie können dann das Ergebnis mod m für jedes Paar erhalten (die tatsächlichen Orte, die sie repräsentieren, z. B. vier, zwei oder eins) und die Ergebnisse mod m hinzufügen.

Answer 2

Viele kleine Prozessor C-Implementierungen können das Ergebnis einer mathematischen Operation für Überlauf/Unterlauf direkt überprüfen.

Eine andere Möglichkeit besteht darin, ein empfangendes Feld zu verwenden, das doppelt so lang ist wie die zugrunde liegende int-Größe I.E. Für eine int-Größe von 2 verwenden Sie ein Ergebnisfeld von 4 Bytes. (vielleicht durch eine lange lange int) oder übertragen Sie beide Zahlen in doppelte Felder und multiplizieren sie dann wieder zurück in int (aber einige Genauigkeit im Ergebnis (IE die niedrigste Zahl) kann ungenau sein.

Eine andere Möglichkeit ist es verwenden, um eine entsprechende Funktion aus der Bibliothek math.h

eine weitere Möglichkeit, lange Multiplikation verwenden Arrays. dies von 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; 

}

Probe kopiert wurde Ausgabe von oben Code:

die erste Nummer eingeben: 55555555

die zweite Zahl eingeben: 3333333333

Multiplikation von zwei Zahlen:

Logic für die Multiplikation großer Zahlen

Wie wir in c wissen, gibt es keine solchen Datentypen, die eine sehr große Zahl speichern können rs. Zum Beispiel wollen wir den Ausdruck lösen:

55555555 * 3333333333

Ergebnis obigen Ausdruck sehr große Zahl ist, die über den Bereich sogar long int oder long double. Dann ist die Frage, wie man so große Zahlen in c speichern kann?

Lösung ist sehr einfach, d.h. mit Array.Das obige Programm hat dieselbe Logik verwendet, die wir wie üblich verwenden, um zwei Zahlen zu multiplizieren, außer die Daten in den normalen Variablen zu speichern, die wir in dem Array speichern.