Displaying items by tag: elfin

Come fa il computer a codificare i numeri reali e come si potrebbero estendere e potenziare gli standard attuali, arrivando anche a manipolare numeri "quasi infiniti"? 1) Introduzione Il metodo usato dai computer o dalle calcolatrici scientifiche per rappresentare numeri decimali è chiamato "formato in virgola mobile" o “Floating Point Format” (FPF) e ricalca quello usato nella cosiddetta "notazione scientifica", insegnata anche nelle scuole medie e superiori. Vedremo in dettaglio come è fatto e che cosa si potrebbe fare per migliorarlo ulteriormente. Il formato FPF, così come viene definito nello standard IEEE 754, è costituito da tre porzioni: un campo segno s un campo significando o mantissa o frazione m; un campo esponente e. Dato che esso è concepito per essere usato in dispositivi digitali a linguaggio binario (0 e 1), tutti i campi suddetti sono espressi da cifre binarie (bit); indicheremo con dm il numero di bit nella mantissa e de quello nell'esponente, mentre s richiede solo 1 bit. Nel FPF, un numero reale N viene quindi implicitamente rappresentato nel modo seguente: N = (-1)s · m · 2e Se il numero N è inferiore a 1, il valore di e deve essere negativo e questo si ottiene sottraendo un "bias" pari a 2(de-1)-1. Inoltre, nel rappresentare la mantissa m si ricorre ad un sotterfugio chiamato "hidden bit" (bit implicito o nascosto) per risparmiare 1 bit dando per sottinteso che la prima cifra binaria della mantissa che precede la virgola sia sempre pari a 1. Il numero più grande e quello più piccolo che possono essere codificati saranno allora dati dalle seguenti espressioni binarie: Nmin = (1,000...) · (2-(de-1)+2) ; Nmax = (1,111...) · (2(de-1)-1) (qui per ora ho messo da parte il segno, omettendo anche di parlare della presenza di numeri "denormalizzati" e delle combinazioni che codificano i valori ±∞). Per passare dalla rappresentazione binaria a quella scientifica normalmente usata da noi umani, entrambi i campi vanno naturalmente convertiti dal formato binario a quello decimale e in tal caso li indicheremo con M ed E. Perciò, indicando la costante di proporzionalità k=log10(2)≈0.301, necessaria per passare da un sistema a base 2 a quello in base 10, il numero di cifre decimali disponibili per la mantissa (dM e dE rispettivamente) sono dati da: dM = int [ k·(m+1) ] ; dE = int [ k·2(e-1)] . I 3 formati di virgola mobile ufficialmente formalizzati e universalmente adottati ad oggi sono i seguenti: Singola precisione: 32 bit suddivisi in 24 bit di mantissa e 8 di esponente→precisione di 7 cifre decimali (con margine minimo) e valori compresi tra 1,18·10-38 e 3,40·1038 ; Doppia precisione: 64 bit suddivisi in 53 bit di mantissa e 11 di esponente→precisione di oltre 15 cifre decimali (quasi 16) e valori compresi tra 2,22·10-308 e 1,80·10308 ; Quadrupla precisione: 128 suddivisi in 113 bit di mantissa + 15 di esponente→precisione di 34 cifre decimali (senza margine) e valori compresi tra 2,97·10-4931 e 1,19·104932 ; In realtà lo standard IEE754 prevede anche una "mezza precisione" a 16 bit che però ha grosse limitazioni pratiche ed un valore prevalentemente didattico (ci torneremo tra poco). In pratica, nei moderni computer viene generalmente utilizzato solo il formato "doppia precisione" a 64 bit mentre gli altri due sono rivolti solo ad applicazioni e ambiti particolari; effettivamente, la doppia precisione offre già una accuratezza e un esponente sovrabbondanti poichè, anche nei calcoli più accurati, sono richieste al massimo 11 o 12 cifre significative (questo è infatti il livello di precisione raggiunto nella misura delle costanti fisiche fondamentali meglio conosciute, come quella di Rydberg o quella di struttura fine). Inoltre, la scelta di dedicare 53 bit alla mantissa implica uno "spreco di precisione" perché corrisponde a 15.95 cifre decimali e quindi, anche se siamo vicinissimi a 16 cifre significative, la precisione dei risultati è garantita solo fino alla quindicesima cifra! 2) Estensione e modifica dei formati Sulla base di queste considerazioni, ho deciso di stilare la seguente tabella di possibili FPF che potrebbero riempire i "vuoti" tra gli standard esistenti, estendendoli sia verso il basso che verso l'alto e correggendo leggermente i sistemi a doppia e quadrupla precisione per ottimizzarne le prestazioni in termini di precisione e di esponente massimo. Tabella 1 : Proposta di estensione e modifica degli FPF attuali Come si vede nella tabella, passando tra i vari formati il numero di cifre decimali significative va da 3 a 300 e il margine di tale precisione (la sua parte frazionaria) tende a 0.7 cifre decimali per gli standard più elevati; questo può essere considerato un valore ideale perché garantisce un ampio margine di precisione sull'ultima cifra visualizzata evitando sia lo "spreco" di bit che si commette nel caso della mantissa della doppia precisione tradizionale, sia l'errore opposto di un'assenza di margine sulla precisione quadrupla. Il quinto formato P è definito "ottimale" poiché dovrebbe soddisfare le esigenze della stragrande maggioranza delle applicazioni*; quelli a precisione molto bassa potrebbero essere impiegati in applicazioni "particolari" (ad esempio per descrivere la luminosità dei pixel in immagini HDR), mentre quelli ad alta precisione sono per applicazioni prettamente matematiche. Una annotazione: per la precisione "ottupla" si potrebbe optare anche per una mantissa di 238 bit, garantendo una precisione di 71 cifre significative (con margine di 0.65) e un esponente massimo di circa ±39450. 3) Oltre la virgola mobile Studiando lo standard IEEE 754 si scopre che, oltre a codificare numeri in virgola mobile veri e propri, il formato prevede anche dei numeri “denormalizzati” (cioè numeri piccoli a “virgola fissa” per evitare problemi di arrotondamento) e valori non numerici indicati come NaN (Not a Number); i primi corrispondono a un valore nullo dell'esponente mentre i secondi appaiono quando il campo E assume il valore massimo1. L'uso dei codici NaN, sebbene sicuramente utile, rappresenta uno spreco dal punto di vista della rappresentazione numerica, soprattutto nei formati floating a molti bit2. Consideriamo a questo proposito il formato tradizionale “doppia precisione” a scopo esemplificativo; la corrispondente ripartizione dei bit è schematizzata qui in basso: Gli 11 bit dedicati all'esponente (segno compreso) implicano che, quando l'esponente assume il valore massimo (cioè 1023), rimangono ben 53 bit tra mantissa e segno, corrispondenti a quasi 1016 combinazioni diverse (precisamente 9007199254740988 combinazioni, escludendo ±∞): francamente troppe per codificare delle situazioni anomale! In realtà, c'è chi ha proposto di utilizzare un sottoinsieme dei NaN (quello dei “signaling NaN” - sNaN) per codificare numeri con precisione più alta oppure numeri complessi. Qui considero appunto una alternativa di questo tipo, in cui i primi 2 dei suddetti 53 bit (li chiameremo “option bit”) vengono utilizzati per indicare una delle seguenti alternative: option bit significato dei successivi 51 bit 11 si tratta di un vero NaN (con ulteriori sottocategorie interne) 01 si tratta di un numero razionale, codificato in formato “floating slash” 10 è un “variable exponent” e/o un “esponenziale generalizzato” (“superfloat”) 00 si tratta di un numero complesso (2 mantisse con esponente comune) Tabella 2: nuovi domini proposti all'interno dei NaN tradizionali Il bit per il segno continua a essere presente con lo stesso significato nei due casi intermedi, dunque i bit utili per il valore assoluto sono esattamente 50, rappresentati in verde nello schema in basso (si noti che adesso gli 11 bit dell'esponente sono necessariamente uguali a 1 e quindi “non sfruttabili”): 1: Come casi particolari, quando il significando/mantissa vale zero si hanno i valori ±∞. 2: Del resto l'utilità e l'attualità dei codici di errore NaN è dubbia ed è oggetto di discussione nella definizione del nuovo standard IEEE_754r 4) Numeri Razionali: il "Floating Slash" Questo formato, proposto da Matula1, consiste nel codificare un numero razionale in una parola di lunghezza finita ma con una ripartizione variabile tra numeratore e denominatore, tramite un indicatore di posizione (“slash position field”). Nel nostro caso, i 50 bit disponibili si suddividerebbero in 6 bit per la “slash position” e i rimanenti 44 per la frazione vera e propria. L'uso di 6 bit consente, come già suggerito da Matula, di avere uno slash che cade anche leggermente al di fuori del campo contenente la frazione, codificando così numeri interi o i loro reciproci in maniera esatta; si tratterebbe, comunque, solo dei multipli delle potenze di due (2,4,8..,128) poiché i bit meno significativi non sono esplicitati e vengono posti uguali a zero. Un ulteriore affinamento di questo formato potrebbe consistere nell'avere solo frazioni ridotte ai minimi termini, massimizzando l'efficienza ed evitando ridondanze; se questo dovesse risultare troppo oneroso in termini di elaborazione, si potrebbero almeno escludere, tra i possibili valori del numeratore, tutti i multipli del denominatore, in maniera da eliminare i numeri interi già codificati da una “slash position” elevata (>44). Inoltre, ovviamente, il valore minimo di numeratore e denominatore deve essere 1 e non zero poiché lo zero e l'infinito sono già contenuti nella codifica floating tradizionale. Ricapitolando, la codifica dovrebbe rispettare il seguente schema con tre diversi "domini": Tabella 3: i domini all'interno del "floating slash" Il grafico sottostante fornisce una rappresentazione di come sono ripartiti i 50 bit disponibili e, nella parte bassa, vengono riportati tre esempi corrispondenti alle tre situazioni elencate nella tabella; si tenga presente che la posizione dello slash (in rosso) è calcolata sottraendo dal valore riportato nel campo “slash position” il bias -10: Naturalmente, n e d indicano il bit generico rispettivamente per numeratore e denominatore mentre quelli nelle caselle semitrasparenti sono valori sottintesi e non modificabili, un po' come l'”hidden bit” del formato floating tradizionale. Questa codifica è migliorabile in molti punti. Alla già citata “ridondanza” dovuta all'eventuale presenza di frazioni non ridotte, c'è da aggiungere la possibilità di scrivere in molti modi le frazioni più semplici, quelle dove la somma di cifre per numeratore+denominatore è inferiore a 44 bit; infatti, in questi casi la posizione dello slash può essere fatta variare in modo arbitrario in un certo intervallo senza che il risultato cambi e questo implica un ulteriore spreco di combinazioni ovvero di informazione. Infine, l'uso di “zero impliciti” nei casi (a) e (b) è alquanto arbitrario e privilegia la base 2 rispetto ad altri sistemi numerici. E' ovvio che codifiche più efficienti possono eliminare questi limiti, al costo però di una complicazione dell'algoritmo di conversione. 1D. Matula - “Fixed slash and floating slash arithmetic” 5) Numeri Grandi: l'esponente a lunghezza variabile Questo è un formato di mia creazione, realizzato per rappresentare numeri molto grandi sulla falsariga del sistema “floating slash” del paragrafo precedente. Dati i 50 bit di valore assoluto disponibili, si dedicano 5 di essi al campo “exponent lenght” λ il cui valore può quindi andare da 1 a 32; questo campo esprime il numero dei bit che vengono dedicati all'esponente, mentre alla mantissa vengono dedicati i rimanenti 45-λ bit. La struttura dei 50 bit è quella sottostante: In realtà, dato che un esponente di 11 bit è già presente nel formato classico a doppia precisione, è opportuno far partire il valore e dell'esponente da 2^(11-1)-1=1023; di conseguenza, in formato binario, per λ=1 l'esponente “floating” andrà da un minimo di 1024 a un massimo di di 1025 (a seconda che il bit #44 valga 0 oppure 1); per λ=2, sempre per non ripetere esponenti già utilizzati, 1026 < e < 1029; poi, λ=3 → 1030 < e < 1037 e così via. Alla fine, per λ=32, avremo 4294968318 < e < 8589935613 ovvero l'esponente massimo è pari a 233+1021 (2585828280 ≈ 2,6 miliardi in formato decimale). Per contro, la mantissa si riduce progressivamente da 44 a 13 bit, ovvero da 13 a poco meno di 4 cifre decimali significative. Il grafico sottostante visualizza l'andamento del range per l'esponente e della precisione al variare di λ (ascisse); si noti che la scala relativa agli esponenti è a sua volta logaritmica mentre per le cifre decimali la scala è quella a destra. I due triangoli si riferiscono al sistema in doppia precisione classico. Come si vede, per λ=22, la precisione è la stessa del sistema floating-32 ma con un esponente massimo che supera gli 8 milioni! Il valore più grande codificato è, per la precisione, pari a: 1,9999•28589935613= 4.327e+2585828280. 6) Numeri Grandissimi: Esponenziale Generalizzato Quello dell' “esponente variabile” è già un risultato notevole ma, volendo, può essere ulteriormente spinto verso numeri "grandissimi" ricorrendo ad una ricursione dell'elevamento a potenza, come previsto dal formato proposto da Clenshaw e Olver1. L'esponenziale generalizzato fa uso di due campi, un intero l chiamato “livello” (che indica l'ordine di elevamento a potenza) e una “radice” a che è un numero reale (con 0<a<1 nella versione normalizzata che qui useremo); in questa rappresentazione, la coppia [l/a] corrisponde al numero seguente: dove il numero di elevamenti a potenza è appunto uguale a l. In sostanza, l e a possono essere viste rispettivamente come la parte intera e la parte frazionaria di un numero y, rappresentabile come un numero a virgola fissa. L'utilizzo di e (base dei logaritmi naturali) come base può sembrare inopportuno in un computer, tuttavia rispetto alla base 2 presenta il vantaggio di rendere continua la derivata prima della funzione che descrive la x, evitando quindi bruschi salti nel livello di precisione relativa. Questa funzione parte con una crescita molto contenuta (di fatto Y=x per Y 4, la crescita diventa vertiginosa: per Y≈4,6322 si raggiunge 224-1 (ovvero ~1,798E308 che è il valore massimo per il formato floating64), mentre per Y=5,2 si è già superato il valore massimo di 101E12 indicato nel paragrafo precedente per il “super-floating”; per Y=6 siamo già ad uno “stellare” ≈1010^1657000. A questo punto, è chiaro che per codificare numeri grandissimi sono sufficienti pochi valori di l; se ad esempio imponiamo l<8 (codificandolo con 3 bit e usando un bias=1), riusciamo ad utilizzare i rimanenti 47 bit per la radice, mantenendo dunque una precisione numerica ragguardevole, almeno per l=1; nei livelli successivi, chiaramente, la precisione degrada drasticamente e può divenire addirittura maggiore del valore cui si riferisce; di conseguenza questa codifica, sebbene ideale per rappresentare numeri estremamente grandi, fornisce solo il loro ordine di grandezza (anzi, la generalizzazione dell'ordine di grandezza!) e il suo utilizzo risulta estremamente limitato. Per questo motivo, è preferibile il sistema dell'esponente variabile, al limite implementando un esponenziale generalizzato al suo interno, come fosse un codice NaN; questa opzione viene illustrata in dettaglio al paragrafo successivo. 1 C. W. CLENSHAW F. W. J. OLVER, "Beyond Floating Point”; Journal of the Association for Computing Machinery, Vol. 31, No. 2, April 1984, pp. 319-328. 7) Il "SUPERFLOATING" Questa opzione unisce le precedenti due, in modo da rappresentare sia numeri molto grandi con una precisione ragionevole, sia “numeri grandissimi” la cui scrittura è di fatto impossibile con la normale notazione scientifica. Per i primi si utilizza il meccanismo del “variable exponent”, con una piccola modifica del tipo NaN sul valore di esponente più alto; quando esso vale 233+1021, allora il significato della mantissa lunga 13 bit è quello di un esponente generalizzato con 3 bit per l'indice e 10 per la radice, come mostrato qui sotto: Naturalmente, per evitare ridondanze e avere una qualche continuità di precisione, è bene che l parta da 1 e che l'esponente generalizzato sia moltiplicato per il valore massimo del “variable exponent” ovvero 28589935613. Ne segue che la precisione, inizialmente equivalente a 3 cifre significative (0,1%) decade al 100% per Y=4,4248 (corrispondente alla codifica #3507); questo significa che tra due valori consecutivi di X c'è un fattore 2 (da 1,55 a 3,1e+2585828324). Poco dopo, l'errore sale al 1000% per Y=4,5361 (combinazione #3621); chiaramente, da questo punto in poi, la rappresentazione della mantissa non ha più alcun senso e anche l'esponente è solo approssimativo. Il valore decodificato più grande che sono riuscito a calcolare tramite il “Big Online Caculator” è quello corrispondente alla codifica #4754 (Y=5,6426) ed è già abbastanza "spaventoso": ≈5,57E+832506912334751785648574585136932151816327901696019923466434419527421641430783 ovvero circa 108,3E+75; la differenza rispetto all'elemento precedente (codifica #4753) è un fattore 2,4 sull'esponente o, se si preferisce, sul logaritmo! Si capisce che la codifica diventa estremamente “rarefatta” e l'utilità di questo sistema sta solo nel fornire l'ordine di grandezza dell'esponente (detto in altre parole, l'esponente dell'esponente oppure l'ordine di grandezza dell'ordine di grandezza!). Tutto questo avviene a poco più di metà strada nell'elenco delle possibili combinazioni: risulta quindi davvero difficile immaginare il numero corrispondente alla codifica più alta, la #8192, corrispondente a Y=8,999; si tratterebbe di un numero dell'ordine di . 8) Numeri Complessi Questa è l'unica opzione per la quale la lunghezza di 51 bit risulta un po' “sacrificata”, poiché è necessario “stivare” in questo spazio due numeri floating necessariamente poco precisi. Per risparmiare un po' di spazio, una buona idea è quella di avere un esponente condiviso tra la parte reale e immaginaria, magari costituito da un numero dispari di bit in modo da avere lo spazio rimanente equamente diviso tra le due mantisse. A mio parere, la soluzione più ragionevole è quella di avere 9 bit per l'esponente comune e 21 bit per ciascuna mantissa, in modo da ottenere una precisione di 6 cifre decimali (con un margine di 0,32 cifre) e un esponente massimo di ±76, come mostrato di seguito: L'alternativa di usare 11 bit per l'esponente è allettante poiché sarebbe uguale alla lunghezza normalmente usata per i numeri reali in doppia precisione; tuttavia, il margine di precisione sulle 6 cifre significative della mantissa diventerebbe estremamente ridotto, con il rischio di avere a volte arrotondamenti scorretti. Rispetto all'uso di una coppia di numeri in singola precisione (uno per la parte reale e l'altro per la immaginaria), questa codifica ha il vantaggio di un esponente massimo comunque maggiore, a parità di memoria occupata. In ogni caso, per studi di funzioni sul piano complesso come la Zeta di Riemann o l'insieme di Mandelbrot e di Julia, la precisione sarebbe in genere insufficiente e bisognerebbe ricorrere perlomeno a due numeri "floating-64" separati. 9) Conclusioni Con le varianti qui mostrate, il formato floating-64 diventerebbe davvero potente e versatile: la precisione sarebbe assoluta sui numeri razionali con numeratore/denominatore inferiori a ~1013 mentre il range abbracciato sui numeri reali arriverebbe ben oltre ~1010^9 (anche se con precisione decrescente), oltre alla possibilità di rappresentare numeri complessi. Il tutto senza intaccare il formato di base e mantenendo comunque un elevato numero di combinazioni NaN (oltre 2e15) a scopo diagnostico. Qualcuno potrebbe osservare che queste modifiche ignorano la possibilità di codificare numeri estremamente piccoli, privilegiando solo quelli estremamente grandi. Tuttavia, una simile aggiunta (peraltro facilmente implementabile destinando ad esempio un bit all'operazione di calcolo del reciproco), andrebbe in conflitto con la filosofia dei numeri “denormalizzati” presenti già nel formato classico; in fondo, anche se si tratta di numeri in virgola fissa, questi ultimi sono l'equivalente dei “variable exponent” poiché la precisione relativa si riduce progressivamente andando verso lo zero. Naturalmente, la reale fattibilità di questo nuovo standard è legata alla complessità software e hardware necessari alla sua implementazione, in rapporto al limitato campo di applicazione. Nel caso di una implementazione di antrambe le proposte di modifica presentate (mantissa a 52 bit anziché 53 bit e utilizzo dei NaN), ci sarebbero naturalmente da apportare piccole modifiche numeriche alla trattazione dei paragrafi 3-8, ma senza variazioni sostanziali. Note: * Lo standard a 52 bit è una versione "potenziata" di quello a 48 bit, più ovvio perché esattamente a metà tra 32 e 64 bit. La scelta di 48 bit (con 9 bit di esponente e 39 di mantissa) implica qualche limitazione in più ma riuscirebbe comunque a soddisfare la stragrande maggioranza delle esigenze, poiché garantirebbe una eccellente precisione di 11 cifre decimali significative (con un margine ottimale di 0.74 cifre) e un esponente massimo -77/+76 (eventualmente ampliabile verso l'alto cambiando il bias, in modo da andare da -54 a +99). Va da sé che esso renderebbe superfluo uno standard intermedio a 40 bit, semplificando la tabella (se ne parla ampiamente in questo articolo successivo) Nota1: per l'argomento trattato e per le proposte originali in esso contenute, l'articolo potrebbe benissimo apparire anche nella sezione "Ricreazioni Matematiche" oppure "Appunti di vista"; alla fine si è resa necessaria una scelta, per quanto arbitraria. Nota2: aggiuta, a Dicembre 2018, una nota riguardante la possibile variante FPF 48 bit