Divisione tra grandi numeri primi
salve a tutti
non so se ho postato nella sessione giusta
mi hanno cosigliato di metterlo qui speriamo bene!
siccome sto scrivendo una classe numerica in c++ e assembler mi sono scontrato con il seguente problema:
come faccio a fare la divisione tra grandi numeri ?
una prima parte del problema penso di averla risolta riducendo i numeri utilizzando il metodo del MCD e poi utilizzando la divisione scolastica.
però come posso affrontare il problema se ho un numero primo e un numero normale oppure 2 numeri primi?
qualcuno conosce un algoritmo che mi possa aiutare?
ho gia cercato su internet, ma forse ho cercato nei siti sbagliati, non ho trovato nulla che mi possa aiutare o illuminare.
ringrazio anticipatamente tutti coloro che mi aiuteranno
non so se ho postato nella sessione giusta
mi hanno cosigliato di metterlo qui speriamo bene!
siccome sto scrivendo una classe numerica in c++ e assembler mi sono scontrato con il seguente problema:
come faccio a fare la divisione tra grandi numeri ?
una prima parte del problema penso di averla risolta riducendo i numeri utilizzando il metodo del MCD e poi utilizzando la divisione scolastica.
però come posso affrontare il problema se ho un numero primo e un numero normale oppure 2 numeri primi?
qualcuno conosce un algoritmo che mi possa aiutare?
ho gia cercato su internet, ma forse ho cercato nei siti sbagliati, non ho trovato nulla che mi possa aiutare o illuminare.
ringrazio anticipatamente tutti coloro che mi aiuteranno
Risposte
La domanda è come fare la divisione tra numeri che non sono uno multiplo dell'altro?
la domanda riguarda quei numeri che non si possono ridurre
esempi giusto per far capire ma i numeri potrebbero essere molto più grandi
esempio 1:
9887 / 8803 entrambi sono numeri primi
esempio 2:
10389745126 / 8803
10389745126 e divisibile almeno per 17
8803 numero primo
adesso il problema consiste nel fatto che per fare le divisioni ho dei limiti di cifre
per gli int a 32 bit il limite e 10 cifre max 4.294.967.295
mentre gli int a 64 bit hanno un limite di 20 cifre max 18.446.744.073.709.551.615
io vorrei andare oltre questi limiti.
riducendo il numero con l' MCD supero questo limite (un pò lenta come tecnica ma funziona!)
ma restano i casi in cui non si trova un MCD
quello che servirebbe a me e un sistema come risolvere i casi in cui non trovo un MCD.
spero che adesso il problema sia più chiaro.
esempi giusto per far capire ma i numeri potrebbero essere molto più grandi
esempio 1:
9887 / 8803 entrambi sono numeri primi
esempio 2:
10389745126 / 8803
10389745126 e divisibile almeno per 17
8803 numero primo
adesso il problema consiste nel fatto che per fare le divisioni ho dei limiti di cifre
per gli int a 32 bit il limite e 10 cifre max 4.294.967.295
mentre gli int a 64 bit hanno un limite di 20 cifre max 18.446.744.073.709.551.615
io vorrei andare oltre questi limiti.
riducendo il numero con l' MCD supero questo limite (un pò lenta come tecnica ma funziona!)
ma restano i casi in cui non si trova un MCD
quello che servirebbe a me e un sistema come risolvere i casi in cui non trovo un MCD.
spero che adesso il problema sia più chiaro.
Vagamente più chiaro. Mi sembra che il problema sia nella struttura dati per memorizzare i numeri, quindi, non in come eseguire effettivamente la divisione.
Questo significa che l'argomento va spostato in informatica, e a questo penserò io.
Per rispondere alla tua domanda, ipotizzando che tu non voglia utilizzare librerie già esistenti, io credo che dovresti progettare una classe in cui viene allocato dinamicamente [=[inline]std::vector[/inline]] il numero spezzando le sue cifre.
Per esempio se un intero potesse gestire solo numeri di due cifre, allora il numero \(12345\) andrebbe memorizzato come il vettore \(01,23,45\).
Questa é la prima idea che mi viene in mente.
Questo significa che l'argomento va spostato in informatica, e a questo penserò io.
Per rispondere alla tua domanda, ipotizzando che tu non voglia utilizzare librerie già esistenti, io credo che dovresti progettare una classe in cui viene allocato dinamicamente [=[inline]std::vector[/inline]] il numero spezzando le sue cifre.
Per esempio se un intero potesse gestire solo numeri di due cifre, allora il numero \(12345\) andrebbe memorizzato come il vettore \(01,23,45\).
Questa é la prima idea che mi viene in mente.
Non ho ben capito quale sia il problema, potresti essere più chiaro? Cosa devi fare di preciso?
Con divisione intendi quella intera?
Il problema è semplicemente trattare numeri (dividendo e/o divisore) che vanno oltre i limiti imposti dal numero di bit, o ci sono problemi di overflow durante i calcoli?
Con divisione intendi quella intera?
Il problema è semplicemente trattare numeri (dividendo e/o divisore) che vanno oltre i limiti imposti dal numero di bit, o ci sono problemi di overflow durante i calcoli?
entrambe le divisioni sia quella intera che quella float.
trattare numeri (dividendo e/o divisore) che vanno oltre i limiti imposti dal numero di bit.
e volevo usare il metodo del MCD per ridurre i numeri al fine di poter poi eseguire la divisione normale.
ma per casi simili a quelli citati negli esempio non ho proprio idea di come fare.
trattare numeri (dividendo e/o divisore) che vanno oltre i limiti imposti dal numero di bit.
e volevo usare il metodo del MCD per ridurre i numeri al fine di poter poi eseguire la divisione normale.
ma per casi simili a quelli citati negli esempio non ho proprio idea di come fare.
x raptorista
e quello che stò cercando di fare una classe numerica solo che mi incaglio su quel problema.
per quanto riguarda la struttura e leggermente più complicata di quella da te proposta.
se ci riesco int, double e float saranno un lontano ricordo!
e quello che stò cercando di fare una classe numerica solo che mi incaglio su quel problema.
per quanto riguarda la struttura e leggermente più complicata di quella da te proposta.
se ci riesco int, double e float saranno un lontano ricordo!
Il metodo classico per rappresentare un numero più grande di quanto disponibile sul tuo sistema è quello di usare un array di numeri interi. Dal punto di vista teorico corrisponde a scrivere il tuo numero come successione di cifre con base \(2^{32}\) (o \(2^{64}\)) e fare le operazioni in tale base. Algoritmi specifici vengono usati in questi casi per ridurre il numero di operazioni necessari rispetto ai comuni algoritmi. Più tardi vedo se riesco a scrivere un piccolo codice di esempio.
con la rappresentazione dei bit non ho problemi il problema sta quando devo dividere il numero!
già faccio una cosa del genere.
dovrò pur ridurre il numero per farlo entrare in un registro a 32 o 64 bit per fare l'operazione!
e il problema consiste proprio nella riduzione del numero che se è primo o non ha un fattore di riduzione, MCD , comune all'altro numero non so come fare!
già faccio una cosa del genere.
dovrò pur ridurre il numero per farlo entrare in un registro a 32 o 64 bit per fare l'operazione!
e il problema consiste proprio nella riduzione del numero che se è primo o non ha un fattore di riduzione, MCD , comune all'altro numero non so come fare!
No, non devi ridurre il numero a 32 o 64 bit.. Come ho detto ci sono algoritmi particolari usati. Da quel poco che so, credo venga trasformata la divisione in una sequenza di prodotti. Siccome esistono algoritmi molto efficienti per la moltiplicazione, questa riduzione è più conveniente di una divisione con gli algoritmi classici (usati per i calcoli a mano o nei microprocessori ad esempio). Come punto di partenza direi però che potresti cercare di implementare la divisione lunga e la divisione per un divisore che sta in 32 o 64 bit (a seconda della cifra che usi).
finchè il divisore sta nei limiti la divisione modello scuola elementare va più che bene
ma quando esce dai limiti, secondo te, va bene se adoperassi un loop di sottrazioni?
ma quando esce dai limiti, secondo te, va bene se adoperassi un loop di sottrazioni?
Non vedo come potrebbe essere più veloce. Nel caso della divisione "modello scuola elementare" la complessità è \(O((M - N)\,N)\) dove \(M\) è il numero di cifre del dividendo e \(N\) è il numero di cifre del divisore. Nel caso invece di una divisione per sottrazioni la complessità è uguale a \(O(b^{M - N})\) dove \(b\) è la base delle cifre. Confronta il numero di passaggi che dovresti fare per entrambi gli algoritmi per calcolare qualcosa come \(10^9 / 2\).. Sono certo che troveresti più veloce calcolare il valore con la divisione da scuola elementare rispetto alle sottrazioni.
se è cosi lenta e meglio evitare le sottrazioni.
però si torna al medesimo problema.
come potrei fare quando i numeri superano le dimensioni del sistema?
però si torna al medesimo problema.
come potrei fare quando i numeri superano le dimensioni del sistema?
Ma te l'ho già spiegato.. O vai a guardare gli algoritmi di riduzione di cui parlavo prima oppure implementi l'algoritmo usato nella divisione a mano. L'unica differenza rispetto a quello che fai a mano è che le cifre non saranno in base 10, ma con una base molto più grande in modo da usare la divisione intera del microprocessore. Si chiama divisione lunga (long division) e la si trova facilmente su internet.
Te lo ha già detto ... io, da profano, una volta per sfizio ho fatto proprio così: converti il numero da decimale ad una base "grande" ma gestibile (per esempio $2^8$ o$2^16$), poi operi sul numero così ottenuto (tenendo conto dei riporti, ovviamente) e poi riconverti ...
Cmq, esistono librerie "ad hoc" per gestire "numeri grandi" ...
Cmq, esistono librerie "ad hoc" per gestire "numeri grandi" ...
per gli algoritmi di riduzione quelli che ho trovato si basano tutti sul MCD e quindi come spiegato prima in alcuni casi non funzionano.
per quanto riguarda gli algoritmi di conversione a basi diverse in questo caso non convengono in quanto rallenterebbero di molto la divisione per non parlare del costo di memoria di cui hanno bisogno.
perchè sarebbero 3 algoritmi lanciati in sequenza.
1) per la conversione.
1) per la divisione.
1) per la riconversione.
qualche altra idea?
per quanto riguarda gli algoritmi di conversione a basi diverse in questo caso non convengono in quanto rallenterebbero di molto la divisione per non parlare del costo di memoria di cui hanno bisogno.
perchè sarebbero 3 algoritmi lanciati in sequenza.
1) per la conversione.
1) per la divisione.
1) per la riconversione.
qualche altra idea?
Se fosse come dici tu, queste idee non verrebbero usate nelle librerie che implementano tali funzionalità. Eppure è esattamente quello che fanno. Non c'è alcuna conversione necessaria, nessun rallentamento dovuto al loro uso e nessun costo eccessivo di memoria. Queste "cifre" sono infatti usate in tutte le operazioni sui numeri di dimensione arbitraria ed è quindi esattamente come vengono memorizzati tali numeri. La dimensione delle cifre di 32 o 64 bit è pensata in modo da usare le operazioni native del processore per velocizzare i calcoli.
Ma dai tuoi commenti mi vengono spontanee alcune domande:
1. Come rappresenti questi numeri?
2. Quanto grandi sono effettivamente i numeri su cui vuoi lavorare?
3. Quali sono gli scopi di questo progetto?
4. Che conoscenze di informatica/analisi numerica/algebra hai?
Ma dai tuoi commenti mi vengono spontanee alcune domande:
1. Come rappresenti questi numeri?
2. Quanto grandi sono effettivamente i numeri su cui vuoi lavorare?
3. Quali sono gli scopi di questo progetto?
4. Che conoscenze di informatica/analisi numerica/algebra hai?
@apatriarca
Ovviamente io da dilettante facevo le conversioni in modo "scolastico" ma presumevo (e presumo) che sfruttando la rappresentazione in bit dei numeri le conversioni siano più "facili" ... o mi sbaglio? (d'altronde la conversione decimale/binario è una cosa normalissima ...)
Ovviamente io da dilettante facevo le conversioni in modo "scolastico" ma presumevo (e presumo) che sfruttando la rappresentazione in bit dei numeri le conversioni siano più "facili" ... o mi sbaglio? (d'altronde la conversione decimale/binario è una cosa normalissima ...)
Ma non devi lavorare su cifre decimali.. Devi lavorare su "cifre" di interi a 32/64 bit facendo l'operazione su tutto il blocco. L'operazione è del tutto equivalente a quella scolastica, ma ovviamente cambia la base. L'idea però di "allineare" le cifre rimane lo stesso.
Sì,ok ... mi sono espresso male, riprovo ... 
In input hai un numero decimale che poi viene convertito in binario perché possa essere gestito dal computer, quindi una procedura di conversione c'è, no? La prima questione perciò è: questa procedura ha dei limiti di dimensioni? Presumo di sì (per quel che ne so un numero in input lo inserisci in una qualche variabile di qualche tipo (numerico), che ha dei limiti, perciò quando questo è troppo grande prima lo leggi in qualche modo (come stringa per esempio) e poi lo elabori per "spezzarlo" in modo da metterlo nelle "normali" variabili).
Fatto questo, non puoi operare "normalmente" su tali numeri (perché "spezzati") ma devi costruire una procedura specifica; sommare e moltiplicare non è un problema, dividere se anche il dividendo è troppo grande non è poi così banale (ovviamente parlo di operare in un ambito "normale", "scolastico", usando le quattro operazioni e non "giochetti" sui bit, non so se mi spiego ... e altrettanto ovviamente escludendo librerie specifiche per trattare questi numeri).
E alla fine devi riconvertire i risultati in decimale (anche qui usando qualche cosa di "non standard").
Concludendo, quando parlavo di "convertire" intendevo questo, non in ogni singolo passaggio ...
Cordialmente, Alex
In input hai un numero decimale che poi viene convertito in binario perché possa essere gestito dal computer, quindi una procedura di conversione c'è, no? La prima questione perciò è: questa procedura ha dei limiti di dimensioni? Presumo di sì (per quel che ne so un numero in input lo inserisci in una qualche variabile di qualche tipo (numerico), che ha dei limiti, perciò quando questo è troppo grande prima lo leggi in qualche modo (come stringa per esempio) e poi lo elabori per "spezzarlo" in modo da metterlo nelle "normali" variabili).
Fatto questo, non puoi operare "normalmente" su tali numeri (perché "spezzati") ma devi costruire una procedura specifica; sommare e moltiplicare non è un problema, dividere se anche il dividendo è troppo grande non è poi così banale (ovviamente parlo di operare in un ambito "normale", "scolastico", usando le quattro operazioni e non "giochetti" sui bit, non so se mi spiego ... e altrettanto ovviamente escludendo librerie specifiche per trattare questi numeri).
E alla fine devi riconvertire i risultati in decimale (anche qui usando qualche cosa di "non standard").
Concludendo, quando parlavo di "convertire" intendevo questo, non in ogni singolo passaggio ...
Cordialmente, Alex
@axpgn: L'input/output è una delle operazioni più lente che uno possa immaginare. Tra l'altro la conversione in decimale trasforma in una successione di char non troppo comodi da usare (tanto per cominciare '0' non ha valore 0 se convertito in intero). Inoltre è terribilmente inefficiente in termini di spazio. In due interi a 64 bit puoi rappresentare \(\displaystyle 2^{128} \) numeri diversi, mentre con 16 char puoi rappresentare solo \(\displaystyle 10^{16} \) numeri che è meno di ciò che puoi rappresentare con un singolo intero a 64bit. Dei 256 possibili valori di un char, 246 non sarebbero usati!
Nota infine che il tuo algoritmo è mal definito, perché usi generalmente la divisione e l'operazione di resto per cambiare base (o alternativamente l'elevamento a potenza e la sottrazione). Insomma paradossalmente vuoi implementare una divisione, richiedendo di fare un numero di divisioni pari alla somma dei logaritmi dei due numeri in base 10.
Nota infine che il tuo algoritmo è mal definito, perché usi generalmente la divisione e l'operazione di resto per cambiare base (o alternativamente l'elevamento a potenza e la sottrazione). Insomma paradossalmente vuoi implementare una divisione, richiedendo di fare un numero di divisioni pari alla somma dei logaritmi dei due numeri in base 10.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo