Esercizio 6divisione con una ALU a 8 bit, fattore di scala e serie (temi d'esame gennaio 2021, gennaio 2022, dicembre 2020 e luglio 2026)

---

Teoria usata: Moltiplicatori veloci e divisionePer il controllo real-time serve un moltiplicatore a ciclo singolo: a look-up table (la tabella cresce come $2^{2n}\cdot2n$ bit, quindi si fa solo a pochi bit e si compongono prodotti da 4 bit: $A\cdot B=A_HB_H,2^{8}+(A_HB_L+A_LB_H)2^4+A_LB_L$) oppure a matrice (schiera di AND e sommatori, ritardo $\sim2n$; varianti a somma per colonne e di Wallace). La divisione hardware si fa con sottrazioni successive (con ripristino) su valori positivi e il segno alla fine ($D=Q,d+R$); con $n$ bit ci sono vincoli su dividendo e divisore. Senza divisore hardware: $Q=N/D$ con la serie $\frac{N(1+Z)(1+Z^2)\cdots}{1-Z^{2^n}}$, $D=1-Z$, $0{,}5<D<1$.Moltiplicatori veloci e divisione →, Virgola fissa - formati n.m e normalizzazioneIn virgola fissa il processore fa aritmetica sugli interi (con segno) e il fattore di scalacostante per cui si moltiplica un valore reale per ottenere l'intero memorizzato $2^{m}$ resta sottinteso: il formato n.m dice che dei bit disponibili $n$ sono la parte intera (compreso il segno se il numero è con segno, S; nessun segno se U) e $m$ la parte frazionaria. Il valore è $\text{codice}/2^m$. Passare dal formato n.m al decimale, o viceversa, è il calcolo più frequente dell'esame: su 16 bit $\text{valore}=\text{codice}/2^m$, l'intervallo è $[0,2^n)$ (U) oppure $[-2^{n-1},2^{n-1})$ (S), la risoluzione è $2^{-m}$.Virgola fissa - formati n.m e normalizzazione →.

(a) Fattore di scala

Con una ALU a $n=8$ bit con segno, quoziente e resto sono nell'intervallo $[0,2^{n-1}-1]=[0,127]$ (il segno si tratta alla fine). Dividere due interi dà un quoziente troncato: $63:27=2$ resto 9, errore relativo $-14\%$. Per recuperare accuratezza si premoltiplica il dividendo per $2^k$: $q_k=\lfloor63\cdot2^k/27\rfloor$ è il quoziente nella scala $2^k$ (il valore vero è $q_k/2^k$); l'errore di troncamento diventa $\frac1{2^k}$ volte più piccolo. La condizione è che $q_k\le127$ (altrimenti la divisione "non è permessa").

Il fattore di scala più conveniente è il massimo che rispetta $q_k\le127$: $2^5=\mathbf{32}$, con quoziente $74$ e valore riportato in scala $74/32=2{,}3125$; il valore vero è $\frac{63}{27}=2{,}3333$: errore relativo $\frac{2{,}3125-2{,}3333}{2{,}3333}=\mathbf{-0{,}89\%}$ (per difetto, perché il quoziente è troncato). Il fattore 16 dà lo stesso valore: conviene 32 perché è il limite superiore (il prossimo, 64, dà 149).

$31:17$ ($=1{,}8235$). $k=6$: dividendo $1984$, $1984:17=116$ resto 12 ($116\le127$ ✓); $k=7$: $233>127$ ✗. Fattore di scala $2^6=\mathbf{64}$; valore $116/64=1{,}8125$; errore relativo $\frac{1{,}8125-1{,}8235}{1{,}8235}=\mathbf{-0{,}60\%}$.

(b) $2174:(-23)$

Il segno si gestisce alla fine, sui moduli: $2174:23=94$ resto $12$, perché $94\cdot23=2162$ e $2174-2162=12$. Il quoziente è negativo (segni discordi): $-94$; il resto ha il segno del dividendo (positivo): $+12$. Deve valere $2174=(-94)\cdot(-23)+12$ ✓.

• Quoziente $-94$ in complemento a 2 su 8 bit: $256-94=162=\texttt{0xA2}=\mathbf{10100010}$.
• Resto $+12=\mathbf{00001100}$.
• Divisore massimo in modulo: $127$ (limite dei numeri con segno a 8 bit): $2174:127=17$ resto 15 ✓.
• Divisore minimo in modulo: il quoziente non può superare 127: $\frac{2174}{|D|}<128$, cioè $|D|\ge\frac{2174}{128}=16{,}98$, quindi $|D|\ge\mathbf{17}$ (con 17: quoziente 127 resto 15; con 16 sarebbe 135, non rappresentabile).

(c) Divisione con il moltiplicatore

Il caso è $Q=\frac ND=\frac1{D/N}$ con $\frac DN=\frac{2{,}1}3=0{,}7\in(0{,}5,1)$ (già nel campo richiesto: nessuna premoltiplicazione).

• (a) $D'=1-\frac DN=1-0{,}7=\mathbf{0{,}3}$.
• (b) L'errore relativo dell'approssimazione con $n$ fattori è $D'^{2^n}$: $n=1$: $0{,}09$; $n=2$: $8{,}1\cdot10^{-3}$; $n=3$: $6{,}6\cdot10^{-5}$; $n=4$: $4{,}3\cdot10^{-9}$. Il risultato è $Q=1{,}428571$, da rappresentare su 16 bit in 1.15 U ($Q<2$): $LSB=2^{-15}=3{,}05\cdot10^{-5}$, errore massimo di rappresentazione $2^{-16}=1{,}5\cdot10^{-5}$ (relativo $1{,}07\cdot10^{-5}$). Perché l'algoritmo non peggiori il risultato serve $D'^{2^n}<1{,}07\cdot10^{-5}$: $n=3$ dà $6{,}6\cdot10^{-5}$ (non basta), $n=4$ dà $4{,}3\cdot10^{-9}$ ✓. $n=4$. Valori parziali: $n=3$: $Q_{app}=1{,}428478$; $n=4$: $1{,}4285714$.
• (c) Formato più conveniente: 1.15 U: $C=\mathrm{round}(1{,}428571\cdot32768)=46811=\texttt{0xB6DB}$.
• (d) Errore assoluto: valore rappresentato $\frac{46811}{32768}=1{,}428558$; $|\varepsilon|=\mathbf{1{,}3\cdot10^{-5}}$ (eccesso negativo: rappresentato minore del vero).

Errori comuni

• Premoltiplicare con un fattore troppo grande: il quoziente supera 127 e la divisione non è ammessa.
• Premoltiplicare con un fattore troppo piccolo (perdita di accuratezza) o dimenticare di dividere per $2^k$ per riportare il risultato in scala.
• Assegnare al resto il segno del divisore: ha il segno del dividendo ($-13:4=-3$ resto $-1$).
• Applicare la serie quando $D/N$ è fuori da $(0{,}5,1)$: va riportato nell'intervallo con una potenza di 2.