Newsgroup: it.comp.lang.c
Titolo: Gestire Numeri con 100+ Cifre

Salve a tutti, vorrei implementare una libreria che mi consenta di gestire
numeri con 100+ cifre e che mi permetta di fare le 4 operazioni di base
(+-*/)
Mi servirebbe avere un'idea dell' implementazione piu' semplice possibile,
eventualmente poi pensero' ad ottimizzare il tutto.
I src che ho trovato in giro sono ovviamente gia' tutti ottimizzati e ci
metterei una vita per cercare di capire il ragionamento che sta alla base
del tutto.
Qualcuno ha esperienza in merito???
Ciau, Il.Socio

 wrote

Ti riferisci ad interi, vero?
Il modo piu' carino per farlo e' usare il C++ che consente di fare
l'overloading degli operatori a cui ti riferisci.
Tuattavia, finezze a parte, il processo in C e' lo stesso (ma devi chiamare
delle funzioni, ad esempio (My100digits_ADD())).
In entrambi i casi, il modo piu' banale e semplice e' quello di fare le
operazioni come ti insegnano a scuola ed In base 10.
il numero 5890 ad esempio raffiguralo come 4 elementi in un array di char o
int.
[3] [2] [1] [0]
 5    8    9   0
Nella riga in alto vedi gli indici, in quella in basso il loro contenuto:
poi se vuoi sommare 5890 a 351 fai:
5  8  9  0    +
    3  5  1    =
ora da sinistra a destra incominci:
0+1=1, poi 9+5=14, scrivo 4 e riporto 1. 8+3+riporto=12 scrivo 2 e riporto
1.
5+0+riporto=6.
risultato 6241. La funzione restituira' un array che contiene i numeri
0,0,.....6,2,4,1. (con std::vector e' piu' comodo!)
Occhio ai segni, devi anche (nella struttura) segnarti se il numero e' pos o
neg, e comportarti di conseguenza.
La moltiplicazione segue lo stesso principio ma e' piu' complicata. Hai
bisogno di array di appoggio.
etc... come ti hanno insegnato a scuola.
Un modo piu' appropriato (spreca molti meno bytes!!!) e' quello di lavorare
bit a bit (come i tipi base int, char etc...), ma visto che non sai come
partire credo tu debba tenerlo come secondo esercizio!
Io anni fa implementai una cosa simile (ma con numeri di (teoricamente)
infinite cifre) in C++ con overloading etc...
Ecco un esempio:
<CODE>
#include<iostream>
#include"CInfInt.h"
using namespace std;
void Scompo(CInfInt n);
int main()
{
    CInfInt n;
    cout << "Tommy HUGE scomposizione:" << endl;
    cout << "Numero da scomporre:" << endl;
    n="65296612059791253540377962630220163144009";
    cout << n << " (numero di " << n.GetRealSize() << " cifre)" << endl <<
endl;
    Scompo(n);
    cout << "Scomposizione completata, grazie !" << endl;
    return 0;
}
void Scompo(CInfInt n)
{
    CInfInt tmp;
    CInfInt i=3;
    while(!(n%2)){
        cout << "+2 ";
        n/=2;
    }
    tmp=n.Sqrt();
    while(tmp>=i){
        if(!(n%i)){
            cout << i << " ";
            n/=i;
            tmp=n.Sqrt();
        }else{
            i+=2;
        }
    }
    cout << n << " " << endl << endl;
}
</CODE>
Come puoi vedere dalla funzine Scompo(CInfInt), CInfInt viene utilizzato
come un int normale:
/= , >= , % , += , etc...
non solo +,*,/,-, ma come vedi anche modulo, +=, *= etc... in pratica tutti
gli operatori e non solo quelli basi.
In piu' c'e' un CInfInt::Sqrt() che gli int ovviamente non hanno! Questa nel
mio numero e' un metodo della classe.
L'output di tale programma e':
<OUTPUT>
Tommy HUGE scomposizione:
Numero da scomporre:
+65296612059791253540377962630220163144009 (numero di 41 cifre)
+3 +3 +7 +7 +7 +13 +13 +13 +13 +13 +103 +751 +911 +911 +911 +2129 +2371
+121763 +1584829
Scomposizione completata, grazie !
</OUTPUT>
In pratica il numero di 41 cifre (possiamo sapere la lunghezza chiamando il
metdodo CInfInt::GetRealSize() ), e' il numero che vogliamo scomporre in
fattori primi, poi dopo abbiamo tutti i fattori primi che se moltiplichiamo
tra di loro formeranno il numero iniziale di 41 cifre. La scomposizione
richiede circa 4 secondi, non e' il massimo della velocita', ma non e'
nemmeno tanto male... (e poi l'ho fatta anni fa per divertimento mentre
imparavo il C++!).
Ovviamente non ho postato l'header CInfInt.h, questo e' quello che devi fare
TU ;-) E poi CInfInf l'ho scritta tutta in C++ usando la ex STL.
Buon lavoro!
Tommy

 Qualcuno ha esperienza in merito???
Come ti ha detto Tommy (magari formalizzi ufficialmente il tutto come un 
polinomio), oppure usi delle stringhe (se non sbaglio l'implementazione 
della GNU si chiama GMP).
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

 partire credo tu debba tenerlo come secondo esercizio!
Grassie dei vostri consigli gente, in effetti pensandoci bene non e' stato
poi cosi' difficile e
l'ho implementata proprio utilizzando un'array di unsigned int in modo da
non sprecare
nessun bittino... Ed presto credo che passero' ad unsigned long.
Per ora sembra fare il suo dovere ...
anche se per fare la moltiplicazione tra A e B mi sono ridotto a fare B
somme ;-P
Ora vedro' di tirare fuori una moltiplicazione un po' + seria shiftando un
po' qua e un po' la...
Anche se non ne ho una immediata necessita' mi piacerebbe poter
rappresentare il tutto
in forma decimale, secondo voi come potrei fare ????
Per come ho implementato il tutto la rappresentazione hex e quella binaria
escono "al volo",
ma per quella decimale come faccio ???
Ciau Il.Socio

 ma per quella decimale come faccio ???
In forma "decimale" propriamente parlando non puoi! Puoi invece ritornare
una stringa che contenga il numero in forma decimale. Se hai 1001 (9), non
puoi ritornare 9, ma puoi ritornare "9" che a video ha lo stesso effetto.
In teoria potresti ritornare 9, ma visto che vuoi numeri di 100 cifre, beh,
in che var lo metti ?!? Quindi ti serve una stringa. (o qualsiasi altro
contenitore).
Tommy

 contenitore).
Allora il problema diventa.... come faccio a convertire un numerone di 400
cifre
in una stringa di 400 char?
Ti faro' un'esempio pratico tanto per capirci meglio....
Il numero 140.000 lo rappresento in questo modo (con un array di unsigned
int)...
a[0] = 2
a[1] = 8.928
infatti 65.536*2 + 8.928 = 140.000
Di questo numerone le conversioni in hex o in binario mi vengono facilmente,
infatti mi basta convertire uno ad uno i singoli elementi dell'array in
stringhe.
Array =>   Hex    =>    Bin
2        =>   2        =>    0000 0000 0000 0010
8.928 =>  22E0   =>    0010 0010 1110 0000
Per ottenere la rappresentazione completa del numerone 140.000 nei due
formati.
Hex  "222E0"
Bin   "0000 0000 0000 0010  0010 0010 1110 0000"
Pero' per la conversione in decimale non so come procedere...
come posso a partire dall' array o eventualmente dalle stringhe hex o bin
arrivare alla stringa "140000" ?
Ciau, e grassie 1000 del supporto, Il.Socio

Pero' per la conversione in decimale non so come procedere...
Un sistema comodo e' usare come base 10000 invece di una
potenza di due. Quindi ogni "cifra" del numerone si traduce
in quattro cifre decimali.
HTH
Andrea

 in quattro cifre decimali.
Ciao andrew, non ho capito bene cosa intendi, puoi farmi un'esempio ???
tnx Il.Socio

 arrivare alla stringa "140000" ?
Capisco, hai pensato troppo al valore binario...
In realta' e' possibile da "0000 0000 0000 0010  0010 0010 1110 0000" (una
volta che sei arrivato a questo valore binaio)arrivare a 140.000, il
problema e' che richiede calcoli che con i tipi  forniti da C/C++ non poi
fare e quindi siamo da capo... dovresti rifare la stessa cosa due volte! E
poi se devi fare dei calcoli pesanti anche per rappresentare i numeri
diventa scomodo.
E' problematico (ma possibile) anche, dalla stringa
"16899546546512131321564123151" (ad esempio) arrivare alla tua
rappresentazione (quindi prendere input dall'utente).
Andrea ti ha proposto una valida alternativa, altrimenti rimane sempre il
metodo sprecone che ti avevo detto io all'inizio. In quel modo convertire il
numero in stringa e' immediato!
Tommy

tnx Il.Socio
Esprimendo i numeri in base 10000 hai il vantaggio che
la conversione a decimale la puoi fare senza dover
ricorrere a operazioni di modulo... ad esempio
   123456789 = 6789 x 10000^0 +
               2345 x 10000^1 +
                  1 x 10000^2
quindi quel numero espresso in base 10000 ha tre cifre.
Il valore 10000 e' "piccolo" a sufficienza per garantire
che con interi a 32 bit non vai in overflow con le
moltiplicazioni e il fatto che la base sia una potenza
di 10 semplifica la stampa perche' basta mappare
ciascuna "cifra" nelle 4 cifre decimali corrispondenti.
La conversione in base 10 di un numero "grande" espresso
in base 10000 e' semplice perche' puo' essere fatta
cifra a cifra... (un po' come la conversione in binario
di un numero espresso in esadecimale).
HTH
Andrea

 quindi quel numero espresso in base 10000 ha tre cifre.
Ah, Capito tutto!!!  Purtroppo e' un'approccio che per l'impiego
che ne devo fare (il tutto dovra' alla fine girare su di un cell.)
non mi posso permettere a causa dello "spreco" eccessivo di byte
che questo metodo comporta.
Grazie cmq. dell'aiuto !!!

 rappresentazione (quindi prendere input dall'utente).
Gia', infatti credo che questi numeroni alla fine li memorizzero' in formato
hex cosi'
mi evito qualsiasi mal di testa e potro' caricarli e salvarli "al volo".
Grazie Tommy !!!

 sentire.
Ovvio. Che applicazione stai cercando di fare per il 3650 in cui hai bisogno
di numeri con 100 cifre? Scusa le mie domande invadenti, se non puoi
rispondere capisco...
Ciao,
Tommy

 rispondere capisco...
Non ti preoccupare tommy, non lavoro per la nasa ;-) sto cercando di
sviluppare
un programmino per lo scambio di mms cifrati con rsa e se avro' tempo
velocizzare
il tutto applicando il des.
Ciau Il.Socio

 Ciau Il.Socio
non bastonarmi ... ma gli algoritmi di crpt/decript non funzionano su
primitive base, e quindi ti sarebbe direttamente di implementarli senza
dover fare cose strane ?
(ho studiato solo come funzionano non mi sono ancora letto gli algoritmi
quindi potrei essere falloso, cmq del des sono sicuro che usa un metodo di
scambio completamente legato solo alla word che tu gli dai come dato base,
che sia scalabile in lunghezza di word e' un'altro conto)

 dover fare cose strane ?
Probabilmente per la fretta ti sei perso qualche parolina qua e la :-) ...
Per il des, questo e' vero, non lo e' pero' per rsa che e' alla base del
mio progetto...
Per implementare rsa e avere un minimo di sicurezza, mi servono
2 numeroni primi di almeno 512bit => 64byte e tra di essi dovro'
calcolarne il prodotto ottenendo quello che e' il modulo di circa
1024bit => 128byte.
Spaccioccando un po' con i dati e con questi numeroni si riesce ad
ottenere una cifratura a chiave asimmetrica abbastanza affidabile,
pero' come vedi, entrano in gioco numeri piuttosto grandi.
Probabilmente gli esempi che hai visto sono quelli classici del tipo...
p=11, q=7, n=77 che pur essendo didattici non sono affatto affidabili
per quel che riguarda la sicurezza dei dati, in quanto e' troppo semplice
fattorizzare il num. 77
Quegli esempi devono essere impiegati nella realta' con numeroni ben piu'
grandi...  Ciau Il.Socio

 ha scritto nel messaggio
news:b830bb$eqi$1...@newsreader.mailgate.org...

bhe lo avevo detto di non bastonarmi :-p
grazie cmq della spiegazione