Come evitare l'overflow nella moltiplicazione modulare?

Question

So che,

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

Ma c'è una possibilità di trabocco. Per semplicità, assumiamo che la dimensione del numero intero sia di 2 bit. Se a = 2 (cioè 10) e b = 2 (cioè 10), m = 3 (ossia 11), quindi un% m e b% m rivelarsi 2 e dopo la moltiplicazione, la risposta è 4 (cioè 100) che non si adatta alla dimensione intera. La risposta finale sarà 0 se 2-lsb sono considerati da 4. Ma la risposta effettiva è 1.

Cosa devo fare per evitare questa situazione?

Answer 1

Se m-1 al quadrato non si adatta al tipo intero, è necessario eseguire una moltiplicazione lunga. Per il tuo esempio a due bit, ciò significa rompere i tuoi numeri a due bit in coppie di numeri a un bit (un bit alto e un bit basso) e moltiplicare tutte e quattro le coppie (alto per alto, alto per basso, basso per alto, basso da basso) individualmente. È quindi possibile ottenere il risultato mod m per ciascuna coppia (prendendo nota dei luoghi effettivi che rappresentano, cioè quattro, due o uno) e aggiungere i risultati mod m.

Answer 2

molte piccole implementazioni C del processore possono controllare direttamente il risultato di un'operazione matematica per overflow/underflow.

Un altro modo è utilizzare un campo di ricezione che è il doppio della lunghezza della dimensione int sottostante I.E. per una dimensione int di 2, utilizzare un campo risultato di 4 byte. (forse con un lungo int lungo) o trasferire entrambi i numeri in doppio campo e moltiplicarli quindi riconvertire in int (tuttavia, una certa precisione nel risultato (IE la cifra meno significativa) potrebbe essere imprecisa

Un altro modo è utilizzare una funzione appropriata dalla libreria math.h

un altro modo è quello di utilizzare lungo la moltiplicazione utilizzando matrici:. questo è stato copiato da 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; 

}

Esempio output del codice precedente:

Inserire il primo numero: 55555555

Inserire il secondo numero: 3333333333

moltiplicazione di due numeri:

logica per la moltiplicazione dei grandi numeri

Come sappiamo in c non ci sono tali tipi di dati che possono memorizzare un numero molto grande rs. Per esempio vogliamo risolvere l'espressione:

55555555 * 3333333333

Risultato di espressione di cui sopra è molto grande numero che al di là della gamma di anche long int o long double. Quindi la domanda è come memorizzare un numero così grande in c?

La soluzione è molto semplice, ad esempio utilizzando la matrice.Al di sopra del programma è stata utilizzata la stessa logica che stiamo usando come logica usuale per moltiplicare due numeri, tranne che invece di memorizzare i dati nelle normali variabili che stiamo memorizzando nell'array.