Aritmetica dei calcolatori

Le reti dell'aritmetica sono reti combinatorie con molti ingressi e molte uscite: nessuno le sintetizza con le mappe di Karnaugh. Il metodo è un altro, e vale in qualunque base: si parte dall'algoritmo che si usa a mano, lo si scompone in operazioni su una cifra, e si montano blocchi elementari (sommatori, multiplexer, comparatori). La parte delicata non è il circuito, ma il dimensionamento: su quante cifre sta ogni risultato, e quando il risultato non esiste.

Rappresentare i numeri naturali

La notazione posizionale

Un sistema posizionale ha una base β ≥ 2, β cifre (con valori da 0 a β − 1) e una legge che associa a una sequenza di cifre un numero naturale:

A ≡ (a_n−1 … a₁ a₀)_β   ⟺   A = Σ_i=0ⁿ⁻¹ a_i · βⁱ

Ogni cifra pesa in base alla sua posizione. Esempio in base sedici, con cifre 0…9, A…F: (1A2F)₁₆ = 15 · 1 + 2 · 16 + 10 · 256 + 1 · 4096 = 6703. Quando scriviamo «54» indichiamo insieme il numero (un concetto) e una sua rappresentazione in base dieci: tenerli distinti aiuta, soprattutto con gli interi.

La divisione con resto e l'operatore modulo

L'unicità viene dal vincolo 0 ≤ r < β: per questo la divisione per un naturale approssima verso sinistra, anche per i negativi: ⌊−7/2⌋ = −4 con resto 1, non −3. Tre proprietà del modulo si usano di continuo:

• |x + k · α|_α = |x|_α per ogni intero k;
• |x ± y|_α = ||x|_α ± |y|_α|_α;
• |x · y|_α = ||x|_α · |y|_α|_α.

Applicando il teorema ripetutamente (MOD & DIV) si trovano le cifre di A in base β: A = q₁ · β + a₀, q₁ = q₂ · β + a₁, … fino a un quoziente nullo; i resti, letti dal basso, sono le cifre. Il teorema garantisce che la rappresentazione esiste ed è unica. Con le stesse proprietà si dimostrano i criteri di divisibilità, utili negli esercizi:

Su quante cifre

Con n cifre in base β si scrivono βⁿ combinazioni, quindi i naturali da 0 a βⁿ − 1 (tutte le cifre a β − 1: 999…9 in base dieci). Per rappresentare A servono n = ⌈log_β(A + 1)⌉ cifre: 1000 in binario richiede ⌈log₂ 1001⌉ = 10 bit. È la domanda da farsi prima di qualunque rete: su quante cifre sta il risultato?

Reti per i numeri naturali

Cifre e codifiche

Una rete combinatoria vede variabili logiche, non cifre. In base 2 una cifra è una variabile; in un'altra base ogni cifra va codificata, di solito con il suo valore in binario (in base dieci è il BCD: 9 → 1001). Una rete «quadrato» in base dieci, con ingresso 1001 (9), deve dare 1000 0001 (81 in BCD), non 1010001 (81 in binario): la base in cui opera la rete è nel modo di interpretare le uscite. Per fortuna quasi tutte le operazioni si esprimono come relazioni tra cifre, indipendenti dalla base: le codifiche servono solo quando si sintetizzano le reti di una cifra.

Il complemento

Il complemento di A su n cifre in base β è A = βⁿ − 1 − A: il numero che, sommato ad A, dà il massimo rappresentabile. Siccome βⁿ − 1 ha tutte le cifre a β − 1, il complemento si fa cifra per cifra: ogni cifra a_i diventa β − 1 − a_i.

• (1034)₁₀ → (8965)₁₀; ma su sei cifre (001034)₁₀ → (998965)₁₀: il complemento dipende dal numero di cifre;
• (1034)₅ → (3410)₅;
• in base 2 il complemento di una cifra è la NOT: il complemento di un numero è una barriera di invertitori.

Moltiplicare e dividere per una potenza della base

25 × 1000 non si calcola: si aggiungono tre zeri. 2562 / 100 ha quoziente 25 e resto 62 senza fare conti. Vale in ogni base:

• moltiplicare per β^k significa aggiungere k zeri in coda (shift a sinistra), su n + k cifre;
• il quoziente della divisione per β^k sono le n − k cifre più significative (shift a destra), il resto le k meno significative;
• di conseguenza concatenare due numeri (X = Z · β^k + Y) e spezzarne uno in due blocchi sono operazioni a costo nullo.

Le reti di shift sono solo fili: usare porte logiche per moltiplicare o dividere per β^k è un errore. Anche l'estensione di campo dei naturali è a costo zero: per scrivere un naturale su più cifre si mettono zeri in testa (per gli interi sarà diverso).

Il sommatore

Dati X, Y su n cifre e un riporto entrante C_in ∈ {0, 1}, la somma vale al massimo 2βⁿ − 1 < βⁿ⁺¹: sta sempre su n + 1 cifre, e l'ultima, il riporto uscente C_out, vale 0 o 1. Se C_out = 0 la somma sta su n cifre; se vale 1 no. Il C_in sembra una complicazione, ma è ciò che rende l'operazione modulare: una somma su n cifre si scompone in n somme su una cifra collegate dai riporti.

Il blocco su una cifra in base 2 è il full adder: tre ingressi, due uscite. La somma vale 1 quando gli ingressi a 1 sono in numero dispari (XOR a tre ingressi); il riporto vale 1 quando sono almeno due (c_out = xy + x c_in + y c_in).

Se uno dei due addendi è sempre nullo il full adder si semplifica: si ottiene l'incrementatore (somma C_in a un numero), un circuito a un solo livello di logica. In Assembler inc %al e add $1, %al danno lo stesso risultato ma sono istruzioni diverse.

Il sottrattore e il comparatore

La differenza X − Y − b_in può non essere un naturale. Si scrive come −b_out · βⁿ + D, con D su n cifre e il prestito uscente b_out ∈ {0, 1}: se vale 1 la differenza è negativa. Sostituendo −Y = Y − βⁿ + 1 si scopre che il sottrattore è un sommatore:

b_out · βⁿ + D = X + Y + b_in

Da qui il comparatore per naturali: A < B se e solo se A − B dà prestito (flag_min). Per l'uguaglianza si fa prima con una XOR per bit e una NOR (flag_eq): la rappresentazione è unica. Attenzione: guardare il prestito funziona solo per i naturali.

Il moltiplicatore

Con X, C su n cifre e Y su m, il risultato P = X · Y + C vale al più β^m(βⁿ − 1) e sta su n + m cifre. Il termine C serve, come il riporto, a scomporre: l'algoritmo delle elementari si riorganizza in modo da sommare due soli addendi alla volta. Esempio, 245 × 131:

Il blocco n × 1 in base 2 è semplicissimo: moltiplicare per una cifra binaria vuol dire scegliere tra X e 0, cioè una barriera di AND, seguita da un sommatore.

In Assembler mul ha un solo operando: l'altro è implicito (AL, AX, EAX) e il risultato va su una destinazione doppia (AX, DX_AX, EDX_EAX). Spesso un moltiplicatore non serve affatto: per convertire due cifre BCD in binario, Y = 10 · x₁ + x₀ = 8x₁ + 2x₁ + x₀. Gli shift sono fili, restano due somme: 2x₁ + x₀ ≤ 27 su 5 bit, poi 8x₁ + (…) ≤ 99 su 7 bit, con gli ingressi di ciascun sommatore estesi alla sua larghezza.

Il divisore

Dividendo X su n + m cifre, divisore Y su m cifre: il resto sta su m cifre (è minore di Y), ma il quoziente, se Y = 1, può richiederne n + m. Si vuole il quoziente su n cifre, e questo è possibile solo se

X < βⁿ · Y   ⟺   le m cifre più significative di X formano un numero minore di Y

Se la condizione è falsa (o Y = 0) la rete alza l'uscita no_div. L'algoritmo a mano: si prendono m + 1 cifre del dividendo, si calcola un quoziente parziale di una cifra e un resto, si concatena il resto con la cifra successiva, e così via. Esempio con β = 10, m = 2, n = 3: 01423 diviso 47 (fattibile: 01 < 47).

1. 014 : 47 → quoziente 0, resto 14;
2. 142 : 47 → quoziente 3, resto 1;
3. 013 : 47 → quoziente 0, resto 13. Quindi Q = 030, R = 13 (verifica: 47 · 30 + 13 = 1423).

Il nucleo è quindi un divisore di m + 1 cifre per m cifre con quoziente su una cifra, e no_div si decide al primo stadio. In base 2 quel nucleo si riduce a un sottrattore e un multiplexer:

La div dell'Assembler vuole un dividendo su 2n bit, un divisore su n bit e un quoziente che stia su n bit, altrimenti genera un'eccezione: tocca al programmatore garantire X < 2ⁿ · Y, ad esempio estendendo gli operandi su un numero doppio di bit.

Esempio: ⌊7X/8⌋ senza moltiplicatori

Con X su n bit, Y = ⌊7X/8⌋ sta su n bit (non meno: con X = 7, Y = 6). Si scrive Y = ⌊(8X − X)/8⌋: 8X è uno shift (tre zeri in coda, n + 3 bit), la differenza si fa con un sottrattore a n + 3 bit (con X esteso), e la divisione per 8 butta via le tre cifre meno significative.

Come si scoprono errori di questo tipo? Come con i programmi: si prova il circuito con qualche ingresso scelto con cura (casi limite, numeri non multipli), calcolando a mano le uscite. Non è una dimostrazione, ma un singolo caso che non torna basta a scoprire l'errore.

Rappresentare i numeri interi

Leggi di rappresentazione

I circuiti lavorano solo su cifre. Per gli interi si sceglie una legge biunivoca L che associa a ogni intero a (minuscolo) un naturale A (maiuscolo), rappresentato su n cifre: a ↔ A. Con βⁿ combinazioni e β pari, l'intervallo più simmetrico possibile è

[ −βⁿ/2 , βⁿ/2 − 1 ]    (su 8 bit: da −128 a +127)

con un negativo in più. Le leggi usate in pratica:

• Traslazione: A = a + βⁿ/2. È monotona (a < b ⟺ A < B); si usa nei convertitori A/D e D/A, dove si chiama binario bipolare, e per l'esponente dei numeri reali.
• Complemento alla radice (CR): A = a se a ≥ 0, A = βⁿ + a se a < 0. È la legge dei calcolatori, monotona solo tra numeri dello stesso segno.
• Modulo e segno: una variabile di segno più il modulo. Non associa interi a naturali, e i circuiti che la usano sono più complessi.

Le proprietà del complemento alla radice

• Segno: a < 0 se e solo se la cifra più significativa è ≥ β/2. In base 2, se il bit più significativo è 1.
• Legge inversa: a = A se a_n−1 < β/2, altrimenti a = −(A + 1). Esempi: (852)₁₀ su 3 cifre ha MSD 8 ≥ 5, quindi a = −(147 + 1) = −148; (500)₁₀ → −500; (1011)₂ → −(0100 + 1) = −5; (1111)₂ → −1.
• Forma compatta: A = |a|_βⁿ. Ma solo se a è rappresentabile! Con β = 10, n = 3: |−953|₁₀₀₀ = 47, che è la rappresentazione di +47, non di −953 (che su tre cifre non esiste). Dimenticarlo è un errore grave.

Prova con il laboratorio: scegli la base e il numero di cifre, poi passa da un intero alla sua rappresentazione e viceversa. Il secondo modo mostra anche opposto, valore assoluto, estensione e riduzione.

Operazioni sugli interi in complemento alla radice

Un circuito esegue l'operazione O sugli interi se, ricevendo A ↔ a e B ↔ b, produce Z ↔ z con z = O(a, b). Il legame tra cifre e interi sta solo nella nostra testa: il bello del CR è che molti circuiti per naturali vanno bene anche così.

Valore assoluto e opposto

Dalla legge inversa: ABS(a) = A se a_n−1 < β/2, altrimenti A + 1. Il risultato è un naturale in [0, βⁿ/2] e richiede n cifre (n − 1 non bastano, neanche in base 2). Esempi: (852)₁₀ → 147 + 1 = 148; (1011)₂ → 0100 + 1 = 5. In base 2 basta una barriera di XOR con il bit di segno e un incrementatore:

Da qui il convertitore da CR a modulo e segno (sempre fattibile) e, con un multiplexer, quello inverso da MS a CR (che può andare in overflow). L'opposto si calcola come |A + 1|_βⁿ: complemento più incremento. Due casi da provare: con A = 10000000 si ottiene di nuovo 10000000, perché −128 non ha opposto su 8 bit (overflow, che in base 2 si riconosce perché ingresso e uscita sono entrambi negativi); con A = 00000000 l'incrementatore dà riporto, ed è per questo che serve il modulo. In Assembler neg calcola l'opposto e alza OF nel caso impossibile.

Estensione e riduzione di campo

Per scrivere lo stesso intero su n + 1 cifre non basta uno zero in testa: i negativi devono «salire» di βⁿ(β − 1). Le n cifre basse restano uguali, e la nuova cifra vale 0 per i non negativi e β − 1 per i negativi. In base 2 si ripete il bit di segno: 1011 (−5) diventa 11011. L'estensione degli interi, a differenza dei naturali, richiede logica (in base 2 basta un filo). In Assembler la fanno cbw, cwd, cwde, cdq; per i naturali non c'è un'istruzione apposta: si mettono zeri.

Il problema inverso, la riduzione da n + 1 a n cifre, ha soluzione solo se il numero sta nell'intervallo più piccolo, cioè se

(a_n = 0 e a_n−1 < β/2)  oppure  (a_n = β − 1 e a_n−1 ≥ β/2)

e in quel caso si butta via la cifra più significativa. In base 10: 9852 (−148) si riduce a 852; 9352 (−648) no, perché −648 non sta in [−500, +499]. In base 2 la condizione è che le due cifre più significative siano uguali: il circuito di overflow è una XOR. Per ridurre di k cifre si controlla che i k + 1 bit più significativi siano tutti uguali (una AND e una OR a k + 1 ingressi, e una XOR tra le loro uscite).

Shift logici e aritmetici

Moltiplicare e dividere per β^k si fa come per i naturali, quando si può cambiare il numero di cifre. Nei registri però i bit sono fissi, e le cose cambiano:

• per 2: bisogna che l'operando sia riducibile (per i naturali MSB = 0, per gli interi due MSB uguali), poi si trasla a sinistra. La traslazione è la stessa: shl e sal sono la stessa istruzione macchina, che alza CF o OF e lascia al programmatore il flag giusto;
• diviso 2: si estende di un bit (0 per i naturali, il segno per gli interi) e si prendono gli n bit alti. Servono due istruzioni diverse: shr e sar.

Somma, sottrazione e overflow

Quando s = a + b è rappresentabile su n cifre, per le proprietà del modulo:

S = |a + b|_βⁿ = ||a|_βⁿ + |b|_βⁿ|_βⁿ = |A + B|_βⁿ

La rappresentazione della somma è la somma delle rappresentazioni: non esiste un sommatore per interi, c'è il sommatore. È questa proprietà, da sola, a giustificare il complemento alla radice. Cambia solo come si capisce se il risultato è giusto: il riporto uscente non dice niente sugli interi. Con A = βⁿ − 1 (cioè −1) e B = 1 si ha C_out = 1 ma la somma (0) è giusta; con A = B = βⁿ/2 − 1 si ha C_out = 0 ma la somma di due positivi esce negativa.

Il metodo generale: si fa la somma su n + 1 cifre con gli addendi estesi (lì è sempre rappresentabile) e si controlla se il risultato è riducibile. In base 2 si arriva a una formula senza stadi in più: ow = c_n ⊕ c_n−1.

La sottrazione è analoga: D = |A + B + 1|_βⁿ, cioè lo stesso sottrattore dei naturali, con l'overflow (in base 2) dato dallo XOR degli ultimi due prestiti. In Assembler c'è una sola add e una sola sub: alzano sia CF sia OF, e dopo l'istruzione il programmatore usa jc/jnc se sta lavorando con naturali, jo/jno se con interi.

Confrontare due interi

L'uguaglianza si testa come per i naturali. Per la minoranza si usa ancora un sottrattore, ma non si guarda il prestito: si guarda il segno della differenza, che per essere sempre rappresentabile va calcolata su n + 1 cifre, estendendo gli operandi. Esempio su 4 bit: −8 < 1, eppure 1000 − 0001 come naturali non dà prestito (8 − 1 = 7).

Moltiplicazione e divisione

Per moltiplicare e dividere conviene passare dai valori assoluti, riusare i circuiti dei naturali e sistemare il segno alla fine:

• prodotto: ABS(p) = ABS(a) · ABS(b), il segno è lo XOR dei segni. Su n + m cifre non c'è mai overflow (|p| ≤ β^n+m/4). Il moltiplicatore per interi non ha l'ingresso C;
• divisione: tra interi il resto non è unico con il solo vincolo |r| < |b| (17 diviso −5 dà q = −3, r = 2 oppure q = −4, r = −3). Si aggiunge che il resto abbia il segno del dividendo: il quoziente è troncato verso lo zero. Allora ABS(a) = ABS(q) · ABS(b) + ABS(r) è una divisione tra naturali.

La fattibilità della divisione naturale tra i valori assoluti è necessaria ma non sufficiente: il quoziente, riportato in CR, può andare in overflow. Esempio in base 10 con n = 1, m = 2: −223 ÷ 28. La divisione naturale 223 ÷ 28 è fattibile (quoziente 7, una cifra), ma q = −7 non sta in [−5, +4]: non si può fare. Con −123 ÷ 28 invece ABS(q) = 4, ABS(r) = 11, quindi q = −4 ↔ Q = 6 e r = −11 ↔ R = 89. Il segnale no_idiv è l'OR di no_div e dell'overflow del convertitore MS → CR. Per questo in Assembler ci sono mul/imul e div/idiv distinte, mentre la somma è una sola.

Esercizi svolti

Il massimo di tre numeri

Testo. Rete che riceve a, b, c su n bit e produce il massimo; poi la stessa con interi in CR.

Tre comparatori calcolano x_AB = (a < b), x_BC = (b < c), x_CA = (c < a); una piccola rete combinatoria ne ricava i due bit di comando di un multiplexer che sceglie tra A, B, C. La combinazione 111 è impossibile (un ciclo di minoranze non esiste) e con 000 i tre numeri sono uguali, quindi va bene qualunque scelta: sono entrambe non specificate, e la sintesi viene b₀ = x_AB, b₁ = x_BC · x_CA. Per gli interi cambia solo il comparatore (segno della differenza estesa invece del prestito). Alternativa con meno logica: confrontare a e b, far passare il maggiore con un multiplexer a due vie, confrontarlo con c.

b = 7 − 5a senza moltiplicatori

Testo. a ↔ A in CR su 6 bit; produrre B ↔ b = 7 − 5a, senza moltiplicatori. Mostrare i valori per a = 14.

1. Dimensionamento: −32 ≤ a ≤ 31, quindi −148 ≤ b ≤ 167: servono 9 bit (da −256 a +255).
2. Riscrittura: b = (7 − a) − 4a = c − d. Il prodotto per 4 è uno shift di due posizioni.
3. Circuito: C = 7 + A + 1 (con A esteso ripetendo il segno), D = 4A (due zeri in coda e segno esteso), B = C + D + 1: due sottrattori a 9 bit.
4. Verifica con a = 14: A = 001110, C ↔ −7 = 111111001, D ↔ 56 = 000111000, B ↔ −63 = 111000001. E infatti 7 − 70 = −63.

Multiplo di 3 in base 4

Testo. A su 5 cifre in base 4: uscita 0 se A è multiplo di tre, 1 altrimenti.

Per il criterio visto (3 divide β − 1 = 3) basta sommare le cifre: ogni cifra sta su 2 bit, la somma di cinque cifre vale al più 15 e sta su 4 bit. Poi si divide per 3 con un divisore naturale e si guarda se il resto (2 bit) è nullo: z = OR dei bit del resto. Attenzione al dimensionamento del divisore: il quoziente arriva a 5 e richiede 3 bit, quindi il dividendo va esteso a 5 bit perché valga X < 2³ · 3.

La tangente a una parabola

Testo. Interi a, b, c, x su n bit in CR; produrre il coefficiente angolare della tangente a y = ax² + bx + c nel punto x, e poi sintetizzare i due bit meno significativi.

La derivata è m = 2ax + b: un moltiplicatore per interi (n × n → 2n bit), uno shift, un'estensione di b e un sommatore a 2n + 1 bit; c non serve. Per i bit bassi si ragiona sui fili: m₀ = b₀, perché l'altro addendo ha uno zero in coda; m₁ = b₁ ⊕ y₀, dove y₀ è il bit basso del prodotto ax, che vale 1 solo se entrambi sono dispari: m₁ = b₁ ⊕ a₀x₀. Il bit meno significativo dice la parità, qualunque sia il segno.

Buone norme per gli esercizi di aritmetica

Verifica