backup del Post

Uno dei blog di .mau.

10/05/2012 Uncategorized ,

Basi di numerazione frazionarie

Abbiamo visto che sono state proposte, ed effettivamente usate, basi di numerazione non standard: la base 3 bilanciata e la base -2. Entrambe le basi avevano qualche vantaggio informatico, ma alla fine un confronto costi/benefici ha fatto pendere la bilancia sull’architettura attuale. Ma per l’appunto stavo parlando di informatica, che per quanto teorica possa essere è una scienza che ha pur sempre un fondamento pratico: i matematici non si curano di queste cose, e si sono inventati basi di numerazione di tutti i tipi. Stavolta parlerò delle basi frazionarie.

Ricordate la differenza tra frazione propria, impropria e apparente? Credo la si impari alle elementari e la si dimentichi nelle scuole medie: una frazione m/n è propria se m < n, impropria se m > n e apparente se m è un multiplo di n e quindi la “frazione” è in realtà un numero intero.

Bene. Un sistema di numerazione in base frazionaria non può usare una frazione apparente, perché in realtà si avrebbe un numero intero. Potrebbe usare una frazione propria, ma ci sarebbero delle difficoltà pratiche, considerando che per ottenere numeri maggiori di 1 saremmo costretti a usare cifre a destra della virgola. Restano insomma solo i numeri in base frazionaria impropria. Questo articolo di Billy Dorminy (all’epoca quindicenne…), oltre ad accennare ad altri tipi di basi di numerazione, specifica come A. J. Kempner nel 1936 trattò anche le basi frazionarie oltre ai numeri negabinari.

Il maggior problema che si ha con le basi frazionarie è riuscire a rappresentare un numero intero. Prendiamo la base più semplice, la 3/2, e cerchiamo di scrivere 2 come faremmo con una base intera. Abbiamo come cifre disponibili “0” e “1”. Il numero 2 è maggiore di “10” , cioè 3/2, e minore di “11”, cioè 5/2; quindi è un numero frazionario: ammetterete che non è una bella cosa… Peggio ancora, non è nemmeno detto che la rappresentazione di un numero sia unica. Sì, questo capita anche con i numeri usuali: a scuola abbiamo studiato come 0,9999… è un altro modo per scrivere 1. Ma qua è più complicato, come si direbbe su Facebook: ho come il sospetto che ci siano infinite rappresentazioni di 1, prendendo opportuni sottoinsiemi delle potenze di 2/3 (cioè 3/2-1, cioè le cifre alla destra della virgola). Magari prima o poi lo dimostro anche, se non ho nulla di meglio da fare…

La soluzione pratica per avere numeri interi che assomiglino a numeri interi è cambiare completamente metodo di definizione delle cifre. Naturalmente rimane la definizione di base di una base (pessimo gioco di parole); ogni cifra “tremezzale” è da moltiplicare per la potenza necessaria di 3/2. Però usiamo come cifre a disposizione tutte quelle fino a un’unità meno del numeratore della base, quindi nel nostro caso 0, 1 e 2. Pertanto 2 si scriverà “2”; 3, invece, avrà due cifre e sarà “20” (3/2×2=3, no?). Proseguendo, abbiamo 4=”21″, 5=”22″. E 6? Ci vogliono tre cifre, ovviamente, mentre il primo numero che ha bisogno di quattro cifre per essere rappresentato è il 9. Si può ingenuamente pensare che ogni aumento di tre unità serva una nuova cifra, ma non è così: il più piccolo numero di cinque cifre è 15 e il più piccolo di sei cifre è 24.

Per convertire un numero da base 10 a base 3/2, o in generale a una qualunque base frazionaria, il sistema più semplice consiste nell’andare da destra a sinistra, eliminando man mano i numeri superiori a 3. Prendiamo un numero a caso, 42, e vediamo come si fa. Prepariamo tante caselle, in questo modo:
      | | | | | | | 42 |
A ogni casella corrisponderà una cifra. 42 è maggiore di 3 che è il numeratore della base, quindi togliamo da esso tutti i multipli di 3, lasciando uno zero, e li portiamo a sinistra, moltiplicandoli per 2 che è il denominatore. Abbiamo così
     | | | | | | 28 | 0 |
Continuiamo così: 28=9×3+1 il che ci porta a
     | | | | | 18 | 1 | 0 |
con i prossimi passi che sono
     | | | | 12 | 0 | 1 | 0 |
     | | | 8 | 0 | 0 | 1 | 0 |
     | | 4 | 2 | 0 | 0 | 1 | 0 |
     | 2 | 1 | 2 | 0 | 0 | 1 | 0 |
Abbiamo così che 42=”2120010″. Bah.

Per come funziona l’algoritmo dovrebbe esservi chiaro che tranne nel caso di 1 tutti i numeri interi iniziano per 2. Ci sono altre proprietà interessanti da considerare? Boh. Dorminy ha trovato una formula ricorsiva per il numero di cifre della rappresentazione in base a/b di un intero, e ha anche proposto un sistema di crittografia che consiste nel codificare per esempio in base 27/2 il testo dove alle ventisei lettere dell’alfabeto è sostituita la coppia di cifre 01, 02, … 26 e allo spazio la coppia 00. Diciamo che non userei questo sistema per codificare nulla di importante, ma sicuramente è qualcosa di carino da provare.

Potete comunque sempre divertirvi a trovare nuove proprietà delle basi frazionarie e scriverci su un articolo… vi lascio volentieri la fama!

Leave a comment

This site uses Akismet to reduce spam. Learn how your comment data is processed.