Metodo di Horner
Conversione Binario ↔ Decimale
Hands on Stem — Prof. Davide Bertolino
1. Introduzione
Esistono diversi metodi per convertire un numero dalla rappresentazione binaria a quella decimale e viceversa: la notazione posizionale (somma dei pesi), la tabella delle potenze di 2, il double dabble (usato nei circuiti digitali) e il metodo di Horner. Ognuno ha i propri vantaggi e contesti di applicazione.
Perché proprio Horner? In questo articolo scegliamo di approfondire il metodo di Horner perché si riduce a un algoritmo semplice e ripetitivo: le uniche operazioni richieste sono moltiplicare per due e sommare uno (o il valore del bit corrente). Questo lo rende particolarmente adatto a un approccio didattico: è facile da ricordare, facile da eseguire a mano e facile da implementare in un programma. È un approccio forse meno rigoroso dal punto di vista formale rispetto alla notazione posizionale classica, ma decisamente più pratico e immediato per chi si avvicina per la prima volta alle conversioni di base.
Il metodo prende il nome dal matematico britannico William George Horner (1786-1837), sebbene fosse già noto a matematici cinesi e persiani molti secoli prima. Permette di convertire un numero da una base qualsiasi alla base 10 (metodo diretto) e dalla base 10 a una base qualsiasi (metodo inverso). I due procedimenti sono algebricamente simmetrici: uno compone il polinomio posizionale, l’altro lo scompone.
2. Dalla forma classica a Horner
La rappresentazione posizionale di un numero binario a n cifre è:
N = bₙ₋₁·2ⁿ⁻¹ + bₙ₋₂·2ⁿ⁻² + … + b₁·2¹ + b₀·2⁰Questa espressione richiede il calcolo di tutte le potenze di 2. Il metodo di Horner riscrive lo stesso polinomio in forma annidata (nested form):
N = ((…((bₙ₋₁·2 + bₙ₋₂)·2 + bₙ₋₃)·2 + …)·2 + b₁)·2 + b₀Esempio concreto
Convertiamo 110101₂ in decimale:
Classica: 1·2⁵ + 1·2⁴ + 0·2³ + 1·2² + 0·2¹ + 1·2⁰
Horner: ((((1·2 + 1)·2 + 0)·2 + 1)·2 + 0)·2 + 1
La forma di Horner elimina la necessità di calcolare le potenze: serve solo moltiplicare per 2 e sommare, operazione dopo operazione.
3. Horner Diretto: Binario → Decimale
Algoritmo
- Inizializza l’accumulatore ACC con il valore del primo bit (MSB, il più a sinistra).
- Per ogni bit successivo, da sinistra a destra:
ACC = ACC × 2 + bit - Quando tutti i bit sono stati elaborati, ACC contiene il valore decimale.
Esempio passo per passo
Convertire 110101₂:
| Passo | Operazione | ACC |
|---|---|---|
| Start | prendi 1 (MSB) | 1 |
| 1 | 1 × 2 + 1 | 3 |
| 2 | 3 × 2 + 0 | 6 |
| 3 | 6 × 2 + 1 | 13 |
| 4 | 13 × 2 + 0 | 26 |
| 5 | 26 × 2 + 1 | 53 |
Risultato: 110101₂ = 53₁₀
4. Horner Inverso: Decimale → Binario
Algoritmo
- Dividi il numero per 2 e annota il resto.
- Ripeti la divisione con il quoziente ottenuto, fino a raggiungere quoziente 0.
- Leggi i resti dal basso verso l’alto: il primo resto è il LSB, l’ultimo è il MSB.
Esempio passo per passo
Convertire 53₁₀ in binario:
| Passo | Divisione | Quoziente | Resto |
|---|---|---|---|
| 1 | 53 ÷ 2 | 26 | 1 (LSB) |
| 2 | 26 ÷ 2 | 13 | 0 |
| 3 | 13 ÷ 2 | 6 | 1 |
| 4 | 6 ÷ 2 | 3 | 0 |
| 5 | 3 ÷ 2 | 1 | 1 |
| 6 | 1 ÷ 2 | 0 | 1 (MSB) |
Risultato: 53₁₀ = 110101₂ (resti letti dal basso verso l’alto ↑)
5. La simmetria dei due metodi
Il metodo diretto e quello inverso sono operazioni algebricamente simmetriche, come encoding e decoding dello stesso schema polinomiale:
Diretto (Encoding)
- Legge bit da sinistra a destra
- Operazione:
ACC × 2 + bit - Compone il polinomio
- Input: cifre binarie → Output: valore decimale
Inverso (Decoding)
- Produce bit da destra a sinistra
- Operazione:
N ÷ 2, resto = bit - Scompone il polinomio
- Input: valore decimale → Output: cifre binarie
6. Generalizzazione a qualsiasi base
Il metodo di Horner non è limitato alla base 2. Le formule generali sono:
Diretto (base B → decimale): ACC = ACC × B + cifra
Inverso (decimale → base B): N ÷ B → quoziente + resto
Esempi
- Base 8 (Ottale):
357₈ → ((3×8+5)×8+7) = 239₁₀ - Base 16 (Esadecimale):
2A₁₆ → (2×16+10) = 42₁₀ - Base 10 (verifica):
435₁₀ → ((4×10+3)×10+5) = 435₁₀
7. Riepilogo
- ✓ Il metodo di Horner riduce la valutazione di un polinomio a operazioni sequenziali semplici.
- ✓ Diretto: moltiplica l’accumulatore per la base e somma la cifra (da MSB a LSB).
- ✓ Inverso: dividi per la base e raccogli i resti (si leggono in ordine inverso, da LSB a MSB).
- ✓ Funziona con qualsiasi base: binario, ottale, esadecimale, decimale…
- ✓ Diretto e inverso sono algebricamente simmetrici: encoding ↔ decoding.