Newsgroup: it.comp.lang.c++
Titolo: Classi C++ per gestire interi a lunghezza infinita.

Vorrei poter gestire un tipo di dato intero però a lunghezza non fissa.
Vorrei anche (ovviamente) poter fare le varie operazioni aritmetiche.
C'è qualcosa già fatto nella libreria standard del C++ (uso Visual C++ 6.0)
oppure posso trovare qualche sorgente in rete.
Se non è disponibile niente di già fatto, è reperibile della documentazione
(quale rappresentazione interna è la migliore, algoritmi per risolvere le
operazioni matematiche, ecc....) così da poter realizzare la classe ?
Grazie per l'attenzione.
Porlock.

operazioni matematiche, ecc....) cosě da poter realizzare la classe ?
Io per divertimento ho scritto un programmino che calcola il
fattoriale di un numero arbitrario... ad esempio ho potuto
calcolare che il fattoriale di 6502 e' composto da 21971 cifre.
La rappresentazione che ho usato mantiene il numero in base
100000 memorizzandone le cifre in un std::vector<long>.
Io ho implementato solo la moltiplicazione ma anche le
altre operazioni non dovrebbero essere un problema.
L'uso della base 100000 semplifica notevolmente la stampa
del numero in decimale.
HTH
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

 calcolare che il fattoriale di 6502 e' composto da 21971 cifre.
                                   ^
                               Fissato! :-)
Ciao,
Nicola

 calcolare che il fattoriale di 6502 e' composto da 21971 cifre.
Se uno vuole *solo* sapere il numero di cifre di cui è composto
un fattoriale può semplicemente fare:
#include <math>
unsigned long fact(unsigned long x, double& f)
{
   double logfact = 0;
   while(x > 1) { logfact += std::log10(x--); }
   // calcola la parte intera di logfact
   unsigned long n = logfact;
   // fact(x) = 10 ^ n * 10 ^ (logfact - n)
   f = std::pow(10, logfact - n);
   return n;
}
#include <iostream>
int main()
{
   int x = 6502;
   double f;
   unsigned long n = fact(x, f);
   std::cout.precision(32);
   std::cout << x << "! = " << f << " 10 ^ " << n << '\n';
}
L'output è:
6502! = 9.0004685575361556 10 ^ 21970
Comunque, rispondendo a Porlock, per gestire numeri a precisione
non fissa è disponibile la libreria GNU GMP.
E' una serie di API scritte in C.
Non dovrebbe essere troppo difficile scrivere una classe
che usi tali funzioni.
Nella libreria libgpp è disponibile una classe Integer, purtroppo
tale libreria non è più supportata.
Manlio Perillo

 wrote in message
39fc3d95...@news.interbusiness.it...

La tua idea di utilizzare un std::vector<long> e di mantenere il numero in
base 100000 mi sembra interessante e decisamente buona.
Potresti mandarmi i sorgenti, te ne sarei veramente grato.
Porlock.

6502! = 9.0004685575361556 10 ^ 21970
Bella l'idea del fattoriale fatto con i logaritmi... non mi era
mai venuto in mente. Comunque non esagererei troppo con la
precision() ... la decima cifra e' gia' sbagliata.


Potresti mandarmi i sorgenti, te ne sarei veramente grato.
La funzione principale e' la Normalize() che prende il numero
e cifra per cifra riduce a 0..100000 con riporto.
  void BigNum::Normalize()
  {
    long carry=0;
    int i,n=d.size();
    for (i=0; i<n; i++)
    {
      d[i]+=carry;
      carry=d[i]/100000;
      d[i]-=carry*100000;
    }
    if (carry)
      d.push_back(carry);
  }
Per moltiplicare numero per un long basta
moltiplicare tutte le cifre e poi chiamare la
funzione Normalize().
Nota che 100000 mi sembra una base un po' troppo
alta per essere valida nel caso generale.
Il problema e' che 100000*100000 non ci sta in
un long (se si hanno long a 32 bit).


 [snip]
perche' usare numeri cosi' strani (potenze di 10)?  se usi potenze di
due puoi fare tutto con >> e & , immagino, e guadagni in velocita'...
-- 
Maurizio Loreti                         
http://www.pd.infn.it/~loreti/mlo.html
Univ. of Padova, Dept. of Physics - Padova, Italy            
lor...@pd.infn.it
Murphy's law: "Anything that can go wr
/bin/fortune: segmentation fault - core dumped


Il problema è che voglio sia usata la massima precisione possibile.
Siccome non 'sapevo' quanto fosse (ad esempio uno potrebbe compilare
il programma su un computer a 128 bit) ho messo un valore 'elevato'.
Ho scritto sapevo al passato perchè mi sono accorto che basta fare:
int digits = numeric_limits<double>::digits10;
cout.precision(digits);
Riguardo alla perdita di precisione, è una cosa normale.
Sarebbe interessante poter stimare l'errore...
Manlio Perillo

 due puoi fare tutto con >> e & , immagino, e guadagni in velocita'...
Io ho scritto la classe BigNum per rispondere ad un post di una
persona che, probabilmente non sapendo contare, suggeriva come
sistema ragionevole di mischiare un mazzo di carte il chiamare
un numero casuale "ma sufficientemente grande" di volte
std::next_permutation(). Giusto per fare lo spiritoso ho voluto
mostrargli quanto valesse 52! (con tutte le cifre esatte).
Se avessi rappresentato un BigNum usando come base una potenza
di due il codice di calcolo si sarebbe velocizzato, ma il codice
per la stampa delle cifre (decimali) si sarebbe come capirai
complicato notevolmente e sarebbe stato molto piu' lento
(per stampare devi fare delle operazioni di divisione sul BigNum).
Penso che quale si la rappresentazione dipenda anche
dall'utilizzo. Se si devono ad esempio fare quasi sempre
solo somme, moltiplicazioni per numeri "piccoli" e stampe
(ad esempio un programma di calcoli in valuta) credo che un
approccio base 10^n sia preferibile (una specie di ibrido
di rappresentazione binaria/BCD).
Andrea
--
----------------------------------------------------------------
 <\___/>  Andrea        email: agriff at tin dot it
 / . . \  "6502"          irc: _6502_@EFNET#italia
(  (")  ) Griffini   homepage: 
http://www.netservers.com/~agriff
Sent via Deja.com 
http://www.deja.com/
Before you buy.


Una buona base è 256 (oppure meglio 65536).
Solo che poi ti tocca convertire in base 10 per la
visualizzazione.
Su Numerical Recipes c'è un capitoletto che spiega come
costruire numeri a precisione multipla.
Manlio Perillo