Come funzionano la moltiplicazione e la divisione nella CPU?

Ci sono diversi metodi di moltiplicazione, ma la maggior parte di essi, alla base, usa una sorta di tabella di ricerca. Questo è - se hai una certa età - lo stesso modo in cui ai bambini a scuola venivano insegnate le tabelle di moltiplicazione -

"un due è due, due due due sono quattro, tre due sono sei ..."

Quando devi moltiplicare 5 per 8, non lo risolvi - ti ricordi semplicemente "cinque otto sono 40". O almeno, io lo faccio. I giovani fustigatori di oggi probabilmente usano l'app calcolatrice sul loro telefono.

In binario, ci sono 256 possibili risultati a 8 bit dalla moltiplicazione di due numeri binari a 4 bit. 256 byte è una dimensione conveniente per una tabella di ricerca codificata con tutti i possibili risultati, così una CPU può moltiplicare due numeri a 8 bit spezzando ciascuno di essi in due numeri a 4 bit, cercando i quattro prodotti parziali 4x4 e sommandoli, con vari offset di 4 bit, per produrre il prodotto a 16 bit. Questo è molto veloce. Le CPU più grandi possono permettersi lo spazio per fare tabelle di ricerca più grandi - una tabella di moltiplicazione 8 per 8 richiede 65.536 parole a 16 bit (131kB). Al di sopra di 8x8, le tabelle diventano troppo grandi. I chip più piccoli possono usare una tabella 2x2 con più stadi adder. Sarebbe anche possibile farlo in microcodice, usando il tradizionale algoritmo shift-and-add, ma sarebbe molto lento. Non conosco nessuna CPU moderna che lo faccia in questo modo.

La divisione è molto più difficile. Può essere fatta in logica combinatoria, così:

Ogni casella quadrata contiene una dozzina di porte logiche, così -

Quindi un divisore a n bit necessita di n*n elementi che occupano molto spazio. Di conseguenza la maggior parte delle piccole CPU lo implementa nel microcodice usando il tradizionale algoritmo shift-and-subtract, o (più tipicamente) lo omette del tutto. È solo quando si raggiungono le CPU su scala di milioni di transistor che il metodo logico diventa economico.