[Java] Moltiplicazione modulare multiprecisione.

[b4kk3]

ciao a tutti!
devo moltiplicare tra di loro due numeri organizzati ognuno in 6 word da 32 bit...
la moltiplicazione di per se non è difficile, moltiplico il moltiplicando per ogni bit del moltiplicatore shiftando e poi faccio la simma bit a bit ma che tipo di struttura mi conviene utilizzare, per immagzzinare i dati e il risultato? e in che modo?
ringrazio in anticipo chi ha voglia di perdere un pò di tempo con me! thanx!

[andbin]

Originariamente inviato da b4kk3
devo moltiplicare tra di loro due numeri organizzati ognuno in 6 word da 32 bit...
la moltiplicazione di per se non è difficile, moltiplico il moltiplicando per ogni bit del moltiplicatore shiftando e poi faccio la simma bit a bit ma che tipo di struttura mi conviene utilizzare, per immagzzinare i dati e il risultato? e in che modo?

Domanda: è un "esercizio didattico" per cui ti è stato chiesto esplicitamente di implementare tu un algoritmo appropriato?

Perché per queste cose (calcoli a "precisione arbitraria") esiste la classe java.math.BigInteger che è sicuramente migliore e più efficiente di quanto potresti fare tu.

Se invece devi farlo proprio tu, una soluzione è quella che hai detto, cioè operare sui bit e fare anche degli shift. Ma la vedo più lunga e difficile (specialmente lo shift).
Un'altra soluzione è fare le moltiplicazioni a pezzi di N x N bit. In questa vecchia discussione avevo mostrato lo schema per fare una moltiplicazione 16x16 bit "sapendo" fare solo moltiplicazioni 8x8 bit. Nella discussione si parlava espressamente di linguaggio Assembly ma il concetto comunque è quello e non cambia.

Il mio suggerimento è di tenere il tuo "big number" memorizzato in un array di int (quindi int[]) e poi fare moltiplicazioni 64x64 bit dove però la parte alta è 0.
In pratica 2 int li converti a long facendo una apposita mascheratura (perché altrimenti si estende il segno) e poi li moltiplichi. È chiaro che devi poi fare delle somme e tenere in considerazione il "carry".

Ma sappi che questo modo di operare è proprio quello che viene usato dal BigInteger di Java. Quindi non è certo una cosa così "campata in aria".

[b4kk3]

grazie per il reply...in realtà è una parte di un piccolo benchmark per cellulari e lo devo sviluppare solo con le api messe a disposizione dall'MIDP 2.0 del J2ME...per questo non posso utilizzare i biginteger! non sono inclusi in quelle librerie!
comunque cercherò di seguire il tuo consiglio, in effetti pensavo di utilizzare l'array di int ma come faccio ad accedere al singolo bit della i-esima posizione?

[andbin]

Originariamente inviato da b4kk3
comunque cercherò di seguire il tuo consiglio, in effetti pensavo di utilizzare l'array di int ma come faccio ad accedere al singolo bit della i-esima posizione?

Se fai come ho spiegato anche in quella discussione, non ti serve accedere ad 1 singolo bit!!!
Devi solo trattare il tuo big number come N word (word in senso generale, una "parola" di N bit), nel tuo caso N int.

Dati i due array int[] uno e int[] due, devi moltiplicare uno[0] * due[0] ecc....
Chiaramente devi prima portarli a long tramite una apposita mascheratura, altrimenti se non lo fai perdi la parte alta e se non mascheri, estendi il segno che non va bene.

[b4kk3]

ho capito, nel fare la somma di due singoli int li casto a long, giusto?
grazie tante per la spiegazione!

[andbin]

Originariamente inviato da b4kk3
ho capito, nel fare la somma di due singoli int li casto a long, giusto?

No, devi fare una operazione di AND bitwise con una costante long che ha i 32 bit alti a 0 e i 32 bit bassi a 1. E il risultato, essendo uno degli operandi un long, è chiaramente un long.

[b4kk3]

Ah, cioè ero totalmente fuori strada!:-)
dunque, ricapitolando (e vediamo se stavolta ho capito bene):
- prendo i miei int e li converto a long mascherandoli con un long che ha i 32 bit alti a 0 e i 32 bassi a 1 (questo facendo una AND bitwise) altrimenti perdo la parte alta ed estendo il segno;
- a questo punto faccio le moltiplicazioni come spiegato nel tuo schema;
- sommo tenendo in considerazione il carry.

Perdona l'ignoranza ma ho alcune altre cose da chiedere:

1) come imposto i 32 bit bassi del long a 1?
2) come faccio a fare una AND bitwise con un long?
3) il risultato finale (dopo le somme) lo salvo in un altro array, questa volta di long?

grazie x la pazienza!;-)

[andbin]

Originariamente inviato da b4kk3
1) come imposto i 32 bit bassi del long a 1?

long mask = 0xFFFFFFFFL;

Originariamente inviato da b4kk3
2) come faccio a fare una AND bitwise con un long?

long res = l1 & l2;

Originariamente inviato da b4kk3
3) il risultato finale (dopo le somme) lo salvo in un altro array, questa volta di long?

No, devi spezzarlo in 2 int, guarda bene lo schema che avevo postato in quella discussione.
Devi creare un array di int che sia sufficiente per contenere il massimo risultato. Se fai 32x32 bit avrai al massimo 64 bit e così via.... Se in input hai un valore di 3 int moltiplicato per un valore di 5 int, il risultato massimo starà in un valore composto di 8 int.

[b4kk3]

ok, adesso ci provo!

thanx a lot!

[b4kk3]

ok, sono riuscito a fare le moltiplicazioni, adesso ho i risultati parziali su 64 bit.
A questo punto devo shiftare e sommare tenendo conto del carry...
cioè, devo sommare la parte alta del primo long con quella bassa della secondo long e così via, secondo lo schema, giusto? ma allora devo shiftare il secondo long...con quali istruzioni lo posso fare? e il carry come lo gestisco?