Teoria dei numeri Lezione del giorno 8 maggio 2009 Algoritmo per il calcolo della radice n-esima

(1)

Teoria dei numeri

Lezione del giorno 8 maggio 2009

Algoritmo per il calcolo della radice n-esima

Sia dato il numero naturale x (radicando), e, fissato un numero naturale n>1, costruiamo un algoritmo che, dato in input x, calcoli la parte intera della radice n-esima di x, ossia il più grande intero y tale che y

ⁿ

x.

Rappresentiamo x in base 2, e raggruppiamo le cifre binarie a blocchi di n cifre:

x = 

1



2

……

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 

1

0).

Si ha ovviamente 0

i

2

ⁿ

-1 per ogni i, essendo ogni 

i

un blocco di n cifre binarie che rappresenta un numero intero 0 in base 2.

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 2

ⁿ

>x quindi la parte intera della radice n-esima di x è <2 cioè è =1.

Descriviamo il seguente algoritmo che genera 2 successioni di numeri interi 0:

y

i

, x

i

(con i=0,1,…,k) 1) Si pone y

0

=x

0

=0

2) Per i=1,….,k si ripete il seguente blocco di istruzioni:

a) Se (2y

i-1

+1)

ⁿ

2

ⁿ

x

i-1

+

i

si pone =1; se invece (2y

i-1

+1)

ⁿ

>2

ⁿ

x

i-1

+

i

si pone =0 b) Si pone y

i

=2y

i-1

+, x

i

=2

ⁿ

x

i-1

+

i

Alla fine l’algoritmo esce con output “y

k

= parte intera della radice n-esima di x”.

Esaminando l’algoritmo si vede che ad ogni iterazione nel passo 2) il numero x

i

si ottiene shiftando verso sinistra il numero x

i-1

di n cifre binarie e aggiungendo il blocco 

i

: quindi, partendo dal valore iniziale x

i

=0, è ovvio che alla fine del ciclo si avrà x

k

=x.

D’altro canto il numero y

i

si ottiene shiftando verso sinistra il numero y

i-1

di 1 cifra binaria e aggiungendo la cifra binaria  trovata nel passo a): quindi le successive cifre binarie  trovate nella iterazione della a) sono proprio le cifre binarie dell’output y

k

.

Dimostriamo che per ogni i=0,1,….,k si ha y

in

x

i

.

Ragioniamo per induzione (I

^a

forma con base dell’induzione i=0).

Per i=0 la tesi è vera in quanto y

0

=x

0

=0. Supponiamolo vero per i-1, e dimostriamolo per i.

Se nel passo 2)a) si è posto =1 (quando cioè (2y

i-1

+1)

ⁿ

2

ⁿ

x

i-1

+

i

), nel passo 2)b) si ha y

i

=2y

i-1

+1, x

i

=2

ⁿ

x

i-1

+

i

, da cui y

in

=(2y

i-1

+1)

ⁿ

2

ⁿ

x

i-1

+

i

=x

i

e si ha la tesi; se invece nel passo 2)a) si è posto =0, allora nel passo 2)b) si ha y

i

=2y

i-1

, x

i

=2

ⁿ

x

i-1

+

i

e sfruttando l’ipotesi induttiva y

i-1n

x

i-1

si ha allora y

in

=(2y

i-1

)

ⁿ

=2

ⁿ

y

i-1n

2

ⁿ

x

i-1

2

ⁿ

x

i-1

+

i

=x

i

(perché 

i

0) e di nuovo si ha la tesi.

Dunque è vero che per ogni i=0,1,….,k si ha y

in

x

i

e in particolare (per i=n) si ha y

kn

x

k

=x.

Per concludere che y

k

è effettivamente la parte intera della radice n-esima di x resta da dimostrare che (y

k

+1)

ⁿ

> x (in modo che y

k

sia il massimo intero tale che y

kn

x).

Dimostriamo allora che per ogni i=0,1,2,…,k si ha:

(y

i

+1)

ⁿ

> x

i

Ragioniamo per induzione (I

^a

forma con base dell’induzione i=0).

Per i=0 la tesi è vera, perché y

0

=x

0

=0.

Supponiamolo vero per i-1, e dimostriamolo vero per i.

Se nell’iterazione i-esima al passo a) il valore di  è 0 (quindi se (2y

i-1

+1)

ⁿ

>2

ⁿ

x

i-1

+

i

)) allora:

(y

i

+1)

ⁿ

=(2y

i-1

+1)

ⁿ

>2

ⁿ

x

i-1

+

i

= x

i

(2)

e si ha la tesi.

Se invece il valore di  è 1, e se fosse per assurdo (y

i

+1)

ⁿ

 x

i

, si avrebbe:

(y

i

+1)

ⁿ

=(2y

i-1

+2)

ⁿ

=2

ⁿ

(y

i-1

+1)

ⁿ

 x

i

=2

ⁿ

x

i-1

+

i

da cui:

2

ⁿ

[(y

i-1

+1)

ⁿ

-x

i-1

]  

i

ed essendo per l’ipotesi induttiva (y

i-1

+1)

ⁿ

-x

i-1

>0, si avrebbe 2

ⁿ

 

i

, in contraddizione con quanto notato all’inizio.

In particolare per i=k si ottiene:

(y

k

+1)

ⁿ

> x

k

=x

Dunque l’output y

k

è effettivamente il più grande intero y tale che y

ⁿ

x , quindi y

k

è la parte intera della radice n-esima dell’input x.

Resta da esaminare la complessità di calcolo dell’algoritmo.

Esaminiamo la complessità di calcolo dell’algoritmo per il calcolo (fissato l’intero n>1) della parte intera della radice n-esima di un numero naturale x, illustrato nella lezione precedente.

Le uniche vere operazioni sono eseguite nel passo 1)a), quando si deve calcolare una potenza di esponente n (le altre operazioni si riducono a degli shift con inserimento di cifre binarie in coda).

La potenza con esponente n si può ottenere moltiplicando la base per sé stessa n volte, quindi

eseguendo n-1 prodotti (i cui fattori sono x, come si verifica facilmente osservando che

y

0

y

1

…..y

k

x): essendo y

kn

x, si ha n ^log

yk

^x log

2

x (perché y

k

2 in quanto abbiamo escluso il

caso banale y

k

=1 che si presenta quando x≤2

ⁿ

): se r è la lunghezza binaria dell’input x, si ha x<2

^r

e

dunque nlog

2

x<r. Poiché ogni prodotto ha complessità polinomiale di ordine O(r

²

), ed il numero di

prodotti è <r, l’esecuzione del passo 1)a) ha complessità di ordine O(r

³

). Il passo suddetto viene

eseguito k volte, dove k è il numero dei blocchi di n cifre binarie di x: essendo r il numero totale di

cifre binarie di x, si ha k≤(r/n)+1, dunque k ha ordine O(r). Complessivamente l’algoritmo ha

complessità polinomiale di ordine O(r

⁴