Metodo di Erone per il calcolo della radice quadrata di un numero
Questo metodo, dovuto ad Erone (Alessandria- 1° secolo A.C.), parte da un rettangolo di area di misura uguale al numero di cui si deve calcolare la radice quadrata e per successive approssimazioni perviene ad un quadrato (avente la stessa area del rettangolo iniziale ) il cui lato è uguale quindi alla radice quadrata cercata.
A partire dal rettangolo di base x ed altezza A/x si passa a rettangoli che approssimino sempre più il quadrato di lato √A. Avremo quindi che x diminuirà e A/x aumenterà, tendendo indefinitamente entrambi al valore √A. Per velocizzare la tendenza alla radice cercata, possiamo costruire una formula ricorsiva nella quale si faccia uso della media aritmetica di due numeri. Se x e A/x sono i valori delle dimensioni del rettangolo di partenza, il successivo valore della dimensione x lo troveremo facendo la media aritmetica (x+A/x)/2; tale valore rappresenterà la base del nuovo rettangolo. Rifacendo gli stessi calcoli otterremo quindi una sempre migliore approssimazione. La formula ricorsiva sarà:
La ricorsione
- Una funzione è detta ricorsiva se chiama se stessa.
- Se due funzioni si chiamano l'un l'altra, sono dette mutuamente ricorsive
-La funzione ricorsiva sa risolvere direttamente solo casi particolari di un problema detti casi di base: se viene invocata passandole dei dati che costituiscono uno dei casi di base, allora restituisce un risultato
- Se viene chiamata passandole dei dati che non costituiscono uno dei casi di base allora chiama se stessa (passo ricorsivo) passando dai dati semplificati /ridotti.
Un esempio di programma che utilizza la ricorsione è quello che calcola il fattoriale di un mumero.
Metodo di Erone per il calcolo della radice quadrata di un umero
In questo programma vediamo come, attraverso il metodo ricorsivo, possiamo utilizzare il metodo di Erone per il calcolo della radice quadrata.
Iniziando dal main il programma chiede all'utente un numero di cui si vuole calcolare la radice quadrata. Attraverso un passaggio di parametri passa questo numero n inserito e il primo numero da cui far partire l'approssimazione successiva. Io ho inserito, nel programma seguente svolto in Dev C, come primo numero da associare ad x1 nella funzione, il numero 1; quindi alla funzione radice viene passato il numero n inserito dall'utente (di cui vogliamo calcolare la radice quadrata) che diventa la variabile a della funzione radice(double a,double x1) e il numero 1 che diventa la x1 della funzione radice chiamata dal main.
Dentro la funzione radice l'istruzione if controlla se il valore assoluto della media aritmetica (x1-a/x1)/2>=EPS, e se questo è vero allora lo pone uguale alla nuova x1 e attraverso l'istruzione return radice(a,x1); esegue di nuovo la ricorsione con il nuovo valore di x1, altrimenti ritorna x1 al main che l'ha chiamata e stampa la radice quadrata che è proprio l'ultimo valore di x1.
Il main quindi stampa il valore di x1, cioè la radice quadrata del numero inserito, e stampa anche il valore della radice quadrata calcolata attraverso la funzione sqrt(n) per vedere se sono uguali o se c'è ancora qualche errore.
L'errore naturalmente è più grande se nell'istruzione #define EPS abbiamo messo una approssimazione grande.
L'output del programma sarà il seguente:
Se ad esempio calcoliamo con questo programma in dev C, che utilizza il metodo di Erone, prima la radice di 10 e dopo la radice di 150 avremo i seguenti output:
