Newsgroup: it.scienza.informatica
Titolo: numero intergalattico

 precisione arbitraria del PHP (BC)

 La domanda č questa: devo credergli? Si possono gestire tali numeri su un


 normale?
Ritengo sia assolutamente credibile , anzi ritengo quasi incredibile che la 
maggior parte dei calcoli effettuati con i Pc usino numeri limitati dalla 
macchina (32 bit per esempio).
Alla fine questo numero occupa solamente 20 Kb .


 
Un numero decimale in base dell'ordine di 10^n è rappresentabile con n+1
cifre decimali o con circa (3,322*n)+1 cifre binarie (dalle proprietà dei
logaritmi. In questo caso l'ordine di grandezza e' (per eccesso) 21000,
per cui le cifre binarie per rappresentare un numero del genere sono
(sempre per eccesso) 70000, ovvero 70000bit = 8750byte = 8.55kB
Direi che è tranquillamente maneggiabile da un normale pc, le prestazioni
che si possono ottenere per eseguire calcoli su tali numeri variano
ovviamente dalla macchina, dagli algoritmi utilizzati e dalle operazioni
stesse.
ciao.
Matteo
-- 
Matteo Moro - mBG on #gemona@IRCNet
Web Personale - 
www.MatteoMoro.net
ICQ#: 91902715, JID: 
emme...@jabber.linux.it

 normale?
Certo. Per controllare il suo risultato (l'aveva postato proditoriamente
come allegato su it.hobby.enigmi) ho scritto un programmino
in C usando la libreria GMP della gnu per i calcoli in precisione
multipla. Tempo di scrittura del programma = 1 minuto,
tempo di esecuzione su un Athlon 1400 = 1 decimo di secondo.
ciao,
g.
-- 
AIUTARE= Accrescere il numero degli ingrati
(Ambrose Bierce, Il Dizionario del Diavolo)

 Alla fine questo numero occupa solamente 20 Kb .
Rispondo qui, ma è come se rispondessi a tutti.
Avete ragione, la potenza dei pc va molto oltre, il fatto è che sono
abituato a int (8 bit) e al max long(64 bit). Qui ci vogliono strutture in
grado di gestire numeri rappresentati con decine di migliaia di bit. Non
ero completamente a conoscenza di queste librerie. Per questo.
Grazie della risposta. Ciao
P.S. il tizio in questione non parla dell'algoritmo, ma non credo abbia
adottato il calcolo ricorsivo (sarebbe assurdo, credo).

Un problema simile si presenta quando si cerca di calcolare il
piu' grande numero primo:
http://www.newscientist.com/news/news.jsp?id=ns99994438
 Raffaello

 adottato il calcolo ricorsivo (sarebbe assurdo, credo).
Sarebbe assurdo se non l'avesse usato...
Uno dei metodi piu' semplici e piu' veloci (non a
caso quello usato nella funzione mpz_fib_ui della
libreria gmp, e' ricorsivo.
Ovviamente non si tratta del metodo f(n+1)=f(n)+f(n-1)
che e' molto piu' lento.
Ecco il metodo (molto noto) usato da gmp:
Prima di tutto una tabella precalcolata per i
valori piu' piccoli, poi:
The formulas used are
      F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k
      F[2k-1] =   F[k]^2 + F[k-1]^2
      F[2k] = F[2k+1] - F[2k-1]
    At each step, k is the high b bits of n.  If the next bit of n is 0
then F[2k],F[2k-1] is used, or if it's a 1 then F[2k+1],F[2k] is used,
and the process repeated until all bits of n are incorporated.  Notice
these formulas require just two squares per bit of n.
Chiaramente c'e' la ricorsione, ma grosso modo ad ogni
passo l'indice si dimezza. Per questo
il calcolo di f(10000) non mi ha preso piu' di un decimo
di secondo su una CPU vecchiotta.
ciao.


 Sarebbe assurdo se non l'avesse usato...
Io intendevo il metodo ricorsivo che si rifà alla definizione della
funzione.
Cmq grazie, interessante questo metodo.