[C++] BigInteger
Quanto tempo è passato, il mio ultimo post risale al 6 Agosto del 2009. 
Ok, mettiamo da parte la nostalgia e veniamo a noi.
Sono qui per chiedervi un consiglio, vorrei scrivere in C++ una libreria per la gestione di interi di lunghezza arbitraria e vorrei quindi implementare quante più operazioni possibili, oltre alle ovvie (somma, sottrazione, moltiplicazione, divisione, ...) citerei le potenze, gli operatori di bitwise, lo shift, gli operatori di stream e quant'altro.
La domanda è, voi, che struttura utilizzereste per rappresentare questo intero?
La cosa più banale che può venire in mente, è quella di utilizzare un vettore dinamico di caratteri e memorizzare ogni cifra dell'intero come un carattere, con questo (stupido) sistema, però, molte operazioni diventano impraticabili.
Mi piacerebbe discuterne con voi e ascoltare i vostri consigli.
Ok, mettiamo da parte la nostalgia e veniamo a noi.
Sono qui per chiedervi un consiglio, vorrei scrivere in C++ una libreria per la gestione di interi di lunghezza arbitraria e vorrei quindi implementare quante più operazioni possibili, oltre alle ovvie (somma, sottrazione, moltiplicazione, divisione, ...) citerei le potenze, gli operatori di bitwise, lo shift, gli operatori di stream e quant'altro.
La domanda è, voi, che struttura utilizzereste per rappresentare questo intero?
La cosa più banale che può venire in mente, è quella di utilizzare un vettore dinamico di caratteri e memorizzare ogni cifra dell'intero come un carattere, con questo (stupido) sistema, però, molte operazioni diventano impraticabili.
Mi piacerebbe discuterne con voi e ascoltare i vostri consigli.
Risposte
Probabilmente utilizzerei un array dinamico di interi senza segno. Il numero sarebbe in questo modo rappresentata in base $2^n$ dove $n$ è la dimensione di ogni singola "cifra". Quando si lavora con un computer è molto più comodo lavorare in binario.
Ma quando ho bisogno di qualcosa di questo tipo faccio normalmente ricorso a GMP oppure uso un linguaggio diverso dal C++.
Ma quando ho bisogno di qualcosa di questo tipo faccio normalmente ricorso a GMP oppure uso un linguaggio diverso dal C++.
Ciao,
tempo fà, per un progetto universitario, ebbi la necessità di pensare ad un sistema per manipolare input di grandi numeri, oltre i "ridicoli" long long int del C.
La manipolazione doveva essere per ogni cifra, perciò dovetti un attimo accantonare l'idea di usare la rappresentazione primitiva di intero. Usai dei vettori di char con allocati dinamicamente 100000000 di cifre (non mi interi, ma char), cosa ovviamente inutile, perchè se si conosce come funziona la memoria non si allocano cose del genere. Ma per il progetto andava bene.
Ma tornarnando alla prima idea che ebbi, cioè usare gli interi primitivi, pensai di usare come massima rappresentazione i long long int (sistema 64 bit, è da contare anch quello), e di utilizzare una struttura ad albero per rappresentare la posizione decimale. O usare dei vettori di longlong int.
Puntai sulla seconda ipotesi, e scrissi anche qualcosa per riuscire a fare delle operazioni, e usare il numero completo dell'intero vettore.
da considerare tutti i problemi di memoria principale e secondaria, ma era una cosa così senza essere formali, tanto era per un progettino, nulla più. Se ti può essere utile posso incollarti qua i vari pezzi di codice e commenti che scrissi.
Ma essendo che te cerchi qualcosa di efficente, e corretto, è meglio pensare bene e fare un'analisi (matematicamente) seria. ci sono molti fattori da tenere conto, dalle strutture dati (alberi, merge-find, heap,....) agli algoritmi.
Se è di un qualcosa di serie meglio pensarci a mente fresca, la mia era solo un riproporre di un qualcosa di già pensato, ma non seriamente
tempo fà, per un progetto universitario, ebbi la necessità di pensare ad un sistema per manipolare input di grandi numeri, oltre i "ridicoli" long long int del C.
La manipolazione doveva essere per ogni cifra, perciò dovetti un attimo accantonare l'idea di usare la rappresentazione primitiva di intero. Usai dei vettori di char con allocati dinamicamente 100000000 di cifre (non mi interi, ma char), cosa ovviamente inutile, perchè se si conosce come funziona la memoria non si allocano cose del genere. Ma per il progetto andava bene.
Ma tornarnando alla prima idea che ebbi, cioè usare gli interi primitivi, pensai di usare come massima rappresentazione i long long int (sistema 64 bit, è da contare anch quello), e di utilizzare una struttura ad albero per rappresentare la posizione decimale. O usare dei vettori di longlong int.
Puntai sulla seconda ipotesi, e scrissi anche qualcosa per riuscire a fare delle operazioni, e usare il numero completo dell'intero vettore.
da considerare tutti i problemi di memoria principale e secondaria, ma era una cosa così senza essere formali, tanto era per un progettino, nulla più. Se ti può essere utile posso incollarti qua i vari pezzi di codice e commenti che scrissi.
Ma essendo che te cerchi qualcosa di efficente, e corretto, è meglio pensare bene e fare un'analisi (matematicamente) seria. ci sono molti fattori da tenere conto, dalle strutture dati (alberi, merge-find, heap,....) agli algoritmi.
Se è di un qualcosa di serie meglio pensarci a mente fresca, la mia era solo un riproporre di un qualcosa di già pensato, ma non seriamente
"apatriarca":
Probabilmente utilizzerei un array dinamico di interi senza segno. Il numero sarebbe in questo modo rappresentata in base $2^n$ dove $n$ è la dimensione di ogni singola "cifra". Quando si lavora con un computer è molto più comodo lavorare in binario.
Potresti spiegarmi meglio la frase che ho evidenziato in grassetto?
"apatriarca":
Ma quando ho bisogno di qualcosa di questo tipo faccio normalmente ricorso a GMP oppure uso un linguaggio diverso dal C++.
Vero, ci sono diverse librerie in circolazione, però in questo specifico caso devo e voglio scrivermi qualcosa io.
Che poi, vorrei arrivare a qualcosa di non complesso ma comunque con delle performance decenti.
"ham_burst":
Ciao,
tempo fà, per un progetto universitario, ebbi la necessità di pensare ad un sistema per manipolare input di grandi numeri, oltre i "ridicoli" long long int del C.
La manipolazione doveva essere per ogni cifra, perciò dovetti un attimo accantonare l'idea di usare la rappresentazione primitiva di intero. Usai dei vettori di char con allocati dinamicamente 100000000 di cifre (non mi interi, ma char), cosa ovviamente inutile, perchè se si conosce come funziona la memoria non si allocano cose del genere. Ma per il progetto andava bene.
E' la prima semplice rappresentazione che può venire in mente, ma credo che poi implementare certe operazioni sia impossibile o comunque un bagno di sangue.
"ham_burst":
Ma essendo che te cerchi qualcosa di efficente, e corretto, è meglio pensare bene e fare un'analisi (matematicamente) seria. ci sono molti fattori da tenere conto, dalle strutture dati (alberi, merge-find, heap,....) agli algoritmi.
Se è di un qualcosa di serie meglio pensarci a mente fresca, la mia era solo un riproporre di un qualcosa di già pensato, ma non seriamente
No aspetta, cerco qualcosa di corretto si ma non "efficiente". Come dicevo sopra, non cerco qualcosa di complesso e non ho bisogno di performance eccezionali. Insomma alla fine è un'esercizio che vorrei fare, seguendo la metodologia dell extreme programming.
Perciò strutture come alberi o altro mi sanno di qualcosa di troppo complicato, per il mio fine.
Voglio prima di tutto evidenziare che non mi sono mai messo seriamente a sviluppare una libreria di questo tipo. Queste sono quindi più che altro considerazioni personali e non sono frutto di esperienza diretta.
In ogni caso, con la frase che hai evidenziato in grassetto volevo dire che un vettore V di interi a $n$ bit di una certa lunghezza $L$ può essere interpretato come il numero:
$C = \sum_{i=0}^L V * 2^{n * i}$.
Ogni intero è quindi come una cifra del tuo numero e le operazioni possono essere svolte su queste cifre come faresti con le "normali" cifre decimali.
L'allocazione della memoria credo sia abbastanza critica per ottenere performance ottimali (insieme alla scelta degli algoritmi da usare ovviamente), ma non è comunque secondo me necessario che tutto il numero sia allocato in modo contiguo per ottenere buone performance. Se dovessi scrivere una libreria di questo tipo, probabilmente allocherei il numero in blocchi di dimensione fissa (una qualche dimensione ottimale per la piattaforma scelta) facendo ricorso ad un memory pool per ottimizzare l'allocazione della memoria. Una cosa sulla quale è bene fare molta attenzione in ogni caso in una libreria di questo tipo in C++ è la creazione di copie temporanee. Potrebbe essere comodo far ricorso ad un meccanismo di copia di tipo copy-on-write per ridurre questo problema.
Nota comunque che GMP non usa questo genere di accorgimenti e l'allocazione della memoria è comunque molto più naïve, anche se è possibile utilizzare degli allocatori personalizzati.
In ogni caso, con la frase che hai evidenziato in grassetto volevo dire che un vettore V di interi a $n$ bit di una certa lunghezza $L$ può essere interpretato come il numero:
$C = \sum_{i=0}^L V * 2^{n * i}$.
Ogni intero è quindi come una cifra del tuo numero e le operazioni possono essere svolte su queste cifre come faresti con le "normali" cifre decimali.
L'allocazione della memoria credo sia abbastanza critica per ottenere performance ottimali (insieme alla scelta degli algoritmi da usare ovviamente), ma non è comunque secondo me necessario che tutto il numero sia allocato in modo contiguo per ottenere buone performance. Se dovessi scrivere una libreria di questo tipo, probabilmente allocherei il numero in blocchi di dimensione fissa (una qualche dimensione ottimale per la piattaforma scelta) facendo ricorso ad un memory pool per ottimizzare l'allocazione della memoria. Una cosa sulla quale è bene fare molta attenzione in ogni caso in una libreria di questo tipo in C++ è la creazione di copie temporanee. Potrebbe essere comodo far ricorso ad un meccanismo di copia di tipo copy-on-write per ridurre questo problema.
Nota comunque che GMP non usa questo genere di accorgimenti e l'allocazione della memoria è comunque molto più naïve, anche se è possibile utilizzare degli allocatori personalizzati.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo