lunedì 2 aprile 2018

Come fanno i computer a calcolare le radici quadrate? — Parte 1: calcolo manuale

“La risposta breve è: le calcolano come faremmo noi per calcolarle a mano”.

“Ah, certo, tutti calcolano radici a mano”.

“La mia professoressa delle medie mi insegnò a farlo, sai?”.

“Anche la mia, ma se devo dire che mi ricordo come si fa, direi una bugia”.

“Sì, il procedimento non è per niente intuitivo, soprattutto in una parte. Ma partiamo dall'inizio: la descrizione completa dell'algoritmo l'ha scritta .mau. un po' di tempo fa, ed è spiegata qua”.

“Oh, bene, bene, ora me la guardo. No, decisamente non mi ricordavo tutto. Anzi, posso dire che mi ricordavo solo che si dovevano raggruppare le cifre del numero a due a due”.

“Sì, quello è il punto di partenza. Vogliamo provare a calcolare una radice quadrata a mano, in modo da sottolineare i punti importanti del procedimento?”.

“Ok, andiamo”.

“Allora, proviamo a calcolare la radice di 7654. Scriviamo il numero raggruppando le cifre a due a due”.

“E quindi formiamo due gruppetti”.

“Sì, e scriviamo in questo modo il tutto:”.

76.54 | 
      |-------
      |

“Ok, ora che succede?”.

“Ora si prendono le prime due cifre e si dà per scontato che la radice del numero composto solo da quelle due cifre la sappiamo calcolare”.

“Io non so quanto valga esattamente la radice di 76, però”.

“Sei in buona compagnia: nessuno lo sa. Ma non ci serve una precisione infinita, perché lavoriamo solo sui numeri interi: per calcolare la radice di 76 ti serve soltanto conoscere le tabelline”.

“Ah, allora posso dire che 8 è troppo poco e 9 è troppo”.

“Approssimiamo per difetto”.

“Allora dico che la radice di 76 è 8”.

“Benissimo, il primo passo è fatto, scriviamo 8 come prima cifra”.

76.54 | 8
      |-------
      |

“Fin qua è stato facile”.

“Ora correggiamo l'errore: calcoliamo il vero quadrato di 8…”.

“Che è 64”.

“Lo scriviamo sotto al 76, e facciamo la differenza, in modo da trovare il resto”.

76.54 | 8
64    |-------
--    |
12    |


“Bene. Adesso? Non ricordo più come si va avanti”.

“Adesso c'è la parte magica del procedimento, ma prima di raccontarla vediamo quello che abbiamo fatto finora. In sostanza abbiamo capito che 76 = 82 + 12”.

“D'accordo”.

“Ma 76 è stato estratto dal numero 7654 prendendo le prime due cifre, e quindi quello che abbiamo fatto in realtà è stato capire che 7600 = 82 × 102 + 1200”.

“Va bene, hai moltiplicato tutto per cento”.

“Sì, in questo modo abbiamo calcolato la radice di 7600, con il suo resto. Però volevamo calcolare la radice di 7654, che è un po' più grande”.

“Ci basterà correggere il resto: 7654 = 82 × 102 + 1254”.

“Ah, certo, ma così il resto diventa un po' troppo grande: non possiamo fare di meglio?”.

“Non saprei. Cioè, immagino di sì, ma non so mica come”.

“Quell'80 è un po' troppo basso, se lo aumentiamo un pochino magari riusciamo a diminuire il resto”.

“Vero, se prendo ad esempio 81 mi viene che 7654 = 812 + 1093”.

“Va già meglio, ma hai scelto 81 a caso. Magari con 82 può andare meglio, o forse con 83, o chissà”.

“E come faccio?”.

“Prova a fare una stima: invece di usare 80, tu vuoi usare 80 + t”.

“E quanto vale t?”.

“Ancora non lo sai: è quello che vuoi stimare. Prova a scrivere 7654 come quadrato di 80 + t. Anzi, per maggiore generalità scrivi 8 × 10 + t”.

“Va bene: 7654 = (8 × 10 + t)2. E adesso?”.

“Adesso svolgi il quadrato di binomio, lasciando indicati tutti i calcoli”.

“Oh, vediamo: quadrato del primo termine, doppio prodotto, quadrato del secondo… Mi viene questa roba:”.

7654 = 802 + 2 × 8 × 10 × t + t2.

“Ottimo. 802 fa 6400, è un numero che avevi già calcolato nel primo passo dell'algoritmo del calcolo della radice quadrata. La parte interessante è quella che segue: 2 × 8 × 10 × t + t2”.

“Che deve dare il famoso 1254”.

“Proprio così. Scriviamolo per bene:”.

2 × 8 × 10 × t + t2 = 1254.

“Ok, e adesso?”.

“Raccogliendo a fattor comune t si ottiene”.

(2 × 8 × 10 + t) × t = 1254

“Bene, e questo mi aiuta a trovare t?”.

“Questo spiega il passaggio magico dell'algoritmo della radice quadrata. Ricordi che avevi trovato la prima cifra, 8?”.

“Sì, e l'avevo scritta in alto”.

“Bene. Adesso il procedimento dice: abbassa altre due cifre di 7654, e poi raddoppia le cifre che hai trovato provvisoriamente per la radice quadrata, scrivile sotto, in questo modo…”.

76.54 | 8
64    |-------
----- | 16
12.54 |


“E poi?”.

“E poi trasforma 16 in decine, e trova quella cifra t delle unità da aggiungere a 16 in modo da trovare un numero 16t tale che 16t × t sia il più vicino possibile a 1254, senza però superarlo”.

“Ma quando scrivi 16t non intendi 16 × t, vero?”.

“No, è per questo che ho sempre esplicitato il simbolo di moltiplicazione: in questo caso con 16t intendo un numero di tre cifre avente 1 come cifra delle centinaia, 6 come cifra delle decine, e t come cifra delle unità”.

“E come si fa a trovare quel numero?”.

“Lo spiega sempre .mau.: in sostanza si va per tentativi, facendo una stima grossolana per eccesso e poi scendendo. Avevamo trovato un resto parziale di 12, dopo aver scritto il primo 8”.

“Vero”.

“Ora, 12 sono diventate centinaia, e la cifra delle decine è diventata 5”.

“Sì, poi 4 è quella delle unità, in modo da ottenere 1254”.

“Tieni solo le prime 3, cioè 125”.

“Ok”.

“Adesso calcola 125 / 16”.

“Viene 7.8 e rotti”.

“Parti quindi da 8, e fai 168 × 8, scrivendolo nello spazio vuoto sotto a 8”.

“Così?”.

76.54 | 8
64    |---------------
----- | 168 × 8 = 1344
12.54 |


“Sì: come vedi 1344 è un numero maggiore di 1254”.

“Allora?”.

“Allora la stima t = 8 era troppo alta, abbassala di uno e ripeti il procedimento”.

76.54 | 8
64    |---------------
----- | 168 × 8 = 1344
12.54 | 167 × 7 = 1169


“Questo va bene, ora puoi scrivere 1169 sotto a 1254 e calcolare il resto giusto. E non dimenticare di aggiungere la cifra 7 al risultato della radice, in alto, di fianco all'8”.

“Ecco:”.

76.54 | 87
64    |---------------
----- | 168 × 8 = 1344
12.54 | 167 × 7 = 1169
11.69 |
----- |
   83 |

“Perfetto, fine del procedimento. La radice di 7654 è 87 con resto di 83”.

“Fammi capire meglio questa cosa del resto, che non l'avevo mai sentito associato alle radici quadrate”.

“Quello che abbiamo fatto è questo: dato m, numero intero positivo, lo abbiamo scritto così”.

m = s2 + r

“Ah, dove s è la radice quadrata approssimata per difetto”.

“E r è il resto, esatto. Nel nostro caso 7654 = 872 + 83”.

“Ho capito”.

“Il procedimento per fare il calcolo a mano è quello di fare i conti a pezzi, dando per scontato che riusciamo a calcolare a mente le radici dei numeri di due cifre”.

“Ok”.

“La cosa strana è che per poter andare avanti e aggiungere una cifra occorre inserire una strana moltiplicazione per 2, che non si sa bene da dove salti fuori”.

“Quando abbiamo preso l'8 appena scritto e lo abbiamo fatto diventare 16?”.

“Proprio così. La spiegazione di quella parte è che quella moltiplicazione per 2 corrisponde al famoso doppio prodotto che salta fuori nello sviluppo del quadrato del binomio”.

“Che roba”.

“E quindi la prossima cifra l'abbiamo cercata intorno all'approssimazione 125 diviso per il doppio prodotto, cioè 125 / 16”.

“Avremmo dovuto fare 1254 / 167”.

“Certo, ma quel 7 non lo conoscevamo ancora…”.

“Ah, già, è vero! E quindi abbiamo stimato 1254 / 16t facendo 125 / 16”.

“Sì, e poi abbiamo aggiustato il tiro”.

“E dici che i computer fanno la stessa cosa?”.

“Non so se tutti i computer facciano così, ma questo è l'algoritmo usato dalla libreria GMP: GNU multiple precision arithmetic library”.

“Dalla descrizione presente nell'introduzione, sembra il meglio che possiamo avere per fare calcoli”.

“Pare proprio di sì: precisione multipla, massima velocità. L'algoritmo usato dalla libreria è in realtà una generalizzazione di questo, ma si basa su questi identici concetti: prendo un numero arbitrariamente grande e lo spezzetto fino a che non so fare i calcoli”.

“A gruppi di 2 cifre?”.

“Non esattamente, ma lo vediamo in dettaglio la prossima volta. Per ora accontentiamoci di definire bene quello che vogliamo fare”.

“La radice quadrata, no?”.

“Certo, ma come definiamo per bene il resto? Quanto può essere grande al massimo?”.

“Ehm”.

“Vedi che occorre, prima di tutto, capire quello che vogliamo. Allora, dato un numero m, diciamo che s è la sua radice quadrata e r è il resto se valgono queste relazioni:”.

s2m = s2 + r < (s + 1)2

“Ok, credo di aver capito, il resto non deve essere così grande da farmi arrivare al quadrato successivo”.

“Esatto”.