radice quadrata intera

Vi siete mai chiesti come calcolare rapidamente una radice quadrata? C’è il metodo che ai miei tempi si insegnava a scuola, e che riscuote ancora un certo successo nelle ricerche, e c’è il metodo babilonese, che fondamentalmente – se non avete voglia di leggere il mio post che ho citato – consiste nel partire da una stima anche grossolana e sostituirla a ogni passo con la media aritmetica della stima precedente e del suo inverso. Qual è la differenza tra i due metodi? Quello manuale è più semplice da portare avanti se devi fare i conti a mano, e quindi assolutamente inutile in pratica: non credo che qualcuno vi punterà mai una pistola alla tempia chiedendovi di prendere carta e penna e trovare le prime sei cifre decimali della radice quadrata di 2. Il metodo babilonese (che poi è stato generalizzato da Newton e Raleigh) è invece perfetto se abbiamo a disposizione un computer a cui far fare i conti, tanto che adesso è addirittura implementato in hardware, con ulteriori scorciatoie che ho raccontato nel mio Chiamatemi pi greco.

Ma supponiamo che non siamo interessati ad avere un numero indefinito di cifre dopo la virgola, ma soltanto il più grande numero naturale il cui quadrato è inferiore a quello di partenza: la radice quadrata intera. E a che ci servirebbe? A fattorizzare un numero, come sapeva bene Fermat! Se riusciamo infatti a scrivere un numero composto dispari come differenza di due quadrati, \( n = a^2 – b^2 \), allora sappiamo già fattorizzarlo come \(n = (a+b)(a-b) \). Esempio pratico: prendiamo 17867273. La sua radice quadrata è 4226,9697… che è quasi 4227. Ora, 4227² = 17867529, e 17867529 − 17867273 = 256, che è il quadrato di 16. Pertanto 17867273 = (4227+16)(4227-16) = 4243 × 4211. Questo tra l’altro ci fa capire perché quando si scelgono due numeri primi “grandi” per le tecniche di crittografia è consigliabile che siano dello stesso ordine di grandezza, ma non troppo vicini tra di loro…

Insomma la radice quadrata intera ha un suo perché. Ma come si calcola? Come spiega John Cook, l’algoritmo babilonese funziona anche se usiamo i numeri naturali al posto di quelli reali: la cosa non è ovvia, ci sono algoritmi che non possono essere “approssimati” così, ma in questo caso l’algoritmo è così robusto da permetterlo. Cook mostra anche il codice Python per l’algoritmo ( “//” è la divisione intera):


def sqrt_floor(n):
a = n
b = (n + 1) // 2
while b < a: a = b b = (a*a + n) // (2*a) return a

Il bello di questo algoritmo è che è applicabile a interi di dimensione arbitraria, se si ha un pacchetto di aritmetica a precisione estesa. E come bonus, ritroviamo lo stesso algoritmo nello standard NIST FIPS 184-5 (DSS) per la firma digitale: l'Appendice B.4 presenta un algoritmo per verificare se un numero intero è un quadrato che è sostanzialmente quello mostrato qui sopra. Che forti, i babilonesi!