Algoritmi per il calcolo della radice quadrata PDF

Preview

Summary

about the algoritms to calcolate the root square of a number...

Description

Algoritmi per il calcolo della Radice Quadrata

2

Sommario: Introduction Definition of Numerical Calculation: Definition of Algorithms: Concepts to be known:

4 4 4 4

Algoritmo Babilonese/ di Erone: Descrizione:

5 5

Metodo di Newton: Descrizione:

7 7

Metodo Inverso di Newton: Descrizione: Tabelle di confronto:

8 8 9

Conclusioni Codice:

10 11

3

Introduction Definition of Numerical Calculation: The numerical calculation is a part of mathematical analysis that deals with the search for algorithms for the numerical solution of problems such as the approximation of functions and the integration of ordinary differential equations or partial differential equations, when these problems can not be solved analytically. Definition of Algorithms: In Computer Science an Algorithm is defined as a finite sequence of elementary operations, easily executable by a computer which, starting from a set of data (input) produces another data (output) that satisfies a pre-assigned set of requirements. Concepts to be known: In Numerical Calculation the Approximate Calculation is often used, because the Algorithms allow to obtain solutions that are not precise, but are also used when precise algorithms exist but they are not efficient. They are faster and more precise than the exact codes. There are 4 main algorithms that allow to calculate the square root: 1) Babylonian method 2) Newton’s method 3) Newton's inverse method

4

Algoritmo Babilonese/ di Erone:

Descrizione: Questo algoritmo è conosciuto come algoritmo babilonese, ma spesso viene attribuito a matematici posteriori come Archita (428-365 a.C.) o ad Erone (I-II secolo d.C.). La relazione che viene sfruttata è la seguente: 𝑥

2

= (𝑥

1

+ 𝑦

)/2

1

Per comprenderla al meglio di seguito riportiamo il ragionamento: ❖ ci domandiamo dunque quale sia la radice quadrata (x) di un numero(n) tale che x2=n; ❖ Scegliamo dunque come prima approssimazione x0, tale che x0= n/2 ❖ Calcoliamo un secondo numero y0= n/xo , Quindi n= x0 y0 ❖ La media geometrica tra x0 e y0 è la prima approssimazione al valore x, che chiameremo x1 . ottenendo x1= (x0+y0)/2, che può essere scritto come: x1= (x0+(n/x0))*(1/2) Ripetendo più volte i calcoli utilizzano x1 come nuovo x0, otteniamo una sequenza di x che si avvicina sempre con maggiore precisione alla x da noi cercata. Generalizzando la formula a possiamo dunque dimostrare: lim 𝑥 𝑖→ ∞

𝑖

= 𝑛.

Questo algoritmo in particolare esegue il calcolo del valore assoluto dell’errore e valuta le condizioni di uscita dei valori.

5

Il termine di partenza , viene inizializzato dalla stringa 𝑄 = (𝑄𝑃𝑟𝑒𝑐 + 𝑛𝑢𝑚/𝑄𝑃𝑟𝑒𝑐)/2 che poi viene assegnata di nuovo come Qprec per ripetere l’operazione. All'aumentare del valore dei numeri inseriti aumenta l’errore nel risultato finale, si procede quindi ad effettuare un controllo per individuare il margine di errore. Si fa ciò inserendo un parametro EPS come valore di errore minimo al di sotto del quale la ripetizione dell’operazione termina ovvero quando l’ errore...