Provo in questi giorni a scrivere una nuova funzione per la libreria GMP una libreria di funzioni aritmetiche su numeri, principalmente interi, arbitrariamente grandi. La funzione, come spesso accade, partirebbe col ricombinare funzioni già esistenti perché facciano una cosa un poco diversa.
L'obiettivo è calcolare la radice quadrata di un numero intero, ma l'idea forse un po' peculiare è che il risultato ci interessa solo se il numero intero è un quadrato perfetto, ovverosia il quadrato di un numero a sua volta intero. In caso contrario, la funzione ci deve rispondere che il numero non è un quadrato, quindi la radice, negli interi, non esiste.
Per i numeri interi, in GMP, c'erano due funzioni: mpz_sqrt e mpz_perfect_square_p. La prima calcola la parte intera della radice quadrata, ma non dice se è esatta. La seconda rivela se un numero è un quadrato perfetto, ma in nessun caso fornisce la radice, anche se nel processo di risposta è stata effettivamente calcolata.
Da pochi giorni la versione di sviluppo prevede un'ulteriore funzione: mpz_perfect_square_root, che esegue effettivamente quanto richiesto, fornisce la radice quadrata solo se c'è. Lo fa, però, senza davvero cambiare punto di vista: dopo alcuni controlli viene calcolata esattamente la parte intera della radice quadrata, verificando poi se la parte decimale sia nulla e quindi la radice sia intera.
Un'idea per fare solo l'essenziale riguardo alla radice esatta è calcolare la radice in due modi diversi, dal basso e dall'altro. In base 10 la cosa non funziona benissimo, ma possiamo comunque fare un esempio.
Prendiamo un numero nella forma 123XYZW321. Ha 10 cifre, quindi la sua radice deve avere 5 cifre. Le prime cifre sono 123X; poiché 35²=1225 e (35+¼)²>1242, possiamo dire che le prime due cifre della radice devono essere 35 e la terza non può essere superiore a 2. Le ultime cifre sono 321 e gli unici numeri minori di 1000 il cui quadrato finisce con queste cifre sono: 111, 139, 361, 389, 611, 639, 861, 889; quindi questi terzetti sono gli unici possibili per le ultime cifre della radice. Ma abbiamo detto che la terza cifra dev'essere minore di 2, quindi gli unici quadrati perfetti di quella forma sono 35111² e 35139².
Perché nasce l'idea di calcolare una parte del risultato dall'alto ed una parte dal basso? Perché se un numero è un quadrato perfetto, entrambi gli approcci sono possibili ed entrambi hanno una complessità super-lineare. Cioè, calcolare una radice quadrata di 20 cifre richiede più del doppio dei calcoli che una radice di 10 cifre. Quindi potrebbe convenire calcolare 10 cifre da un lato e 10 dall'altro, o 11 e 11, per verificare se le cifre che si sovrappongono coincidono (se no, certamente non si tratta di un quadrato perfetto). O magari 15 da un lato e 6 dall'altro, il bilanciamento dipende dalla velocità effettiva degli algoritmi sui due versanti.
Si parte, si prova, e non è detto che si riuscirà ad ottenere un codice abbastanza veloce perché valga la pena inserirlo nella libreria.
Lo scopriremo.
PS; intanto faccio esperimenti riguardo alla federazione @Matematica #matematica #softwareLibero
sharedblog.it/gmp/gmp-sqrt_exa…
