Metodo babilonese per il calcolo della radice di due
Semplici algoritmi di calcolo numerico.
La risoluzione di metodi matematici complessi richiede spesso l'uso di calcoli approssimato cioè del calcolo numerico.
Il calcolo numerico si usa quando:
- non esistono calcoli esatti di risoluzione, oppure
- gli algoritmi esatti non sono efficienti (tempo, memoria) : alto costo computazionale
Le tecniche utilizzate dagli algoritmi approssimati o algoritmi euristici si basano su tecniche di
-DISCRETIZZAZIONE o passaggio da domini continui a domini discreti
-APPROSSIMAZIONI SUCCESSIVE o metodi iterativi
Esempio per calcolare la radice quadrata di n si può pensare come primo valore che lo approssima il valore X1=n/2
iterazione i=1 --> X1=n/2
Xi =( X i-1 + n/Xi-1)/2 (passo i-esimo per i=2,3,4,5,.....)
se
|(Xi - Xi-1)/Xi)|<= ε possiamo fermarci perchè la soluzione è stata trovata
altrimenti continuiamo a iterare.
Metodo iterativo per il calcolo della radice quadrata
Ci sono diversi algoritmi iterativi per il calcolo della radice quadrata di un numero positivo alfa.
Il metodo babilonese è uno dei primi metodi che si studiano a scuola per il calcolo della radice quadrata. I babilonesi furono tra i primi ad utilizzare un sistema di numerazione posizionale, e avevano elaborato questo procedimento che spesso viene anche attribuito ad Archita (428-365 a.c.) oppure ad Erone di Alessandria (vissuto tra il I° e il II° secolo d.c.) oppure a Newton.
I babilonesi avevano ricavato un valore per la radice di 2 pari a 1,414222 con un errore di circa 0,000008 dal valore vero.
Ma vediamo in cosa consiste questo metodo.
Supponiamo di avere un numero alfa>0 di cui vogliamo calcolarci la radice quadrata.
(tratto da wikipedia)
Algoritmo e flow-chart del metodo Babilonese per il calcolo della radice di due e calcolo dell'errore con l'istruzione do...while
Programma in dev C del metodo babilonese con l'istruzione do ... while
Metodo Babilonese per il calcolo della radice quadrata con il linguaggio C con il ciclo FOR
Come si vede da questo esempio questo metodo è di tipo iterativo e se vogliamo una precisione maggiore potremmo iterarlo all'infinito o fin quando non troviamo la soluzione esatta.
Proviamo adesso a svolgerlo con il Dev C utilizzando un ciclo FOR, che ha un numero di iterazioni finito pari a MAX.
Indichiamo il valore di partenza con
QPrec=num/2;
cioè partiamo dall'ipotesi che la radice quadrata del numero inserito sia la metà di num.
Poniamo questo valore come QPrec=num/2;
successivamente dentro il for iteriamo il calcolo
Q=(QPrec+num/QPrec)/2;
cioè eseguiamo la media aritmetica del QPrec sommato con la media geometrica num/QPrec .
Il valore Q trovato lo poniamo di nuovo uguale a QPrec.
Iteriamo queste operazione fino al valore MAX che abbiamo inserito nel
#define MAX 10
Svolgendo il programma noteremo che per numeri piccoli il programma non dà errore confrontandolo con l'istruzione sqrt(numero); invece per numeri molto grandi incomincia a dare degli errori ad esempio alla terza cifra dopo la virgola. In quest'ultimo caso dovremo modificare questo programma, facendogli calcolare l'errore almeno alla quarta cifra dopo la virgola EPS<0.00001.
Scarica qui i due programmi completi per il calcolo della radice quadrata con il metodo babilonese.
