View Full Version : [C++] Lavorare su interi infiniti
Goten_ssj
12-05-2007, 17:30
il mio problema è questo: ho bisogno di creare un programma, una sorta di calcolatrice, che possa lavorare su interi infiniti...
la mia idea è quella di concatenare + interi (4 byte sono no?) in modo tale da non essere limitato nelle cifre...
qualcuno può aiutarmi nella realizzazione?? qualche idea?
Goten_ssj
12-05-2007, 18:02
infinito per modo di dire..ma dico che mi servirebbe lavorare ad esempio con un intero che abbia tipo 300 cifre...e dato che un int mi sembra ne possa contenere solo 16 o 32 (adesso non ricordo) dovrei riuscire a concatenarli e lavorare sui riporti no?
Ziosilvio
12-05-2007, 18:29
Ci sono librerie C e C++ per gli interi di grandezza arbitraria; ma non mi ricordo come si chiamano... :muro:
A che scopo ti serve lavorare con numeri così grandi?
Comunque 300 cifre sono tante, sicuramente dovrai dividire i calcoli per numeri più piccoli.
Goten_ssj
12-05-2007, 18:31
uhm...c'è qualcuno che può aiutarmi a trovare quelle librerie?? e per grandezza arbitraria cosa intendi??
Goten_ssj
12-05-2007, 18:35
A che scopo ti serve lavorare con numeri così grandi?
Comunque 300 cifre sono tante, sicuramente dovrai dividire i calcoli per numeri più piccoli.
ma è per dire...possono bastare anche 80-90 cifre..però è x trovare un modo che concateni in modo infinito gli interi, lavorando sui riporti penso..qualcuno ha altre idee??
Ma è per fare calcoli simili ai limiti o robe così?
Che ci posso fare sn curioso :D
Goten_ssj
12-05-2007, 19:29
è una sfida che mi hanno fatto..tutto qui..niente di che..non so a cosa potrebbe servire XD
Capisco, comunque considerando i long(4 byte=32 bit) li puoi pensare invece che un numero singolo come una parte di numero, in quel modo non hai limiti di grandezza...teoricamente.
Goten_ssj
12-05-2007, 19:37
si..ma come faccio??
Ti devi studiare un buon sistema, ma il linea di massima potresti fare una cosa del tipo:
N=8749827489237426748236874 3724523462364326546327634
N1=8749827489237426748236874
N2=3724523462364326546327634
In pratica invece di considerare un unico grande numero, lo consideri come formato da più numeri piccoli.
Però i calcoli, i riporti ecc ecc te li devi gestire te...
Se non ti interessano i numeri con la virgola non è nemmeno tanto complicato, ma comunque bisogna studiarsi un po' la cosa.
Goten_ssj
12-05-2007, 19:50
infinito per modo di dire..ma dico che mi servirebbe lavorare ad esempio con un intero che abbia tipo 300 cifre...e dato che un int mi sembra ne possa contenere solo 16 o 32 (adesso non ricordo) dovrei riuscire a concatenarli e lavorare sui riporti no?
è esattamente la prima cosa che ho scritto...mi servono idee per realizzare la concatenazione e i riporti.. :(
Goten_ssj
13-05-2007, 01:12
qualcuno può aiutarmi? :(
Energy++
13-05-2007, 08:26
http://www.hwupgrade.it/forum/showpost.php?p=13190194&postcount=29
Goten_ssj
13-05-2007, 12:42
grazie per la segnalazione, il problema è che a me occorre lavorare in c++ (e non in c) e il numero di cifre non dovrebbe essere solo limitato a 20, ma dovrebbe lavorare in modo illimitato, quindi penso occorrerà utilizzare dei puntatori...
se c'è qualcuno di animo buono che può darmi qualche spunto e consigliarmi qualche libreria che contenga funzioni utili mi farebbe un grande favore..
ecco qua
http://gmplib.org/
Goten_ssj
13-05-2007, 13:12
ehm..dato che sono un po' niubbo, puoi spiegarmi come usare quella libreria??
Goten_ssj
13-05-2007, 15:55
se volete vi posto l'interfaccia del programma che penso di fare..
c'è una memo per inserire il numero, 4 bottoni per gli operatori (+,-,*,/) e il bottone di visualizza risultato (=)
Guarda, per fare una cosa basilare non vedo troppe difficoltà da affrontare.
Soluzione nr. 1: usi una libreria come quella che ti è stata suggerita.
Soluzione nr. 2: te lo fai te.
Per fartelo te hai diverse possibilità. Puoi tenerti il numero memorizzando le singole cifre in un array o in una lista o in una stringa ad esempio.
Poi per le operazioni elementari (somma e moltiplicazione) fai come facevi alle elementari. Te le ricordi ancora le operazioni in colonna? bene... ad un livello base si fa cosi.
Se però ti interessano le performance, per moltiplicare due numeri grandi ci sono algoritmi più efficenti, tipo quello di Karatsuba. Ma qui si che ci dovrai sbattere la testa un pò di più...
Io mi terrei le cifre in un array o in una lista e poi a mano ti gestisci le operazioni di somma e moltiplicazione con il metodo che ti insegnano alle elementari.
Goten_ssj
13-05-2007, 19:57
si..pensavo di farmelo da me..non ho ancora ben capito bene come memorizzare e dividere i numeri di 40-50 cifre ad esempio per poi poterli usare per fare i calcoli
si..pensavo di farmelo da me..non ho ancora ben capito bene come memorizzare e dividere i numeri di 40-50 cifre ad esempio per poi poterli usare per fare i calcoliSe non hai ben chiari i concetti legati alla aritmetica a "precisione multipla", al "carry" e altre cose (tra cui il sistema di numerazione binario, complemento a due, algebra booleana, ecc...), lascia perdere ... o usa una libreria apposita.
Goten_ssj
13-05-2007, 20:27
li so quei concetti...ma se qualcuno mi desse una qualsiasi dritta mi farebbe un piacere...
il carry l'ho visto solo in assembler che sarebbe il flag del riporto xò più di quello non ricordo altri ambiti..
per quanto riguarda l'aritmetica a precisione multipla cosa intendi??
li so quei concetti...ma se qualcuno mi desse una qualsiasi dritta mi farebbe un piacere...
il carry l'ho visto solo in assembler che sarebbe il flag del riporto xò più di quello non ricordo altri ambiti..
per quanto riguarda l'aritmetica a precisione multipla cosa intendi??Semplice, scenario tipico: devi fare una somma di due numeri a 64 bit ma il tuo processore è solo in grado di fare somme su operandi a 32 bit. Che fai??? .... e il carry centra eccome!
si..pensavo di farmelo da me..non ho ancora ben capito bene come memorizzare e dividere i numeri di 40-50 cifre ad esempio per poi poterli usare per fare i calcoli
Usi un array, ad esempio.
12345 lo memorizzi in un array di 5 elementi dove
a[0]=5
a[1]=4
a[2]=3
a[3]=2
a[2]=1
Poi le operazioni come le facevi alle elementari? Prendi due numeri e li incolonni per la somma o la moltiplicazione ad esempio. E applichi le stesse regole.
10 +
15 =
-------
25 (0+5, 1+1...eccc, insomma si fa alle elementari)
@andbin
cosa c'entra l'algebra booleana?? :mbe:
Goten_ssj
13-05-2007, 20:33
ma il problema è che non si può sapere quante cifre hanno gli operandi, quindi dovrei fare qualcosa tipo un array dinamico che possa contenere sia un numero di 4 cifre che un numero di 83 cifre...
ma il problema è che non si può sapere quante cifre hanno gli operandi, quindi dovrei fare qualcosa tipo un array dinamico che possa contenere sia un numero di 4 cifre che un numero di 83 cifre...
hai familiarità con il concetto di 'lista'?
Goten_ssj
13-05-2007, 20:36
ehm, no..
poi volevo kiedere: una variabile di tipo string non ha limiti di spazio vero??
12345 lo memorizzi in un array di 5 elementi dove
a[0]=5
a[1]=4
a[2]=3
a[3]=2
a[2]=1
Ma stai scherzando??? Tu prendi le singole cifre decimali e vorresti farci i calcoli così ... direttamente???
@andbin
cosa c'entra l'algebra booleana?? :mbe:Centra centra .... specialmente se vuoi fare tutto in C puro senza assembly.
Goten_ssj
13-05-2007, 20:39
si..il mio progetto devo farlo tutto con un unico compilatore di c++ (uso il borland c++ builder 6)
Ma stai scherzando??? Tu prendi le singole cifre decimali e vorresti farci i calcoli così ... direttamente???
Non mi sembra che per le sue esigenze ci siano troppe controindicazioni.
Tu cosa gli consiglieresti?
Goten_ssj
13-05-2007, 20:46
ah..mi è venuta in mente un'ideona..
suddividere entrambi gli operandi in singole cifre ad esempio:
23828378232873+
(a[0]=3
a[1]=7
a[2]=8
a[3]=2
a[4]=3
a[5]=2
a[6]=8
a[7]=7
a[8]=3
a[9]=8
a[10]=2
a[11]=8
a[12]=3
a[13]=2)
88238723782379=
(b[0]=9
b[1]=7
b[2]=3
b[3]=2
b[4]=8
b[5]=7
b[6]=3
b[7]=2
b[8]=7
b[9]=8
b[10]=3
b[11]=2
b[12]=8
b[13]=8)
e poi li sommo ad uno ad uno ad esempio
c[0]=a[0]+b[0]=3+9=12=2 (+il riporto che andrò ad aggiungere a c[1])
c[1]=a[1]+b[1]+riporto=7+7+1=15=5 (+ il riporto e così via)
tutto questo potrebbe essere fatto con un ciclo for...poi potrei pensare a farlo per la moltiplicazione etc...
Non mi sembra che per le sue esigenze ci siano troppe controindicazioni.Beh certo, se la mettiamo così gli potrebbe anche andare bene fare operazioni sulle singole cifre decimali! .... anche se parlando di prestazioni e efficienza farebbe :Puke:
Tu cosa gli consiglieresti?In genere per queste cose si sceglie la dimensione della "parola" (word) gestibile dal processore, es 32 bit (un int) e si gestisce un array di N word in cui i dati sono chiaramente in binario.
Fare somme/sottrazioni è davvero banale (c'è solo la questione del carry se non si vuole usare assembly). La moltiplicazione è tutto sommato semplice (concettualmente), la divisione un po' meno.
Beh certo, se la mettiamo così gli potrebbe anche andare bene fare operazioni sulle singole cifre decimali! .... anche se parlando di prestazioni e efficienza farebbe :Puke:
In genere per queste cose si sceglie la dimensione della "parola" (word) gestibile dal processore, es 32 bit (un int) e si gestisce un array di N word in cui i dati sono chiaramente in binario.
Fare somme/sottrazioni è davvero banale (c'è solo la questione del carry se non si vuole usare assembly). La moltiplicazione è tutto sommato semplice (concettualmente), la divisione un po' meno.
A me non sembrava così strampalata l'implementazione che ho consigliato...
http://en.wikipedia.org/wiki/Bignum
...
It is often implemented by storing a number as a variable-length array of digits in some base, in contrast to most computer arithmetic which uses a fixed number of bits related to the size of the processor registers.
...
Goten_ssj
13-05-2007, 21:05
allora la mia idea può andare??
i problemi vengono con sottrazioni e divisioni credo :O
A me non sembrava così strampalataNon ho detto che è strampalata .... semplicemente è meno efficiente che gestire un array di N word binarie.
La classe BigInteger di Java è fatta proprio con un array di N int. La somma ad esempio la fa in modo davvero banale semplicemente sommando, in ciclo, la word di un operando con la word dell'altro operando. Per la gestione del carry fa una furbizia semplice: il calcolo lo fa come long, così la parte alta tiene il carry che viene shiftato a destra di 32 e risommato alla word successiva.
Veloce, semplice e furbo.
Goten_ssj
13-05-2007, 21:12
Non ho detto che è strampalata .... semplicemente è meno efficiente che gestire un array di N word binarie.
La classe BigInteger di Java è fatta proprio con un array di N int. La somma ad esempio la fa in modo davvero banale semplicemente sommando, in ciclo, la word di un operando con la word dell'altro operando. Per la gestione del carry fa una furbizia semplice: il calcolo lo fa come long, così la parte alta tiene il carry che viene shiftato a destra di 32 e risommato alla word successiva.
Veloce, semplice e furbo.
bisognerebbe che me lo trasporresti in c++ anche se penso di aver capito...dovrei solo provarlo su carta x capire meglio quella questione del carry da shiftare.. ^_^
Concordo con andbin, l'approccio migliore è usare la memoriazzazione con sequenze di interi...
Comunque in questo caso si tratterebbe di realizzare un'algebra in base 2^32, di fatto ogni numero sarebbe composto da una serie di interi che di fatto rappresentano una cifra nella nostra algebra.
Un'approccio interessante sarebbe quello che sfrutta gli algoritmi usati nelle ALU per svolgere le varie operazioni in binario, solamente generalizzati con cifre a 32 bit.
Basta realizzare i blocchi di base per poi poter usare pari pari gli stessi algoritmi...
Goten_ssj
13-05-2007, 21:20
si..per quanto riguarda addizione e sottrazione non dovrebbe essere troppo difficile...è la moltiplicazione e la divisione che preoccupano (almeno se uso quel sistema che dite voi a gruppi di 32 bit)
mentre se suddivido cifra per cifra è più semplice xkè posso farlo a metodo elementare...
Ripeto...esistono algoritmi ben precisi per moltiplicazione e divisione...basta reimplementarli modularmente per cifre a 32 bit...
Comunque sicuramente si trovano fior fiore di librerie che fanno la stessa cosa...
Goten_ssj
13-05-2007, 21:39
volevo utilizzare librerie solo se strettamente necessario..non per un solo algoritmo che serva per fare LA MOLTIPLICAZIONE o LA DIVISIONE..
penso che dovrò utilizzare la libreria string per trasferire i valori di input dalle memo...appena posso mi metto al lavoro e vi faccio vedere cosa butto giù...
Hai cercato gli algoritmi usati nelle alu per fare moltiplicazione e divisione ?
Goten_ssj
14-05-2007, 13:17
no..dove posso trovarli? :D
Google ? http://www.google.it/search?hl=it&client=firefox-a&rls=com.ubuntu%3Aen-US%3Aofficial&hs=1JZ&q=alu+multiplication+division+algorithm&btnG=Cerca&meta=
Comunque ti conviene prima progettare i componenti basilari...ad esempio nella mltiplicazione serve un full-adder a 64 bit...che può essere realizzato mediante due full-adder a 32 bit ;)
no..dove posso trovarli? :Dhttp://en.wikipedia.org/wiki/Category:Computer_arithmetic
Goten_ssj
25-05-2007, 16:29
allora..il prof mi ha detto che il programma va fatto con le liste, cosa che ci ha appena spiegato...
quindi, qualcuno può suggerirmi qualcosa??
Le liste è solamente il metodo di memorizzazione degli interi concatenati...per il resto puoi usare gli algoritmi di cui ti avevo parlato...
Prima di tutto devi realizzare un full-adder modulare (cioè che si possa concatenare ad altri full-adder a 32 bit...poi concatenando questi full-adder puoi realizzare somma e sottrazione a N*32 bit...
Quenado hai un adder a N*32 bit puoi realizzare anche moltiplicazioni e divisioni con gli algoritmi di cui ti avevo parlato...
Goten_ssj
25-05-2007, 18:03
e come lo realizzo questo full adder??
e come lo realizzo questo full adder??Per "full adder" si intende una logica che ha come input:
Le due parole A e B
il carry (dall'adder relativo alle parole meno significative)
e come output:
La parola S che rappresenta la somma di A e B
il carry risultante
Goten_ssj
25-05-2007, 20:12
per la moltiplicazione mi è quasi kiaro...
mi è meno kiaro l'impiego di questo full adder per la sottrazione..
Goten_ssj
09-06-2007, 15:22
ok..ho realizzato addizione e sottrazione...non riesco a venirne fuori dalla moltiplicazione e divisione...idee??
Come le realizzi le moltiplicazioni quando le fai a mano ?
54 x 32 = 2 * 54 + 3 * 54 * 10 = (2 * 4 + 2 * 5 * 10) + (3 * 4 + 3 * 5 * 10) * 10
Ora immaginati che le tue cifre siano interi a 32 bit e non in base 10...
Immaginati quindi che 54 sia in base 2^32...quindi 5 * 2^32 + 4, cioè ogni cifra è un elemento della catena di interi che ti sei costruito per rappresentare i numeri...
Quindi:
54[base 2^32] x 32[base 2^32] = (2[base 2^32] * 4[base 2^32] + 2[base 2^32] * 5[base 2^32] * 2^32) + (3[base 2^32] * 4[base 2^32] + 3[base 2^32] * 5[base 2^32] * 2^32) * 2^32
La somma ce l'hai già, la moltiplicazione per 2^32 è banale perché basta aggiungere uno 0 a 32 bit come elemento meno significativo della catena di interi (equivale ad uno shift a sinistra).
L'unico problema è la moltiplicazione fra due interi a 32 bit:
x[base 2^32] * y[base 2^32]
infatti può dare un risultato su 64 bit...ed è qui che devi lavorare.
Se lavorassi in assembler sarebbe banale, perché già i risultati delle moltiplicazioni a 32 bit vengono riportati su 2 registri a 32 bit, ma probabilmente non puoi. Quindi devi lavorare di ingegno per fare questa moltiplicazione...e questa te la lascio a te.
Goten_ssj
09-06-2007, 16:30
ho fatto una lista di interi da una cifra per facilitare le funzioni e la lettura dalle edit...
void ListaInt::somma(ListaInt *l)
{
ListaInt *ltemp=new ListaInt;
pareggia(l);
bool rip=false;
for(int i=0; i<=contaelementi()-1; i++)
{
if(ottienielemento(i)+l->ottienielemento(i)+int(rip)>9)
{
ltemp->aggiungi((ottienielemento(i)+l->ottienielemento(i)+int(rip))%10);
rip=true;
}
else
{
ltemp->aggiungi(ottienielemento(i)+l->ottienielemento(i)+int(rip));
rip=false;
}
}
ltemp->aggiungi(int(rip));
svuota();
for(int i=ltemp->contaelementi()-1; i>=0; i--)
{
aggiungi(ltemp->ottienielemento(i));
}
}
questa è il codice della funzione di addizione tra 2 liste...
la funzione pareggia aggiunge tanti zeri all'inizio della lista per avere uno stesso numero di cifre...
la funzione ottienielemento restituisce la cifra ad una certa posizione..
la funzione contaelementi restituisce il numero delle cifre del numero..
la funzione aggiungi aggiunge la cifra di peso minore all'interno della lista..
ok..ho realizzato addizione e sottrazione...non riesco a venirne fuori dalla moltiplicazione e divisione...idee??Per la moltiplicazione è abbastanza semplice ... si fa quello che si farebbe a mano come ci è stato insegnato alle elementari.
Immagina di dover moltiplicare 2 numeri di 64 bit ognuno. Lavorando in ambiente a 32 bit, però puoi solo fare 32x32=64 bit. Quindi spezzi gli operandi in due parti da 32 bit e fai delle moltiplicazioni parziali che alla fine sommerai.
Risulterebbe una cosa del genere:
32bit 32bit
/ | \
+-----+-----+
| A | B | x
+-----+-----+
+-----+-----+
| C | D | =
+-----+-----+
-------------------------------
+-----+-----+
| B x D | +
+-----+-----+
+-----+-----+
| A x D | +
+-----+-----+
+-----+-----+
| B x C | +
+-----+-----+
+-----+-----+
| A x C | =
+-----+-----+
-------------------------------
+-----+-----+-----+-----+
| Risultato su 128 bit |
+-----+-----+-----+-----+
E se uno volesse moltiplicare 256 bit x 256 bit?? Se puoi fare sempre e soltanto moltiplicazioni su 32 bit, avrai 8 parole da 32 bit per ogni operando. Fai le moltiplicazioni parziali tra le singole parole e poi la somma.
Goten_ssj
09-06-2007, 16:42
si, ci ho provato, ma mi dà dei problemi nell'annidamento dei for...
ho provato sia in quel modo che in un modo di somme ripetute, dato che non ho problemi ad aggiungere numeri infiniti tra di loro con l'algoritmo della somma...l'addizione funziona con "infinite" cifre...
si, ci ho provato, ma mi dà dei problemi nell'annidamento dei for...Volendo "generalizzare" la moltiplicazione, si tratta di fare 2 for, uno dentro all'altro. Uno per scansionare le parole dell'operando A e l'altro per scansionare le parole dell'operando B.
Goten_ssj
09-06-2007, 16:49
si..ma mi dà un pacco di problemi già quando i numeri iniziano a essere di 3 cifre e non so xkè...sono 2 giorni che stò debuggando e non ne vengo fuori...
Mettiamo che tu abbia la tua classe LongInteger...
Suppongo che la classe abbia i metodi add per fare la somma, getInt per ottenere l'i-esimo intero, shl per fare lo shift a sinistra di N cifre (aggiunge N interi a zero nelle posizioni meno significative meno significativo)...
LongInteger a, b sono i numeri da moltiplicare...
LongInteger result(0); //risultato inizializzato a 0
for(int i = 0; i < a.intCount(); ++i)
{
LongInteger partial(0);
for(int j = 0; j < b.intCount(); ++j)
{
LongInteger tmp = LongInteger::IntMultply(a.getInt(i), b.getInt(j));
partial.add(tmp.shl(j)):
}
partial.shl(i);
result.add(partial);
}
L'unica cosa che devi realizzare è
static LongInteger IntMultply(int a, int b);
Questo metodo static presi in input 2 interi ritorna un LongInteger su 64 bit con il loro prodotto.
Per fare prodotto puoi fare secondo lo schema postato da andbin ricordando che un intero a 32 bit è anche formato 2 interi a 16 bit...
Goten_ssj
09-06-2007, 17:09
come ho già detto, per motivi di comodità, facilità di ragionamento e di lettura dalla Edit di input, ho creato delle liste di normali int ai quali viene assegnata una sola cifra..
questo è il .h che contiene la classe lista...
// Librerie e Unit Incluse
#include "ClassNodo.h"
#ifndef ClassListaH
#define ClassListaH
class ListaInt
{
private:
NodoInt *primo;
NodoInt *ultimo;
bool segno; // true=positivo, false=negativo
public:
// Costruttore
ListaInt()
{
primo=0;
ultimo=0;
segno=true;
}
// Metodi di Get
NodoInt *ottieniprimo(){return primo;}
NodoInt *ottieniultimo(){return ultimo;}
int ottienielemento(int pos);
int contaelementi()
{
int i=0;
for(NodoInt *t=primo; t!=0; t=t->ottieniprox(),i++){}
return i;
}
bool ottienisegno() {return segno;}
bool vuota() {if(primo==0) return true; else return false;}
bool monocifra() {if(contaelementi()==1) return true; else return false;}
bool maggiore(ListaInt *l)
{
for(int i=contaelementi()-1; i>=0; i--)
{
if(ottienielemento(i)<l->ottienielemento(i))
{
return false;
}
else if(l->ottienielemento(i)<ottienielemento(i))
{
return true;
}
}
return true;
}
// Metodi di Set
void impostaprimo(NodoInt *p) {primo=p;}
void impostaultimo (NodoInt *p) {ultimo=p;}
void aggiungi(int n);
void togli();
void svuota();
// Metodi delle Operazioni
void pareggia(ListaInt *l);
void scambia(ListaInt *l);
void somma(ListaInt *l);
void sottrai(ListaInt *l);
void moltiplica(ListaInt *l);
void dividi(ListaInt *l);
// Distruttore
~ListaInt() {svuota();}
};
#endif
questo è il .h che contiene la classe nodo..(in questa i metodi sono tutti inline, quindi contenuti nel .h, mentre nell'altra solo alcuni sono inline e i restanti sono nel file.cpp...
// Librerie e Unit Incluse
#ifndef ClassNodoH
#define ClassNodoH
// Classe Nodo
class NodoInt
{
private:
int dato;
NodoInt *prec;
NodoInt *prox;
public:
// Costruttore
NodoInt()
{
dato=0;
prec=0;
prox=0;
}
// Metodi di Get
int ottienidato() {return dato;}
NodoInt *ottieniprec() {return prec;}
NodoInt *ottieniprox() {return prox;}
// Metodi di Set
void setdato(int n) {dato=n;}
void setprec(NodoInt *n) {prec=n;}
void setprox(NodoInt *n) {prox=n;}
// Distruttore
~NodoInt(){}
};
#endif
questo x facilitare a voi un po' la comprensione..
come ho già detto, addizione e sottrazione funzionano senza problemi (finalmente sono riuscito a fare anche le sottrazioni in negativo), ma proprio da dio :D
L'approccio è sbagliato...la classe ha troppe responsabilità...rappresenta sia la lista di interi che un intero lungo.
Quindi ti consiglio caldamente di separarla in due: una classe LongInteger ed una classe IntList (suppongo che tu non possa usare la STL).
La classe IntList farà solo operazioni sulla lista: creazione, aggiunta in coda e in testa, recupero di un elemento, eliminazione di un elemento (se ti serve).
La classe LongInteger si occuperà di rappresentare l'intero e tutte le operazioni che ci devi fare: somma, sottrazione, moltiplicazione, shift a destra, shift a sinistra
Goten_ssj
09-06-2007, 17:24
veramente la classe lista ha solo puntatori a primo e ultimo nodo più la variabile booleana del segno..
non capisco bene quello che mi stai chiedendo.. (STL??)
mi hanno appena spiegato le liste ed è il primo lavoro che ci stò facendo...iniziamo l'anno prox a lavorare per bene con tutti gli oggetti dinamici..
Per i metodi delle operazioni ti consiglio di usare questa struttura:
LongInteger & add(const LongInteger &op);
Per farti un esempio:
LongInteger & shiftLeft(const int count)
{
for(int i = 0; i < intList.intCount(); ++i)
intList.headInsert(0); //inserisco uno zero in testa per fare uno sfiht a sinsitra
return *this;
}
Goten_ssj
09-06-2007, 17:32
questo inserirebbe tanti zeri quante sono le cifre del numero?
quindi se la mia lista fosse formata da
2-3
con questo metodo diventerebbe
2-3-0-0
a che pro?
veramente la classe lista ha solo puntatori a primo e ultimo nodo più la variabile booleana del segno..
Lascia perdere la STL, volevo solo sapere se la potevi usare, ma se non la conosci significa che non puoi.
Come dati ha solo quello, ma svolge sia le operazioni di una lista che le operazioni di un intero lungo e questo non va bene perché rende inutilmente confusionario il lavoro che hai fatto.
Metti solo le funzioni della lista in una classe IntList o ListaInt come preferisci...e le operazioni sugli interi in una classe LongInteger o BigInteger o InteriGrandi. Io te lo scrivo in inglese, ma poi lo puoi mettere anche in italiano, come più ti aggrada.
class IntList
{
IntNode *primo;
IntNode *ultimo;
int nodeCount;
public:
IntList(int firstInt); //tanto una lista vuota non ti serve a niente
void headInsert(int value);
void tailInsert(int value);
int headRemove();
int tailRemove();
int getNodeCount();
int getNodeValue(int index);
~IntList();
}
Poi la classe che rappresenta l'intero:
class BigInteger
{
IntList intList;
bool sign;
public:
BigInteger(int value = 0) : intList(value), sign(false); //se non hai fatto le liste di inizializzazione ignora quello che vedi dopo i ":", ma in tal caso devi mettere anche il costruttore per la lista vuota
BigInteger & add(const BigInteger &operand);
BigInteger & subtract(const BigInteger &operand);
BigInteger & multiplyBy(const BigInteger &operand);
BigInteger & divideBy(const BigInteger &operand);
BigInteger & shiftLeft(const int operand);
bool getSign();
int getInt(const int index);
static BigInteger IntMultiply(const int a, const int b);
}
questo inserirebbe tanti zeri quante sono le cifre del numero?
quindi se la mia lista fosse formata da
2-3
con questo metodo diventerebbe
2-3-0-0
a che pro?
Se leggi il codice per la moltiplicazione che ti ho postato nel messaggio prima lo scoprirai ;)
Equivale a moltiplicare per 2^32 ;)
Goten_ssj
09-06-2007, 17:49
posso pure metterle come dici tu cmq sia il fatto è che non riesco a creare l'algoritmo che moltiplica senza che ci siano errori :P
BigInteger & add(const BigInteger &operand);
BigInteger & subtract(const BigInteger &operand);
BigInteger & multiplyBy(const BigInteger &operand);
BigInteger & divideBy(const BigInteger &operand);
BigInteger & shiftLeft(const int operand);
Ti spiego anche a cosa serve una struttura di questo tipo...
Ad esempio puoi fare:
BigInteger a, b, c;
a.add(b).shiftLeft(10).sum(c);
Cioè aggiungo b, shifto di 10 e poi sommo c
Oppure anche una cosa del genere:
a.add(b.shiftLeft(10));
posso pure metterle come dici tu cmq sia il fatto è che non riesco a creare l'algoritmo che moltiplica senza che ci siano errori :P
Te l'ho scritto l'algoritmo usando lo shift...
LongInteger result(0); //risultato inizializzato a 0
for(int i = 0; i < a.intCount(); ++i)
{
LongInteger partial(0);
for(int j = 0; j < b.intCount(); ++j)
{
LongInteger tmp = LongInteger::IntMultply(a.getInt(i), b.getInt(j));
partial.add(tmp.shl(j)):
}
partial.shl(i);
result.add(partial);
}
Devi solo implementare:
static BigInteger IntMultiply(const int a, const int b);
che moltiplica due interi presentando il risultato su 64 bit...che con l'esempio grafico che ti ha fatto andbin è semplicissimo (un intero a 32 bit è anche formato da due interi a 16 bit)...
Goten_ssj
10-06-2007, 15:00
evvaiiii!!!
sono riuscito a fare la moltiplicazione per addizioni aggiuntive..
ad esempio 34214*4=(34214+34214+34214+34214)
consigli per la divisione??
http://www.tuttogps.it/forum/images/smilies/sparati.gif
Goten_ssj
10-06-2007, 18:10
ho fatto anche la divisione per sottrazioni successive..
ok...ho finito le operazioni d base (+,*,-,/)
quando avrò voglia farò qualcos'altro...grazie a tutti per il supporto :)
speriamo che il prof nn impazzisca a correggermi il codice :banned:
:Prrr:
evvaiiii!!!
sono riuscito a fare la moltiplicazione per addizioni aggiuntive..
ad esempio 34214*4=(34214+34214+34214+34214)
consigli per la divisione??
Ok...allora vedo che ho parlato per niente :D
http://www.tuttogps.it/forum/images/smilies/sparati.gif
Ue chi si rivede :)
ciao, cionci.
le fai al mugello le pieghe ? :D
Goten_ssj
10-06-2007, 21:38
Ok...allora vedo che ho parlato per niente :D
in teoria hai parlato giusto..
con il mio metodo e soprattutto usando il tipo di lista che ho creato (ogni elemento una cifra), facendo moltiplicazioni o divisioni tra numeri anche non troppo grandi impiega davvero tanto tempo
prima per fare una semplice moltiplicazione tra 2 numeri non eccessivamente grandi mi è arrivato ad allocare quasi 3gb nel file di paging (guardato dal taskmanager) :doh:
ihih..
goten, per farla semplice, il trucco potrebbe essere in un algoritmo di "rinormalizzazione" del numero ottenuto nella base scelta b:
somma-sottrazione delle due serie e rinormalizzazione
moltiplicazione delle due serie e rinormalizzazione
divisione delle due serie e rinormalizzazione
l'operazione di rinormalizzazione ti permette di lavorare con numeri rappresentati da una serie di potenze della base prescelta b senza cura del vincolo che i coefficienti della serie siano interi tra 0 e b-1.
Li trasformi poi nella rappresentazione in serie di potenze di b canonica in un secondo tempo con gestione a valanga e automatica dei riporti.
Goten_ssj
10-06-2007, 22:29
ehhh??
no ehhh ma
A = Sum (ai*b^i)
eccetera
giovane ma la conosci la farina no ? :confused: :D
Goten_ssj
10-06-2007, 22:45
no.. XD
Goten_ssj
10-06-2007, 22:50
ehh lo dico io...
no XD dici tu.
e io dico ehhhh ?
zo' fai ? dormi ? :confused: :p
Goten_ssj
10-06-2007, 22:58
ma cosa?
te capi' o no ? :confused:
Goten_ssj
10-06-2007, 22:59
no
ma cusa che l'è XD ??? :confused:
Goten_ssj
10-06-2007, 23:02
sarebbe una smile...:rolleyes:
Goten_ssj
10-06-2007, 23:04
:confused:
cioè dico, sta' smile ... te la trombi ? ;) :cool:
Goten_ssj
10-06-2007, 23:05
tu non stai bene..:D
mah. qui so' tuti mati. :confused: :(
:D
mah. qui so' tuti mati. :confused: :(
:D
ciao a2000.1 bentornato
ciao okay. tutto okay ? :)
somma algebrica e moltiplicazione in Z a numero di cifre e base a piacere:
no more than 15 code rows. :cool: :D
Goten_ssj
12-06-2007, 08:30
eh beh..
rettifico (me voglio rovina'):
le quattro operazioni in Z, con base e numero di cifre a piacere, con:
13 righe di codice! :eek: :D
e very fastweb !
Goten_ssj
12-06-2007, 20:03
vediamo...
Non te lo farà in C++ ;) a2000 è una mago del Fortran e del VBA :) E preparatissimo in generale sulla matematica...
Goten_ssj
12-06-2007, 22:51
vediamo cmq.. :D
ciao cionci :)
ma i maleDucati li conosci ?
vediamo cmq.. :D
assaggino old fashion:
Sub mul(a(), b(), c())
For i = 0 To II
ci = 0
For j = 0 To i
ci = ci + a(j) * b(i - j)
Next j
c(i) = ci
Next i
Call Rinormalizza(c())
End Sub
Goten_ssj
12-06-2007, 23:16
che linguaggio è?
basic-fortran-pascal a piacere :D
Goten_ssj
12-06-2007, 23:23
non conoscendolo non posso darti ragione o torto, cmq sfido kiunkue a fare 1 programma in c++ ke faccia anke solo la somma tra 2 numeri di cifre non definite...
e che ci vuole: :sborone:
Sub sum(a(), b(), c())
For i = 0 To II
c(i) = a(i) + b(i)
Next i
Call Rinormalizza(c())
End Sub
guarda che è anche pseudocodice pronto per C++ :)
Goten_ssj
12-06-2007, 23:29
ma dove??
mai viste quelle istruzioni :O
ma quanti anni hai ? :bimbo:
:D
hai già avuto morbillo, commodore e scarlattina ? :D
Goten_ssj
12-06-2007, 23:33
pochi..
primo PC ?
486 ? :confused:
Goten_ssj
12-06-2007, 23:36
hai già avuto morbillo, commodore e scarlattina ? :D
non so..se ti devi sfogare con il mondo mentre tu studiavi il pascal e giocavi ad arkanoid con il tuo commodore, hanno inventato le chat...guarda, esistono le reti irc, vai su un qualsiasi server, entri nel primo canale di ghei emarginati dal mondo che trovi e puoi scrivere tutte le stronzate che vuoi :D :D :D
ma dove??
mai viste quelle istruzioni :O
quando si dice ammazzarli da piccoli ... :( :D
Goten_ssj
12-06-2007, 23:39
e che ci vuole: :sborone:
Sub sum(a(), b(), c())
For i = 0 To II
c(i) = a(i) + b(i)
Next i
Call Rinormalizza(c())
End Sub
guarda che è anche pseudocodice pronto per C++ :)
immagino che siano array a(), b(), e c() :mbe:
immagino che siano array a(), b(), e c() :mbe:
giusto, bravo ... stai cominciando a disintossicarti :)
Goten_ssj
12-06-2007, 23:43
cmq sia nn c'è nessun riporto..uhm..mah..
Goten_ssj
12-06-2007, 23:44
vettori ... :O
:rotfl:
giusto, bravo ... stai cominciando a disintossicarti :)
ma siete in 2 con lo stesso account che rispondete?? :confused:
shhh, è qui il trucco !!!!
i riporti sono tutti qui:
Call Rinormalizza(c())
mitico eh :sborone:
a2000: ma nel caso in cui a non abbia le stesse cifre di b ?
In pratica lui ha messo una cifra per ogni elemento del vettore
Immaginati un vettore di N elementi per un numero di N cifre...
Facendo praticamente a[i] + b[i] ottieni c[i], anche se c[i] potrebbe essere maggiore di 10.
In tal caso ci penserà la funzione normalizza ad aggiungere il riporto alla cifra successiva e poi normalizzarla...
Goten_ssj
12-06-2007, 23:47
vabè..quello non è un problema..basta impostare a 0 tutti gli elementi in meno che ha un numero rispetto all'altro...
è così cionci. :)
ma i maleDucati (http://www.maleducati.it/) li conosci ? :confused:
Goten_ssj
12-06-2007, 23:49
shhh, è qui il trucco !!!!
i riporti sono tutti qui:
Call Rinormalizza(c())
mitico eh :sborone:
aho..si poteva intuire, ma il for nn avendo le parentesi non capivo quali comandi doveva eseguire ad ogni ciclo...
ma i maleDucati (http://www.maleducati.it/) li conosci ? :confused:
Sinceramente no :D
Goten_ssj
12-06-2007, 23:53
ma in c++ come si crea un vettore infinito??
tipo così?
int *vettore[];
bohh..come si fa? XD
A = Sum (ci * b^i) ci qualunque; b= base
Rinormalizza
A = Sum (ai * b^i) ai=0, b-1; b= base
Sinceramente no :D
:stordita:
Goten_ssj
12-06-2007, 23:57
A = Sum (ci * b^i) ci qualunque; b= base
Rinormalizza
A = Sum (ai * b^i) ai=0, b-1; b= base
ma non ce l'hai 1 linguaggio + comprensibile? XD
piuttosto scrivi a parole che interpreto meglio :D
http://www.rtsi.ch/prog/images/trasm/la_citta_incantata-b.jpg
ma in c++ come si crea un vettore infinito??
Per quello che conosci ora non si può...l'unica alternativa è ridimensionare il vettore quando gli elementi superano la dimensione allocata.
In realtà lo standard C++ definisce anche la cosiddetta Standard Tempalte Library che aggiunge un vero e proprio framework di strutture dati generiche (cioè adattabili per qualsiasi tipo di dato) al C++.
Ad esempio per i vettori di int:
vector <int> v;
v.push_back(10); //aggiungo 10 in fondo al vettore
Goten_ssj
13-06-2007, 00:01
Per quello che conosci ora non si può...l'unica alternativa è ridimensionare il vettore quando gli elementi superano la dimensione allocata.
In realtà lo standard C++ definisce anche la cosiddetta Standard Tempalte Library che aggiunge un vero e proprio framework di strutture dati generiche (cioè adattabili per qualsiasi tipo di dato) al C++.
Ad esempio per i vettori di int:
vector <int> v;
v.push_back(10); //aggiungo 10 in fondo al vettore
vabbè..puoi dirmelo...ormai la scuola è finita e lavorerò a questa calcolatrice, non dovrò farlo sulle basi delle spiegazioni del prof :P
ma non ce l'hai 1 linguaggio + comprensibile? XD
piuttosto scrivi a parole che interpreto meglio :D
ti mando tutto dopo.
ciao chihiro, buonanotte. :)
http://www.cinemadelsilenzio.it/images/film/poster/1061_big.jpg
Goten_ssj non ti preoccupare...è sempre così :D
Goten_ssj
13-06-2007, 00:06
nn mi preoccupo XD
xò adesso mi spieghi quella storia dei vettori infiniti :P
Te l'ho scritto sopra ;)
Esiste una classe della STL chiamata vector...questa classe fa uso dei template che sono una feature aggiunta una decina di anni fa (forse anche di più) al C++.
Con i template in pratica puoi creare una classe o una struttura dati o un funzione, parametrizzata in base ad uno o più tipi di dati.
Con vector quindi puoi gestire vettori di int, di float, di strutture, di oggetti creati da te...etc etc
http://www.cppreference.com/cppvector/index.html
Ad esempio:
vector <int> v;
for(int i = 0; i < 10; ++i)
{
v.push_back(i); //aggiungo l'elemento di valore i in fondo al vettore (si ridimensiona da solo)
}
Goten_ssj
13-06-2007, 00:25
spacca..appena ho tempo provo..
giovane a che punto stai ? :confused:
forzanpo' :mad:
dai che sono quattro righe in tutto :O :D
Goten_ssj
13-06-2007, 23:17
non ho ancora avuto lo sbatto :P
tel chì :)
si riduce ancora di una decina di righe :cool:
Const base = 10, base1 = base - 1
Const II = 100, II1 = II + 1
Dim a(0 To II1), b(0 To II1), c(0 To II1)
Sub sumalg(a(), s, b(), c())
If f_GT(a, b) >= 0 Then sc = 1: c(II1) = a(II1) Else sc = -1: c(II1) = s * b(II1)
For i = 0 To II
c(i) = sc * (a(i) - b(i))
Next i
ONbase c()
End Sub
Sub mul(a(), b(), c())
c(II1) = a(II1) * b(II1)
For i = 0 To II
ci = 0
For j = 0 To i
ci = ci + a(j) * b(i - j)
Next j
c(i) = ci
Next i
ONbase c()
End Sub
Function f_GT(a, b) As Integer
For i = II To 0 Step -1
f_GT = Sgn(a(i) - b(i))
If f_GT <> 0 Then Exit For
Next i
End Function
Sub ONbase(c())
For i = 0 To II - 1
Select Case c(i)
Case Is < 0
c(i + 1) = c(i + 1) - 1
c(i) = c(i) + base
Case Is < base
Case Else
c(i + 1) = c(i + 1) + Int(c(i) / base)
c(i) = c(i) Mod base
End Select
Next i
End Sub
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.