Newsgroup: it.comp.lang.c++
Titolo: Algoritmo per divisione di numeri molto grandi

Salve a tutti.
Uno si mette a studiare 3/4 linguaggi di programmazione, un paio di sistemi
operativi, strutture dati e algoritmi, un po' di altre cosette ancora ... e
pensa di conoscere il mestiere. Non potete immaginare quanto mi fa incazzare
trovare per caso, su un libro dedicato a chi comincia a studiare C++ da
zero, un esercizio che non riesco ad immaginare come risolvere. Farei meglio
a darmi una calmata ( just joking ). Veniamo al punto.
In questo esercizio è richiesto di implementare un programma per eseguire
le quattro operazioni aritmetiche di base (+,-,*,/) più il modulo (%) su
numeri molto grandi sia interi che a virgola mobile. Non ho avuto problemi
ad immaginare strutture dati ( semplici stacks e arrayes ) e algoritmi per
le prime tre. Invece non so come fare per la divisione e il modulo.
C'è qualcuno li fuori con qualche idea?
Grazie in anticipo a tutti quelli che risponderanno.
FabioMDF
	987654321987654321987654321.987654321 / 123456789123456789.123456789 =
??????
 
--------------------------------
Inviato via 
http://arianna.libero.it/usenet/

 	987654321987654321987654321.987654321 / 123456789123456789.123456789 =
Io partirei pensando a come si fanno le divisioni con carta e penna.
Ciao,
Nicola

                    Il 12 Ago 2004, 09:32, Nicola....@ObjectWay.it (Nicola Musatti) ha
scritto:

Ti assicuro che con carta e penna sono capace di estrarre il risultato. Ma
questo non mi aiuta.
Il metodo che conosco necessita di considerare il divisore come un unico
ente non scomponibile:
	200 | 10
	20 ------
        ==0 20
	     0
             =
Non posso trattare ( almeno credo ) il 10 della divisione di sopra se non
nella sua interezza. E se al posto del 10 ci fosse il fatidico "very large
number" ? Intendo dire che non sarebbe un problema fare la divisione di un
dividendo molto grande purchè almeno il divisore sia un intero abbastanza
piccolo da entrare in un "long".
Comunque mi aiuti a capire cosa mi sfugge?
Grazie e ciao,
FabioMDF


 piccolo da entrare in un "long".
Beh, se capisco bene vuoi avere il numero 1658 come [1][6][5][8] dove ogni
[] e' un elemento di un array o lista di digits. Ok, questo e' un modo
semplice di fare calcoli con numeri di dimensione arbitraria ma e' poco
efficiente.
Ad ogni modo:
446002 / 1658
1658 = 4 digits quindi prendo 4460
guardo se 1658 e' piu' piccolo di 4460 se e' piu' grande prendo 44600, ma in
questo caso basta 4460.
provo 1658 * 2 = 3316 che e' piu' piccolo di 4460 quindi provo * 3  che e'
4974 che e' piu' grande quindi l'ultimo moltiplicatore valido e' 2.
1658 * 2 = 3316, ora 4460 - 3316 = 1144 [per ora abbiamo 2......]
ora abbiamo 1144 e 02 prendiamo lo 0.
1144 e' 4 cifre come 1658 ma 1658 >1144 quindi prendiamo lo 0 del 02 che
rimane:
11440 / 1658 =
1658 * 2 = 3316 e' minore di 11440, 1658 * 3 = 4974 e' pure minore .....
1658 * 6 = 9948 e' minore, 1658 * 7 = 11606 e' maggiore, quindi uso 6. [per
ora abbiamo 26.....]
11440 - 9948 = 1492
1492 e' di 4 cifre ma minore di 1658 quindi aggiungo il 2, ultima cifra
rimasta!
14922 / 1658 =
1658 * 2 = 3316 e' minore di 11440, 1658 * 3 = 4974 e' pure minore .....
1658 * 9 = 14922 e' esattamente uguale quindi prendiamo 9.
[per ora abbiamo 269....]
14922-14922 = 0 beh, possiamo terminare e' esattamente 269.
se ci fosse stato un piccolo resto tipo 2, allora visto che non abbiamo piu'
numeri da aggiungerci rimasti mettiamo la virgola ed andiamo avanti
aggiungendo zeri....
in questo caso 446002 / 1658 fa proprio 269, quindi non serve andare a
mettere la virgola.
Come puoi notare il processo e' lungo, ma questo e' il metodo scolastico, un
metodo che si addice bene alla tua struttura dati....
Tieni conto che se vuoi fare qualche cosa di veloce ed efficiente allora
devi cambiare struttura dati.
Tommy

 efficiente.
E perchè non lavorare in aritmetica "sizeof(long int)-aria"?

 Tommy
Ciao,


alberto ha scritto:

Cioè, tipicamente, aritmetica a base 4? :-)
Forse volevi dire aritmetmetica "~(unsigned long)0+1"-aria. O, più
semplicemente, aritmetica "ULONG_MAX"-aria.
--
Cingar
P.S. È il mio primo post. Ciao a tutto il NG.


 [...] O, più semplicemente, aritmetica "ULONG_MAX"-aria.
Cioè, pardon, "ULONG_MAX+1"-aria.
--
Cingar


 risolto.
E' proprio per questo che ti ho voluto far vedere come si faceva...
Buon divertimento.
Tommy

 Tommy
Buon divertimento anche a te.
FabioMDF
P.S. Già che ci siamo, conosci anche qualche open source library per lo
studio (minimi, massimi, asintoti, etc.) e la visualizzazione di grafici di
funzioni di più variabili in 2/3 dim.?


 funzioni di più variabili in 2/3 dim.?
Ovviamente in C/C++, ma anche in Ada.
Grazie,
Fabio


 le prime tre. Invece non so come fare per la divisione e il modulo.
Be sull'appendice del Patterson Hannessy ce un capitolo dedicato
alla computer artimetich lo trovi anche al
http://www.mkp.com/CA3