Newsgroup: it.scienza.informatica
Titolo: Conversioni e potenze

Salve,
vi scrivo per sapere se esiste un metodo matematico (diverso da quello
classico) per trasformare da decimale a binario e viceversa.
Vi spiego meglio il problema.
Vorrei dichiarare un tipo di dato intero un po' insolito in grado di
lavorare con cifre mostruose (256 bit).
Se ho una sequenza binaria a n bit la formula per trasformare in decimale
tale sequenza è:
2^0 + 2^1 + ..... + 2^(n-1)
e vale se tutti i bit valgono 1, altrimenti per quelli che valgono 0 non
considero la potenza.
Ma questa formula può risultare utile quando i bit sono pochi ed il numero
dell' ultima potenza ( 2^ (n-1) ) non è enorme.
Visto che i bit sono 256, mi trovo che l' ultima potenza è ( 2^255 ) vale a
dire un numero non molto semplice da gestire.
Allora vi chiedo:
esiste un metodo diverso per fare un' operazione simile ? (magari
scomponendo il numero in più parti e lavorando con potenze piccole.....non
so !! )
La stessa domanda vale anche per trasformare un numero decimale enorme
(dell' ordine di 80 cifre minimo ) in un numero binario.
Grazie per le risposte......
Saluti...
Antonio Tarolla

Salve
perche' non passi ai log in base 2?
Cheers 
Yuri

 (dell' ordine di 80 cifre minimo ) in un numero binario.
Il primo problema che devi risolvere e' come rappresentare i numeri. Mi
sembra evidente che se vuoi rappresentare in forma decimale numeri da 256
bits  *senza perdere precisione*  dovrai utilizzare numeri decimali da 77
cifre. Cosi' se vuoi rappresentare in forma binaria numeri decimali di 80
cifre dovrai utilizzare circa 270 bits.
Se accetti di pedere precisione allora puoi utilizzare rappresentazioni
floating point in cui sostanzialmente puoi scegliere indipendentemente la
precisione ed il range di numeri rappresentabili.
Una volta che hai un modo di rappresentare il numero, devi disporre di
programmi aritmetici che operano sui numeri nella rappresentazione che
usi. 
Per farti un esempio in unix esiste un "valutatore di espressioni" a
precisione infinita (limitata ovviamente dalla lunghezza delle stringhe
decimali che ottineni):
 bc - An arbitrary precision calculator language
DESCRIPTION
       bc is a language that supports arbitrary precision numbers
       with interactive execution of statements.
							l.f.
--------------------------------------------------------------------------
       -- )     Luca Fini                            Tel: +39 055 2752 307
 ___    |\      Osservatorio Astrofisico di Arcetri  Fax: +39 055 2752 292
/   |   | |-_   L.go E.Fermi, 5 +-----------------------------------------
(___|___//___)  50125 Firenze  /   WWW: 
http://www.arcetri.astro.it/~lfini
 (_)      (_)   Italia        / e-mail: 
lf...@arcetri.astro.it
-----------------------------+--------------------------------------------
                              In a world without fences - who needs GATES?

perche' non passi ai log in base 2?
cioè cosa vorresti fare di preciso ?
Magari riporta un esempio semplice.
Ti saluto....a presto !!
Antonio Tarolla
BSSoftware Tips Mailing - List Support

Salve
tempo fa ho postato il suggerimento di passare ai logaritmi in base due
e giustamente mi e' stato chiesto di essere piu' preciso. Confesso di non 
avere le idee chiare e che la mia era piu' una intuizione che altro ma
un esempio dell'uso del log x al posto di x lo si trova nel caso dell'uso
dei dB per rappresentare segnali, fdt di filtri e/o quadriupoli e altro.
Non ho ben capito l'ambito di applicazione dei "numeroni" ma essendo la
loro grandezza un problema lo si puo' affrontare in questo modo.
Cheers
Yuri

Allora,
non specifichi quale ambiente (s.o./linguaggio) vorresti usare,
quindi non mi sono chiari i vincoli che devi rispettare.
Se ti interessa manipolare numeri di grande dimensione e usi
il linguaggio c, allora puoi scaricarti le librerie
gmp dello gnu che sono free e vanno benissimo e fanno
tutto quello che vuoi e anche di piu'.
Se invece vuoi (o devi...) reiventare la ruota, allora
ti posso suggerire questo sistema che non e' sicuramente
il migliore ma e' il primo che mi viene in mente,
cosi' su due piedi.
Richiede un po' di precalcolo, fatto una volta sola.
Allora:
supponiamo che tu abbia questo numero da 256 bits,
che ti permette di rappresentare il numero massimo
2^256-1 =
11579208923731619542357098500868790785326998466564056403945758
4007913129639935
che ha (mi sembra...) 78 cifre.
Supponiamo inoltre che tu questo numero lo possa leggere
come 16 gruppi di 16 bit, cioe' come
16 numeri tra 0 e 2^16-1=65535. Cioe', se 
x e' il numero, io suppongo che tu lo possa leggere
come scritto in base 2^16, ovvero composto dalle cifre c[0..15],
in modo tale che 
x=Somma(per i=0,..,15 di c[i]*2^(16i))
Ora per ciascuno dei 16 numeri 
2^(16 i), per i=0,..,15, ti calcoli il numero
e lo rappresenti in decimale con 78 cifre,
e memorizzi le cifre in un vettore v[i][0..77],
in questo modo
2^(16*0)= 1 -> v[0][0]=1 v[0][1]=0 ... v[0][77]=0
2^(16*1)=65526 -> v[1][0]=6 v[1][1]=2 v[1][2]=5 v[1][3]=5
                  v[1][4]=5 v[1][5]=6 v[1][7...77]=0
2^(16*2)=4294967296 ->
v[2][0]=6 v[2][1]=9 v[2][2]=2 v[2][3]=7 etcetc
In modo che per ogni i=0..15, valga
2^(16*i) = somma(j=0..77, v[i][j]*10^j)
Una volta fatto questo precalcolo
(sono solo 16 numeri "lunghi" che ti copio sotto)
Supponi di dover calcolare la rappresentazione
decimale del numero
x = c[0]c[1]c[2]...c[15] (gruppi da 16 bit..)
allora azzeri preliminarmente un
vettore di supporto r[0..77].
poi, per ogni k=0..15 e per ogni j=0..77 fai:
r[j]=r[j]+c[k]*v[k][j];
A questo punto devi normalizzare la rappresentazione
decimale r[..]
e fai cosi':
per ogni k=0..76 (non 77)
r[i+1] = r[i+1]+parte intera inferiore (r[i]/10);
r[i]=r[i] modulo 10;
e per finire hai la tua bella rappresentazione
cifra per cifra in r[0..77].
Spero di essere stato chiaro.
Questo sistema non e' certo il piu' efficiente.
Per esempio puoi migliorarlo facendo una 
conversione preliminare non alla base
10 ma alla base 1000 o 10000 in modo
da dover fare meno calcoli.
In ogni caso con questo metodo,
a parte precalcolare i 16 numeroni, non
hai bisogno di implementare moltiplicazione
o divisione di numeri in precisione multipla.
Ciao.
i numeri 2^(16*i) per i=0..15 sono:
(se ti servono)
{1,65536,4294967296,281474976710656,18446744073709551616,
  1208925819614629174706176,79228162514264337593543950336,
  5192296858534827628530496329220096,
  340282366920938463463374607431768211456,
  22300745198530623141535718272648361505980416,
  1461501637330902918203684832716283019655932542976,
  95780971304118053647396689196894323976171195136475136,
  6277101735386680763835789423207666416102355444464034512896,
  411376139330301510538742295639337626245683966408394965837152256,
  269599466671506397946670150870196306736371444225405724 - a capo
            81103610249216,
  176684706477838432958329750074291851582748389687561895 - a capo
            8121606201292619776}