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
Premesso che ho detto fin dall'inizio che esistono librerie specifiche per la gestione di numeri "grandi" e che i modi in cui sono "gestiti" i numeri all'interno di un computer permettono operazioni che non conosco e algoritmi sicuramente più efficienti di quelli che ho usato, ho voluto semplicemente mostrare che è possibile fare calcoli di questo tipo senza particolari "costruzioni"; non mi pare di aver scritto che fosse un metodo particolarmente efficiente (solo efficace).
Quello che non capisco è cosa c'entri l'input, se voglio elaborare un numero dovrò prima o poi comunicarlo al computer e se è così grande che il linguaggio/sistema che sto usando non é in grado di "memorizzarlo" come numero, dovrà "piazzarlo" da qualche parte e poi "elaborarlo" per renderlo "usabile" cioè trasformarlo in numeri accettabili dal sistema, no? Non ho detto che lavoro con i char dall'inizio alla fine, anzi ...
Quello che non capisco è cosa c'entri l'input, se voglio elaborare un numero dovrò prima o poi comunicarlo al computer e se è così grande che il linguaggio/sistema che sto usando non é in grado di "memorizzarlo" come numero, dovrà "piazzarlo" da qualche parte e poi "elaborarlo" per renderlo "usabile" cioè trasformarlo in numeri accettabili dal sistema, no? Non ho detto che lavoro con i char dall'inizio alla fine, anzi ...
scusate se non vi ho potuto rispondere prima ma il lavoro non mi ha dato tempo.
comunque
x apatriarca
quello che dici sulla dimensione delle cifre a 32 o 64 bit e ovvio
per quanto riguarda
evidentemente chi ha usato queste idee non è riuscito a trovarne di migliori.
siccome il costo non è poi cosi esoso e le prestazioni sono buone le hanno implementate.
se non si percorressero nuove strade a quest'ora saremmo ancora nelle caverne!
i numeri nella mia classe hanno 2 modi di rappresentazione
1) modo normale vengono rappresentate le cifre da 0 a 9 2 cifre per ogni byte
2) modo compresso vengono rappresentate le cifre da 0 a Z (compressione massima) 1 cifra per ogni byte naturalmente il fattore di compressione e scelto dall' utente.
come dimensioni massime avremo per la modalità normale 512 cifre
mentre nella modalità compressa avremo 9180 cifre ma come dicevo prima ciò dipende dalla fattore di compressione utilizzato.
nelle mie intenzioni c'è l'idea di proggettare una classe che non faccia differenza tra numeri normali,interi, e numeri con virgola,float e double, come in realtà si riscontra in molte librerie e nel sistema stesso.
per quanto riguarda le mie competenze in informatica sono molto molto bravo mentre in matematica sono un pò carente.
comunque
x apatriarca
quello che dici sulla dimensione delle cifre a 32 o 64 bit e ovvio
per quanto riguarda
"apatriarca":
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.
evidentemente chi ha usato queste idee non è riuscito a trovarne di migliori.
siccome il costo non è poi cosi esoso e le prestazioni sono buone le hanno implementate.
se non si percorressero nuove strade a quest'ora saremmo ancora nelle caverne!
i numeri nella mia classe hanno 2 modi di rappresentazione
1) modo normale vengono rappresentate le cifre da 0 a 9 2 cifre per ogni byte
2) modo compresso vengono rappresentate le cifre da 0 a Z (compressione massima) 1 cifra per ogni byte naturalmente il fattore di compressione e scelto dall' utente.
come dimensioni massime avremo per la modalità normale 512 cifre
mentre nella modalità compressa avremo 9180 cifre ma come dicevo prima ciò dipende dalla fattore di compressione utilizzato.
nelle mie intenzioni c'è l'idea di proggettare una classe che non faccia differenza tra numeri normali,interi, e numeri con virgola,float e double, come in realtà si riscontra in molte librerie e nel sistema stesso.
per quanto riguarda le mie competenze in informatica sono molto molto bravo mentre in matematica sono un pò carente.
Affermare che "chi ha usato queste idee non è riuscito a trovarne di migliori," è incredibilmente irrispettoso per le persone che hanno scritto tali librerie e che al contrario di te hanno passato gran parte della loro vita a lavorare a nuove idee e algoritmi per il calcolo efficiente di numeri di grandi dimensioni. E non stiamo parlando di 9180 cifre decimali.. Stiamo potenzialmente parlando di milioni di cifre. In effetti non esiste alcun limite al numero di cifre che tali librerie supportano in modo MOLTO efficiente.
Ci sono due grossi difetti nel tuo ragionamento. Prima di tutto dai per scontato che le cifre siano introdotte e stampate come stringhe. Potrebbe essere vero ma normalmente non è così. Potrebbero anche essere calcolati. Per esempio potresti decidere di voler calcolare una grossa potenza di un numero o calcolare pi greco con una certa precisione. Nessuno di questi due casi richiede di passare valori da una stringa. La tua notazione diventa in questi casi MOLTO scomoda in effetti. Lo stesso discorso vale per la stampa dei valori come stringhe. Non è affatto detto che questo sia richiesto. Potresti anche semplicemente stampare il valore in esadecimale e per questo genere di rappresentazione la tua notazione è più scomoda di usare dei normali interi a 32 bit. Un altro problema è quello di supporre che la conversione avvenga più spesso delle altre operazioni. Di fatto sarà molto probabilmente vero il contrario. La conversione verrà probabilmente fatta una singola volta e le operazioni saranno potenzialmente tantissime.
Venendo poi ai tempi di calcolo. Supponiamo di voler fare una semplice somma. Nel caso di cifre a 32 bit devi semplicemente fare un ciclo in cui sommi le due cifre, vedi se c'è stato un overflow e in tal caso passi il bit alla fase successiva. In assembly è praticamente immediato e molto veloce. Nel tuo caso non è così semplice e sarà sicuramente meno efficiente. E stiamo parlando dell'operazione più veloce di tutti.. Nel caso di prodotto e divisione il vantaggio in termini di performance sarà ancora maggiore. Venendo poi al discorso dell'occupazione di memoria. Nel tuo caso hai che un numero \(N\) occuperà \( \log_{100}(N) \) bytes nel caso della rappresentazione non compressa e \( \log_{36}(N) \) bytes nel caso compresso (non mi è chiaro perché ritieni che tale rappresentazione sia più efficiente in effetti.. ma forse ho capito male come hai rappresentato tale numeri). Nel caso di rappresentazione con cifre a 32 bit hai invece \( \log_{256}(N) \) bytes..
Ho dubbi anche sul tuo obiettivo finale. Perché fare una classe che non distingue tra tipi numerici? Suppongo tu voglia passare in modo automatico da una rappresentazione ad un altra con facilità, ma per le migliori performance è spesso importante conoscere il tipo.
Ci sono due grossi difetti nel tuo ragionamento. Prima di tutto dai per scontato che le cifre siano introdotte e stampate come stringhe. Potrebbe essere vero ma normalmente non è così. Potrebbero anche essere calcolati. Per esempio potresti decidere di voler calcolare una grossa potenza di un numero o calcolare pi greco con una certa precisione. Nessuno di questi due casi richiede di passare valori da una stringa. La tua notazione diventa in questi casi MOLTO scomoda in effetti. Lo stesso discorso vale per la stampa dei valori come stringhe. Non è affatto detto che questo sia richiesto. Potresti anche semplicemente stampare il valore in esadecimale e per questo genere di rappresentazione la tua notazione è più scomoda di usare dei normali interi a 32 bit. Un altro problema è quello di supporre che la conversione avvenga più spesso delle altre operazioni. Di fatto sarà molto probabilmente vero il contrario. La conversione verrà probabilmente fatta una singola volta e le operazioni saranno potenzialmente tantissime.
Venendo poi ai tempi di calcolo. Supponiamo di voler fare una semplice somma. Nel caso di cifre a 32 bit devi semplicemente fare un ciclo in cui sommi le due cifre, vedi se c'è stato un overflow e in tal caso passi il bit alla fase successiva. In assembly è praticamente immediato e molto veloce. Nel tuo caso non è così semplice e sarà sicuramente meno efficiente. E stiamo parlando dell'operazione più veloce di tutti.. Nel caso di prodotto e divisione il vantaggio in termini di performance sarà ancora maggiore. Venendo poi al discorso dell'occupazione di memoria. Nel tuo caso hai che un numero \(N\) occuperà \( \log_{100}(N) \) bytes nel caso della rappresentazione non compressa e \( \log_{36}(N) \) bytes nel caso compresso (non mi è chiaro perché ritieni che tale rappresentazione sia più efficiente in effetti.. ma forse ho capito male come hai rappresentato tale numeri). Nel caso di rappresentazione con cifre a 32 bit hai invece \( \log_{256}(N) \) bytes..
Ho dubbi anche sul tuo obiettivo finale. Perché fare una classe che non distingue tra tipi numerici? Suppongo tu voglia passare in modo automatico da una rappresentazione ad un altra con facilità, ma per le migliori performance è spesso importante conoscere il tipo.
"apatriarca":non volevo mancare di rispetto a nessuno volevo semplicemente dire che una volta trovata la soluzione ad un problema o per tempo o per voglia non si vanno a trovare soluzioni alternative che magari potrebbero essere più efficienti.
Affermare che "chi ha usato queste idee non è riuscito a trovarne di migliori," è incredibilmente irrispettoso per le persone che hanno scritto tali librerie e che al contrario di te hanno passato gran parte della loro vita a lavorare a nuove idee e algoritmi per il calcolo efficiente di numeri di grandi dimensioni. E non stiamo parlando di 9180 cifre decimali.. Stiamo potenzialmente parlando di milioni di cifre. In effetti non esiste alcun limite al numero di cifre che tali librerie supportano in modo MOLTO efficiente.
comunque le 9180 cifre non sono decimali ma in base 36!
"apatriarca":
Ci sono due grossi difetti nel tuo ragionamento. Prima di tutto dai per scontato che le cifre siano introdotte e stampate come stringhe. Potrebbe essere vero ma normalmente non è così. Potrebbero anche essere calcolati.
è normale che le cifre vengano calcolate e non solo stampate o inserite da stringa.
Semplicemente è più semplice esporre un problema limitandosi hai casi più semplici.
"apatriarca":
il valore in esadecimale e per questo genere di rappresentazione la tua notazione è più scomoda di usare dei normali interi a 32 bit.
hai ragione ma essa mi permette due vantaggi non da poco rispetto alla notazione scentifica che viene normalmente usata per immagazinare i numeri sia dal sistema che in molte librerie.
abbassamento del valore di errore in fase di calcolo specialmente con i float.
permette la gestione con un unico campo sia degli interi che dei float.
"apatriarca":
Venendo poi ai tempi di calcolo. Supponiamo di voler fare una semplice somma. Nel caso di cifre a 32 bit devi semplicemente fare un ciclo in cui sommi le due cifre, vedi se c'è stato un overflow e in tal caso passi il bit alla fase successiva. In assembly è praticamente immediato e molto veloce.
anche con la mia metodologia e la stessa cosa già fatto e testato.
"apatriarca":
Nel caso di prodotto e divisione il vantaggio in termini di performance sarà ancora maggiore
per la moltiplicazione basterà scegliere l'algortmo più consono.
per la divisione sono d'accordo con te ma non mi vengono altre idee in mente. al di fuori di quelle, gentilmente, suggeritemi da questo forum.
"apatriarca":
Ho dubbi anche sul tuo obiettivo finale. Perché fare una classe che non distingue tra tipi numerici? Suppongo tu voglia passare in modo automatico da una rappresentazione ad un altra con facilità, ma per le migliori performance è spesso importante conoscere il tipo.
perchè, a parte il lato accademico, non ha molto senso fare cose che hanno già fatto in molti e molto spesso utilizzando le stesse metodologie.
purtroppo solo la visione dell'insieme potrà farmi rendere conto della gravità degli svantaggi che ci saranno.
cercherò di colmarli nelle release successive.
"smalldragon":
non volevo mancare di rispetto a nessuno volevo semplicemente dire che una volta trovata la soluzione ad un problema o per tempo o per voglia non si vanno a trovare soluzioni alternative che magari potrebbero essere più efficienti.
comunque le 9180 cifre non sono decimali ma in base 36!
Si cerca continuamente di trovare nuove soluzioni a problemi già risolti e a migliorare le implementazioni esistenti. L'ultima versione stabile di GMP è stata rilasciata ad esempio questa estate ed è un progetto che va avanti dal 1991. Parlando di divisione quello che segue è un esempio di quello a cui stanno lavorando al momento:
Division m,n
Implement van der Hoeven's MU generalisation.
Perfect algorithm selection for nn-limb by dn-limb division.
Add pi/preinv variants for all mu functions. [2h]
We still use mpn_tdiv_qr or even mpn_divrem in many files. Replace by current division functions:
mpn mpz mpf
generic/divrem.c jacobi.c get_str.c
generic/gcd.c powm.c set_q.c
generic/gcd_subdiv_step.c set_str.c
generic/gcdext.c tdiv_qr.c ui_div.c
generic/get_str.c tdiv_r.c
generic/powm.c
These files also use mpn_tdiv_qr, but just for nails:
mpz/cdiv_q_ui.c mpz/cdiv_qr_ui.c mpz/cdiv_r_ui.c mpz/cdiv_ui.c mpz/fdiv_q_ui.c mpz/fdiv_qr_ui.c mpz/fdiv_r_ui.c mpz/fdiv_ui.c mpz/tdiv_q_ui.c mpz/tdiv_qr_ui.c mpz/tdiv_r_ui.c mpz/tdiv_ui.c
All'interno di questa libreria sono supportati diversi algoritmi per ogni operazione tra cui scegliere. Non mi sembra quindi che ci si sia accontentati del primo algoritmo che si è trovato. C'è invece un continuo miglioramento e una continua ricerca.
"smalldragon":
è normale che le cifre vengano calcolate e non solo stampate o inserite da stringa.
Semplicemente è più semplice esporre un problema limitandosi hai casi più semplici.
E' normale usare tali casi come esempi e casi di test, ma è importante ricordarsi che esiste altro per non basare il design del programma interamente su questi casi giocattolo.
"smalldragon":
hai ragione ma essa mi permette due vantaggi non da poco rispetto alla notazione scentifica che viene normalmente usata per immagazinare i numeri sia dal sistema che in molte librerie.
abbassamento del valore di errore in fase di calcolo specialmente con i float.
permette la gestione con un unico campo sia degli interi che dei float.
Non sono sicuro di aver seguito il tuo ragionamento. E' ovvio che se la tua libreria supporta i numeri con precisione arbitraria avrà una maggiore precisione rispetto ai float. Tuttavia il confronto andrebbe più che altro fatto rispetto a librerie con funzionalità simili (come MPFR rimanendo in ambiente GNU).
"smalldragon":
anche con la mia metodologia e la stessa cosa già fatto e testato.
L'idea di base è la stessa in ogni base ma l'implementazione è necessariamente più complicata se i byte possono contenere anche valori non validi.
"smalldragon":
perchè, a parte il lato accademico, non ha molto senso fare cose che hanno già fatto in molti e molto spesso utilizzando le stesse metodologie.
purtroppo solo la visione dell'insieme potrà farmi rendere conto della gravità degli svantaggi che ci saranno.
cercherò di colmarli nelle release successive.
Sei ovviamente libero di implementare queste funzionalità come desideri. Non ho però compreso un paio di cose:
1. Perché parli di versione compressa e versione normale, quando quella compressa è meno compatta di quella normale? In quella normale memorizzi due cifre decimali per ogni byte e quindi avrai 100 valori possibili. Nel caso della versione compressa memorizzi solo 36 valori per ogni byte. Inoltre la versione compressa così pensata mi sembra più complicata da gestire e comprendere. Una versione compressa potrebbe piuttosto usare la base 16 e quindi avere 256 valori per ogni byte.
2. Utilizzi sempre questa notazione o a seconda della situazione passi da una notazione ad un altra?
"smalldragon":
1. Perché parli di versione compressa e versione normale, quando quella compressa è meno compatta di quella normale? In quella normale memorizzi due cifre decimali per ogni byte e quindi avrai 100 valori possibili. Nel caso della versione compressa memorizzi solo 36 valori per ogni byte. Inoltre la versione compressa così pensata mi sembra più complicata da gestire e comprendere. Una versione compressa potrebbe piuttosto usare la base 16 e quindi avere 256 valori per ogni byte.
non è vero che la versione compressa e meno compatta della normale
per esempio : nella versione normale il numero 108
viene menorizzato in 2 byte perchè viene memorizzato come 01 08
mentre nella versione compatta col massimo valore viene memorizzato come 30
la versione compressa normalmente serve per memorizzare i dati su file ed conveniente quando si opera su grandi numeri.
inoltre la versione compressa offre anche un modo semplice per cifrare i dati.
comunque il valore di compressione e a scelta dell'utilizzatore.
"smalldragon":
2. Utilizzi sempre questa notazione o a seconda della situazione passi da una notazione ad un altra?
come dicevo sopra lascio libera scelta all'utilizzatore anche se consiglio di utilizzare la modalità compressa solo per memorizzare i dati su file perchè i calcoli in modalità compressa, giustamente e a prescindere dagli algoritmi che utilizzero, sarebbero molto più lenti della modalità normale.
Continuo a non vedere i vantaggi. Hai scritto quattro cifre invece di due, ma in entrambi i casi hai 2 byte.. Se invece pendii qualcosa come 99 hai un solo byte nella versione non compressa e 2 in quella compressa.
più e grande il numero + si vedono i vantaggi ed in fondo sarà una classe per gestire grandi numeri.
anche se il più delle volte sarà usata per gestire numeri normali.
comunque per ovviare a questo problema farò in maniera tale che se la compressione non conviene non sarà effettuata.
grazie per l'aiuto che mi hai dato spero di fare un buon lavoro.
anche se il più delle volte sarà usata per gestire numeri normali.
comunque per ovviare a questo problema farò in maniera tale che se la compressione non conviene non sarà effettuata.
grazie per l'aiuto che mi hai dato spero di fare un buon lavoro.
Come ti ho già detto.. Non conviene mai. In un caso hai 100 simboli per byte e nell'altro solo 36..
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo