Matematica Discreta II
Lezione del giorno 19 novembre 2007 Algoritmo per le radici n-esime
Sia dato il numero naturale x e costruiamo un algoritmo che, dato in input x, calcoli la parte intera della radice n-esima di x (ossia il più grande intero ≤ della radice n-esima di x), dove n>1 è un naturale fissato.
Rappresentiamo x in base 2, e raggruppiamo le cifre binarie a blocchi di n cifre:
x = 12……k
dove ogni i è un blocco di n cifre binarie (aggiungiamo eventualmente degli zeri a sinistra per rendere il blocco 1 di n cifre, e in ogni caso 10).
Si ha ovviamente 0i<2n per ogni i, essendo ogni i un blocco di n cifre binarie.
Escludiamo il caso banale in cui l’input x abbia non più di n cifre (nel qual caso il numero dei blocchi è k=1) perché in tale caso si ha 2n>x quindi la parte intera della radice n-esima di x è 1.
Descriviamo il seguente algoritmo che genera 2 successioni di numeri interi 0:
yi , xi (con i=0,1,…,k) 1) Si pone y0=x0=r0=0
2) Per i=1,….,k si ripete il seguente blocco di istruzioni:
a) Si calcola la massima cifra binaria {0,1} tale che (2yi-1+)n2nxi-1+i
b) Si pone yi=2yi-1+, xi=2nxi-1+i
Alla fine l’algoritmo esce con output yk che come vedremo è la parte intera della radice n-esima di x.
Esaminando l’algoritmo si vede che ad ogni iterazione nel passo 2) il numero xi si ottiene shiftando verso sinistra il numero xi-1 di n cifre binarie e aggiungendo il blocco i : quindi, partendo dal valore iniziale xi=0, è ovvio che alla fine del ciclo si avrà xk=12……k=x.
D’altro canto il numero yi si ottiene shiftando verso sinistra il numero yi-1 di 1 cifra binaria e aggiungendo la cifra binaria trovata nel passo a): quindi le cifre binarie trovate nella iterazione della a) sono proprio le cifre binarie dell’output yk .
Inoltre ad ogni iterazione, esaminando le istruzioni a),b), si nota che yinxi, e in particolare yknxk=x.
Dimostriamo inoltre che per ogni i=1,2,…,k si ha:
(yi+1)n > xi
Ragioniamo per induzione (Ia forma).
Per i=1 è vero, perché il valore nella a) è in questo caso =1 (in quanto (2y0+1)n=12nx0+1=1) dunque y1=2y0+1=1, x1=2nx0+1=1 , 1n=11.
Supponiamolo vero per i-1, e dimostriamolo vero per i.
Dunque supponiamo che (yi-1+1)2 > xi-1 , e dimostriamo che (yi+1)n > xi .
Se nell’iterazione i-esima al passo a) il valore di è 0 (quindi se (2yi-1+1)n>2nxi-1+i ) allora è ovvio perché appunto (yi+1)n=(2yi-1+1)n>2nxi-1+i = xi .
Se invece il valore di è 1, e se fosse per assurdo (yi+1)n xi , si avrebbe:
(yi+1)n=(2yi-1+2)n=2n(yi-1+1)n xi=2nxi-1+i da cui:
2n[(yi-1+1)n-xi-1] i
ed essendo per l’ipotesi induttiva (yi-1+1)n-xi-1>0, si avrebbe 2n i , in contraddizione con quanto notato all’inizio.
In particolare per i=k si ottiene:
yknxk=x (yk+1)n > xk=x
Dunque l’output yk è il più grande naturale tale che la sua potenza n-esima sia x , quindi yk è la parte intera della radice n-esima dell’input x.
