L'obiettivo è calcolare una potenza di numeri estremamente grandi, in modulo, con javascript.
Per chi non avesse la nozione di modulo, una piccola spiegazione:
Una potenza in modulo si calcola semplicemente risolvendo la potenza e applicando il modulo.
Esempio:
Il problema è che calcolare una potenza in questo modo risulta molto sconveniente in javascript quando si usano numeri da 300 cifre, poiché si arriverebbe a superare il valore massimo degli interi e quindi succederebbero cose orribili al mondo.
Per cui ho pensato di usare una proprietà del modulo, che mi permette di applicare il modulo anche ad ogni moltiplicazione e non solo a operazione finita:
a^n = a*a*a*...*a*a (n volte), quindi [a^n] = [a*a*a*a*...*a*a] = [[...[[[[[a*a]*a]*a]*a]*...*a], dove [] indicano l'applicazione del modulo.
Ciò mi permette di non superare mai il numero n, numero del modulo "(mod n)".
Per questo ho creato questa banalissima funzione, che però non funziona:
Per quale motivo non funziona? (mi sento un ritardato)
Per chi non avesse la nozione di modulo, una piccola spiegazione:
Se in un orologio prendiamo il numero 3, se lo sommiamo con 10, darà come risultato 1, non 13. Un orologio è infatti un sistema a modulo 12.
Se prendiamo 2 e lo sommiamo a 6, in un orologio con i numeri 0, 1 e 2, darà come risultato 2, ovvero il resto dato della divisione 8/3.
Un numero a, espresso in modulo n, corrisponde al resto della divisione tra a ed n.
In pratica:
Se prendiamo 2 e lo sommiamo a 6, in un orologio con i numeri 0, 1 e 2, darà come risultato 2, ovvero il resto dato della divisione 8/3.
Un numero a, espresso in modulo n, corrisponde al resto della divisione tra a ed n.
In pratica:
a (mod n) = a % n
Dove "a%n" corrisponde al resto della divisione a/n, e "(mod n)" indica che c'è da applicare il modulo.
Dove "a%n" corrisponde al resto della divisione a/n, e "(mod n)" indica che c'è da applicare il modulo.
Una potenza in modulo si calcola semplicemente risolvendo la potenza e applicando il modulo.
Esempio:
3^4 (mod 5) --> 81 (mod 5) --> 81 % 5 = 1 => 3^4 (mod 5) = 1 (mod 5)
Il problema è che calcolare una potenza in questo modo risulta molto sconveniente in javascript quando si usano numeri da 300 cifre, poiché si arriverebbe a superare il valore massimo degli interi e quindi succederebbero cose orribili al mondo.
Per cui ho pensato di usare una proprietà del modulo, che mi permette di applicare il modulo anche ad ogni moltiplicazione e non solo a operazione finita:
a^n = a*a*a*...*a*a (n volte), quindi [a^n] = [a*a*a*a*...*a*a] = [[...[[[[[a*a]*a]*a]*a]*...*a], dove [] indicano l'applicazione del modulo.
Ciò mi permette di non superare mai il numero n, numero del modulo "(mod n)".
Per questo ho creato questa banalissima funzione, che però non funziona:
Codice:
//a è la base della potenza, x l'esponente e mod il modulo
var powmod = function(a, x, mod){
var t = 1;
while(x > 0){
t = (t*a) % mod;
x=x-1;
}
return t;
};
Per quale motivo non funziona? (mi sento un ritardato)