divisione tra grandi numeri primi

[smalldragon]

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

[Raptorista]

La domanda è come fare la divisione tra numeri che non sono uno multiplo dell'altro?

[smalldragon]

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.

[Raptorista]

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 [=std::vector] 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.

[Super Squirrel]

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?

[smalldragon]

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.

[smalldragon]

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!

[apatriarca]

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.

[smalldragon]

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!

[apatriarca]

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).