Come fanno i computer a calcolare le radici quadrate? — Parte 2: l'algoritmo Karatsuba

“La volta scorsa abbiamo visto come si calcola a mano una radice quadrata”.

“Ricordo. Una radice quadrata con resto, se ben ricordo”.

“Esatto. Per essere precisi: dato un numero m, diciamo che s è la sua radice quadrata e r è il resto se valgono queste relazioni:”.

s² ≤ m = s² + r < (s + 1)²

“E abbiamo detto che i computer seguono un algoritmo simile”.

“Ancora esatto: adattano questo algoritmo alle loro caratteristiche, sfruttano la base 2 invece della base 10, e sfruttano soprattutto il fatto di essere molto bravi a compiere operazioni ripetitive. In sostanza imparano a fare i calcoli con un caso relativamente facile, e se poi i numeri diventano troppo grossi allora li spezzettano in modo da ridurre il caso difficile a tanti casi facili”.

“Bello”.

“Posso farti vedere un programmino che simula quello che viene fatto effettivamente dall'algoritmo”.

“Perché dici simula?”.

“Perché le vere implementazioni sono al solito complicate da casi particolari relativi a quanto sono lunghi i gruppi di bit che ogni macchina riesce a gestire velocemente, e quindi i veri sorgenti sono pieni di controlli del tipo se lavori con 32 bit allora fai questo, se invece lavori con 64 allora fai quest'altro, e cose così”.

“Roba da informatici”.

“Già. E poi, per semplicità, il mio programmino funziona in base 10”.

“Ok”.

“L'algoritmo si chiama SqrtRem”.

“Bel nome, molto evocativo”.

“Non l'ho scelto io: è il nome che gli autori della libreria GMP hanno scelto; la prima parte, Sqrt, significa Square Root, cioè radice quadrata, e la seconda, Rem, sta per remainder, cioè resto”.

“Va bene, non critico più i nomi scelti dagli informatici”.

“Meglio così. Ora, abbiamo detto che l'algoritmo riconduce i casi difficili a casi più facili. Si dice che opera ricorsivamente, cioè chiama più volte sé stesso fino a che non è arrivato a un caso gestibile”.

“E qual è questo caso gestibile?”.

“Il caso è gestibile quando il numero di cui dobbiamo calcolare la radice quadrata è composto da al massimo tre cifre”.

“E perché è gestibile?”.

“Perché i quadrati composti da al più tre cifre non sono così tanti, e ce li possiamo calcolare a mano”.

“Cosa?”.

“Sì, hai capito bene: quando arriviamo a un numero composto da tre cifre o meno, diciamo al computer quale risultato deve dare”.

“Questo è barare, però”.

“Anche imparare le tabelline a memoria lo è, allora”.

“Uhm”.

“Rassegnati: inseriamo nel computer la lista di alcuni quadrati e, per loro, non ci poniamo più il problema di estrarre la radice quadrata”.

“Va bene, mi rassegno”.

“Ottimo. Ecco dunque una funzione, che si chiama BaseSqrtRem, che calcola le radici dei numeri composti da al massimo 3 cifre”.




“Oh, molto bene, cerco di capire cosa fa. Vedo intanto un controllo su m: deve effettivamente essere un numero di tre cifre”.

“Esatto”.

“Poi vedo che costruisci un dizionario in cui a ogni quadrato perfetto associ la sua radice”.

“Sì, come vedi non sono tanti. E anche nella realtà si fa così, eh. L'algoritmo memorizza una tabella di valori a cui fare riferimento: serve per terminare il ciclo ricorsivo”.

“Ok, mi fido, immagino che dopo si vedrà questo ciclo. Poi, vediamo che succede: fai un ciclo in cui esplori il dizionario ordinato. Perché lo ordini?”.

“Perché non è detto che i valori dentro a un dizionario python siano ordinati, e a noi invece interessa che lo siano. Per esempio, se vuoi calcolare la radice quadrata di 420 devi cominciare a guardare i valori che sono nella lista dei quadrati, e continui a scorrere la lista finché non trovi un numero che supera 420. Nel frattempo, memorizza l'ultimo valore che hai trovato”.

“In questo caso troverei 441”.

“Sì: il ciclo si blocca non appena trova 441, e in quel momento all'interno della variabile k è memorizzato il valore trovato al passo precedente, cioè 400”.

“Sì, vedo: il ciclo si blocca prima della assegnazione k = i”.

“Perfetto. Ora vedi che si esce dal ciclo e che si memorizza in s il valore di d[400], cioè 20”.

“Questa è la radice di 420, vero?”.

“Sì. Poi viene calcolato il resto sottraendo da 420 il quadrato di s, cioè 400. Risultato: 20”.

“Quindi la radice quadrata di 420 è 20 col resto di 20”.

“Perfetto, e questo è il caso base: quando arriviamo qui sappiamo fare il calcolo”.

“Perché nella lista c'è anche 1024?”.

“Perché se vuoi calcolare la radice di un numero maggiore o uguale a 961 il ciclo deve arrivare a considerare 1024, per poi bloccarsi”.

“Ok, chiaro. E adesso?”.

“Adesso arriva la parte seria: la funzione SqrtRem. L'idea è questa: se ho un numero composto da 4 cifre o più, lo prendo e divido le cifre in quattro gruppetti”.

“Anche nel calcolo a mano facevamo così? Non mi pare”.

“No, facevamo una cosa analoga ma non identica: dividevamo il numero a gruppetti composti da 2 cifre: tenevamo fisso il numero di cifre di cui era composto ogni gruppetto, e in questo modo avevamo un numero di gruppetti variabile”.

“Qui invece teniamo fisso il numero di gruppetti, mentre facciamo variare il numero di cifre che li compongono?”.

“Proprio così. Ti faccio vedere la parte di funzione che si occupa di questa suddivisione:”.



“Ah, ma usi le stringhe?”.

“Sì, ti ho detto che questo programma è un esempio, che in realtà non si fa così, no?”.

“Sì, ma non capisco le stringhe”.

“Immagina di fare i conti a mano: quando dividi un numero in 4 gruppi, lo fai contando le cifre. Tu, operatore manuale, usi le stringhe in questa fase, non ragioni sui valori numerici. Il programma ti copia”.

“Ah, va bene”.

“Quindi, arrivati alla fine di questa parte, nelle quattro variabili a0, a1, a2 e a3 sono contenuti i quattro gruppetti di cifre”.

“E che succede se la divisione non è esatta?”.

“Le cifre in più vanno a finire in a0. Mi spiego meglio: se il numero di cui vuoi calcolare la radice è 12345, i gruppi vengono composti in questo modo: 12|3|4|5. Se invece fosse 123456, i gruppi diventerebbero 123|4|5|6”.

“Ah, ok. Diventano tutti di 2 cifre quando si arriva a 12345678, suppongo”.

“Proprio così. Ora si parte con l'algoritmo vero e proprio, usando la filosofia divide and conquer”.

“Cioè?”.

“Cioè calcoliamo la radice quadrata del numero composto solo dai primi due gruppetti, che sono a0 e a1”.

“E come facciamo?”.

“Richiamiamo la funzione con quel numero”.

“Roba da matti. E funziona?”.

“Certo che funziona: ogni volta accorci il numero di cui vuoi calcolare la radice, e a un certo punto arrivi a un numero composto da al massimo 3 cifre. E di quello sai calcolare la radice. Il difficile è poi tornare indietro e ricomporre, da tutti i pezzettini, la radice del numero iniziale”.

“Ah, ecco”.

“Ecco quindi il nucleo della funzione che calcola la radice quadrata”.



“Oh, qua non si capisce niente”.

“Allora, la prima riga è la chiamata ricorsiva: vedi che viene chiamata nuovamente SqrtRem passandole, però, il numero a3*10^l+a2, cioè il numero composto dai primi due gruppetti di cifre”.

“Perché elevi alla l?”.

“Perché l è il numero di cifre di cui è composto ogni gruppetto: moltiplicare per 10^l significa spostare di l cifre a sinistra il numero moltiplicato”.

“Ah, ok. Immagino che nella realtà al posto di 10 ci sia un 2, vero?”.

“Esatto”.

“Quindi dentro a s1 e r1 ci finiranno la radice quadrata e il resto di quel numero”.

“Sì, e ora bisogna mettere a posto i conti, perché così facendo non hai considerato le cifre contenute in a1 e a0”.

“E come si fa?”.

“Forse è meglio seguire i calcoli con un esempio: diciamo che vogliamo calcolare la radice di 12345”.

“Oh, bene, un esempio con dei numeri veri! Allora, divido in quattro gruppetti, che dovrebbero essere questi: 12|3|4|5”.

“Giusto. Ora prendiamo soltanto i primi due, cioè il numero 123, e riapplichiamo di nuovo l'algoritmo”.

“Questa volta però il numero è di 3 cifre, quindi dovremmo trovare il risultato direttamente, vero?”.

“Certo: prova a farlo a mente. Qual è il più grande quadrato minore di 123?”.

“121, il quadrato di 11”.

“Bene, quindi 123 = 11² + 2”.

“Ah, quindi ho trovato s1 = 11 e r1 = 2, vero?”.

“Sì, questo è il primo passo: quello che hai fatto è scrivere 12300 = 12100 + 200. Ma tu vuoi trovare un'espressione simile per 12345”.

“Ho completamente trascurato le cifre 4 e 5”.

“Già. Ora procediamo come si farebbe a mano: se ricordi, c'era un calcolo apparentemente magico che diceva di raddoppiare il risultato parziale trovato fino a questo momento per la radice, per poi eseguire altri calcoli che avevano lo scopo di trovare la cifra successiva”.

“Mi ricordo, avevi spiegato anche il perché”.

“Ottimo. Partiamo sempre dalla stessa idea: una prima stima della radice che stiamo calcolando è 110, ma è soggetta a errore perché siamo partiti da 12300. Magari il numero che vogliamo non è 110 ma 111, o 112”.

“Allora modifichiamo un po' quel 110”.

“Esatto: immagina che sia (110 + q). Se lo elevi al quadrato ottieni 12100 + 220q + q²”.

“E quindi 220q + q² dovrebbe essere uguale a 12345”.

“Ma tu hai già scritto 12345 come 12100 + 200 + un errore, che è 45. Ora si procede in modo un po' diverso rispetto a quello che si farebbe a mano: si corregge 200 non aggiungendo 45 ma solo 40. Cioè, in realtà non si fa il confronto tra 245 e 220q ma tra 24 e 22q, buttando via l'ultima cifra”.

“Perché? Non considero nemmeno q²? Nel calcolo a mano lo facevamo”.

“Hai ragione, qua non si fa, e non ho trovato una spiegazione sul motivo. Alla fine l'errore che si commette trascurando quel termine viene corretto, ma non so perché si preferisca fare così. Sospetto per la velocità di esecuzione: se confrontiamo 240 con 220q vediamo che ci basta fare una divisione per trovare q, senza procedere per tentativi. Se si commette un errore, alla fine lo si corregge”.

“Ah, ok, quindi avremmo che q = 24/22, cioè 1”.

“Sì, con resto di 2. Questi due valori vengono memorizzati in q e u”.

“Ah, ecco il motivo di quelle due righe di codice. E poi che succede?”.

“Le due righe successive aggiungono la cifra q al risultato, e ricalcolano il resto”.

“E quel controllo sul resto negativo?”.

“Eh, è la correzione di cui ti parlavo prima: i calcoli fatti per q potrebbero, in alcuni casi, dare un resto negativo. Se così fosse, allora diminuiamo s di 1 e aggiorniamo il resto”.

“Non capisco bene l'aggiornamento del resto”.

“Supponi di aver sbagliato per eccesso il calcolo di una radice, cioè come se tu scrivessi A = B² − r”.

“Ah, ok, devo sottrarre il resto invece di aggiungerlo”.

“Esatto. Ora, che succede se al posto di B metti B − 1? Come devi correggere l'uguaglianza?”.

“Provo a fare i calcoli: se sviluppo il quadrato del binomio ottengo (B − 1)² = B² − 2B + 1”.

“E quindi A = (B − 1)² + 2B − 1 + r”.

“Ah, ecco, vedo: al vecchio resto devo aggiungere 2B e togliere 1, ho capito”.

“Perfetto. Ecco qua la funzione completa che calcola la radice quadrata di un numero col resto”.

“Ottimo. Ancora una vittoria per la carta e la penna”.