Moltiplicazione cifra per cifra di vettori
Ciao a tutti...
Non sono un matematico ma un informatico e vorrei sapere da voi se c'è un modo per moltiplicare due numeri memorizzati in un vettore cifra per cifra...
Un esempio sarà più chiaro:
Ho due vettori v1=[4,6,2] e v2=[3,2,5]
Vorrei ottenere 150150 = 462 x 325 appunto
Ho questo problema perchè devo moltiplicare numeri di centinaia di cifre che le normali variabili Java non possono gestire...
Ovviamente il numero deve essere nella forma v3=[1,5,0,1,5,0] perchè se i due fattori hanno centinaia di cifre il loro prodotto è minimo della stessa dimesione...
Se vi può aiutare i numeri sono sempre primi...
Esistono classi Java che permettono di fare moltiplicazioni tra numeri enormi ma dovrei evitare di usarle...
Non è detto che esista una soluzione "matematica" ma prima di cercare una soluzione "informatica" chiedo a voi...
Grazie
Non sono un matematico ma un informatico e vorrei sapere da voi se c'è un modo per moltiplicare due numeri memorizzati in un vettore cifra per cifra...
Un esempio sarà più chiaro:
Ho due vettori v1=[4,6,2] e v2=[3,2,5]
Vorrei ottenere 150150 = 462 x 325 appunto
Ho questo problema perchè devo moltiplicare numeri di centinaia di cifre che le normali variabili Java non possono gestire...
Ovviamente il numero deve essere nella forma v3=[1,5,0,1,5,0] perchè se i due fattori hanno centinaia di cifre il loro prodotto è minimo della stessa dimesione...
Se vi può aiutare i numeri sono sempre primi...
Esistono classi Java che permettono di fare moltiplicazioni tra numeri enormi ma dovrei evitare di usarle...
Non è detto che esista una soluzione "matematica" ma prima di cercare una soluzione "informatica" chiedo a voi...
Grazie
Risposte
Un idea, non formalizzo perchè tendo a sbagliare facilmente i pedici: Scrivi i numeri nella rappresentazione polinomiale decimale, in modo che si possa poi utilizzare la moltiplicazione tra polinomi per determinare i "coefficienti" del prodotto.
[Secondo me dovrebbe stare nella sezione informatica]
[Secondo me dovrebbe stare nella sezione informatica]
"Mathematico":
Un idea, non formalizzo perchè tendo a sbagliare facilmente i pedici: Scrivi i numeri nella rappresentazione polinomiale decimale, in modo che si possa poi utilizzare la moltiplicazione tra polinomi per determinare i "coefficienti" del prodotto.
[Secondo me dovrebbe stare nella sezione informatica]
Perché decimale? Scrivi il numero in base [tex]2^{32}[/tex]. Ora a [tex]2^{n32} + b 2^{n32} = (a+b) 2^{n32} = x 2^{(n+1)32} + y 2^{n32}[/tex]. Il trovare [tex]x[/tex] richiede di usare variabili di dimensioni maggiori oppure trucchetti.
Considerando che [tex]a2^{n32}\cdot b2^{n32} = ab 2^{2n32}[/tex] per questo calcolo potrebbe convenirti usare interi a 64 bit.
Il tutto comunque sarebbe definito da una classe che contiene una lista di interi (per poter gestire dinamicamente la gestione della memoria).
Se è per questo si potrebbe usare qualunque base 
. Io non sono abituato a lavorare con quelle diverse da 10. Non avevo proprio pensato ai problemi di implementazioni, costi computazionali, tempi... Sono un pessimo informatico? Sì! 
. Io non sono abituato a lavorare con quelle diverse da 10. Non avevo proprio pensato ai problemi di implementazioni, costi computazionali, tempi... Sono un pessimo informatico? Sì!
"Mathematico":
Se è per questo si potrebbe usare qualunque base
Beh, in realtà avevo letto velocemente e pensato si stesse lavorando ad una implementazione di una classe BigInteger... Il suo problema effettivamente può anche semplicemente fatto usando una rappresentazione decimale (non richiede di memorizzare in maniera semipermanente ulteriore memoria). Comunque non so se 32 è il numero migliore... per esempio con 31 puoi gestire gli overflow meglio. E immagino che le varie SSE possano gestire alcune parti dell'implementazione al meglio. Ci sono libri interi su come implementare cose di questo genere
.
Immagino che se fossi interessato alle performance avresti usato BigInteger, non vedo infatti alcuna ragione per cui non dovresti usarla se non per qualche imposizione esterna (è un esercizio per qualche corso?). Per cui ti mostro algoritmi semplici ma non necessariamente ottimali.
Cerco di mostrarti come fare il prodotto con un esempio. Supponiamo di avere i tuoi numeri 462 e 325. Come calcoleresti questo prodotto a mano? Un modo è il seguente:
Ci siamo a questo punto ridotti al calcolo del prodotto con una sola cifra (che puoi calcolare con un singolo ciclo in cui fai il prodotto, calcoli il modulo e riporti il resto al successivo elemento) e ad una somma (e volendo allo “shift sinistro” delle cifre per la moltiplicazione per potenze di 10). Questo dovrebbe essere più o meno il metodo usato in hardware per fare il calcolo del prodotto tra numeri interi (da quello che mi avevano spiegato qualche tempo fa e non sono per niente un esperto, ma nel caso di cifre binarie la moltiplicazione per 0 o 1 è molto facile*). Questo è quindi un primo metodo molto facile che puoi implementare. Non è efficientissimo, ma per numeri non troppo grandi può essere accettabile.
Il metodo polinomiale è fattibile ma, al contrario di quello precedente, il resto non è limitato ad essere una singola cifra. Il calcolo cioè di [tex]c_i = \sum_{p+q=i} a_p b_q[/tex] potrebbe portare a numeri molto grossi e quindi, a priori, resti molto grandi da portare nel calcolo successivo. Ma per numeri non troppo grandi, usando un intero a 64bit, dovresti poter fare i calcoli in questo modo senza problemi più velocemente che nel caso precedente. Ma è certamente limitato. L'alternativa è ovviamente di calcolare quella sommatoria usando il tuo sistema, ma non credo che sia una buona idea.
Per ottenere performance migliori, conviene ovviamente passare ad una rappresentazione diversa (con base [tex]2^{32}[/tex] o [tex]2^{64}[/tex] ad esempio) per velocizzare i calcoli e sfruttare a pieno la capacità del processore. Esistono poi algoritmi più avanzati, ma credo che valga la pena di considerarli solo per numeri veramente grandi e casi più seri.
* Consiste in un AND tra le cifre del numero e la cifra da moltiplicare.
Cerco di mostrarti come fare il prodotto con un esempio. Supponiamo di avere i tuoi numeri 462 e 325. Come calcoleresti questo prodotto a mano? Un modo è il seguente:
462 * 325 = -------- 2310 + (462*5) 924_ + (462*20) 1386__ = (462*300) -------- 150150
Ci siamo a questo punto ridotti al calcolo del prodotto con una sola cifra (che puoi calcolare con un singolo ciclo in cui fai il prodotto, calcoli il modulo e riporti il resto al successivo elemento) e ad una somma (e volendo allo “shift sinistro” delle cifre per la moltiplicazione per potenze di 10). Questo dovrebbe essere più o meno il metodo usato in hardware per fare il calcolo del prodotto tra numeri interi (da quello che mi avevano spiegato qualche tempo fa e non sono per niente un esperto, ma nel caso di cifre binarie la moltiplicazione per 0 o 1 è molto facile*). Questo è quindi un primo metodo molto facile che puoi implementare. Non è efficientissimo, ma per numeri non troppo grandi può essere accettabile.
Il metodo polinomiale è fattibile ma, al contrario di quello precedente, il resto non è limitato ad essere una singola cifra. Il calcolo cioè di [tex]c_i = \sum_{p+q=i} a_p b_q[/tex] potrebbe portare a numeri molto grossi e quindi, a priori, resti molto grandi da portare nel calcolo successivo. Ma per numeri non troppo grandi, usando un intero a 64bit, dovresti poter fare i calcoli in questo modo senza problemi più velocemente che nel caso precedente. Ma è certamente limitato. L'alternativa è ovviamente di calcolare quella sommatoria usando il tuo sistema, ma non credo che sia una buona idea.
Per ottenere performance migliori, conviene ovviamente passare ad una rappresentazione diversa (con base [tex]2^{32}[/tex] o [tex]2^{64}[/tex] ad esempio) per velocizzare i calcoli e sfruttare a pieno la capacità del processore. Esistono poi algoritmi più avanzati, ma credo che valga la pena di considerarli solo per numeri veramente grandi e casi più seri.
* Consiste in un AND tra le cifre del numero e la cifra da moltiplicare.
Innanzi tutto scusate se ho sbagliato sezione...
Grazie per tutte le risposte che mi avete dato... non avevo pensato alla soluzione di cambiare la rappresentazione dei numeri, proverò sicuramente...
In effetti come scrive apatriarca, il divieto di usare BigInteger è stato imposto a priori... una versione dell'algoritmo (crittografia RSA) l'ho già implementata con BigInteger e funziona...
RSA non è complesso da realizzare, il problema è appunto la gestione dei grandi numeri (anche fino a 1024 bit)...
La moltiplicazione in colonna è un'idea che avevo avuto anche io ma i risultati dei parziali avrebbero comunque una dimensione notevole...
Vi farò sapere...
Grazie ancora
Grazie per tutte le risposte che mi avete dato... non avevo pensato alla soluzione di cambiare la rappresentazione dei numeri, proverò sicuramente...
In effetti come scrive apatriarca, il divieto di usare BigInteger è stato imposto a priori... una versione dell'algoritmo (crittografia RSA) l'ho già implementata con BigInteger e funziona...
RSA non è complesso da realizzare, il problema è appunto la gestione dei grandi numeri (anche fino a 1024 bit)...
La moltiplicazione in colonna è un'idea che avevo avuto anche io ma i risultati dei parziali avrebbero comunque una dimensione notevole...
Vi farò sapere...
Grazie ancora
$2^1024$ ha solo 309 cifre, non lo definirei un array di dimensioni notevoli... Usando una rappresentazione basata su una potenza di due utilizzi meglio l'hardware, ma secondo me anche il semplice algoritmo della moltiplicazione in colonna è abbastanza efficiente. Nota che puoi moltiplicare per una cifra e sommare il nuovo prodotto con il risultato parziale nello stesso ciclo (mantenendo un resto da passare alla cifra successiva).
"apatriarca":
$2^1024$ ha solo 309 cifre, non lo definirei un array di dimensioni notevoli...
Mi riferivo al numero non all'array...
Comunque esiste anche la moltiplicazione araba... ma non è facile farne un algoritmo...
Anche io mi riferivo a quello. Alla fine le operazioni su quel numero si ridurrebbero a operazioni su array di circa 300 valori (lavorando in decimale) e solo 128 byte nel caso in cui volessi usare i byte (ancora meno se usi degli int o long). I numeri saranno anche molto grossi, ma non devi sottovalutare le capacità del tuo computer che è in grado di operare su milioni di oggetti in tempo reale.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo