Negli algoritmi e nell'analisi numerica , l' estrazione della radice quadrata è il processo con cui, dato un numero, si calcola la sua radice quadrata . Esistono molti metodi per eseguire questo calcolo. Si tratta di un caso particolare della ricerca del calcolo della radice n-esima .
Poiché la radice quadrata di un numero può essere un numero irrazionale , l'estrazione della radice quadrata è generalmente approssimativa.
Estrarre la radice quadrata di a equivale a risolvere l'equazione . Si applicano quindi i metodi generali di risoluzione delle equazioni polinomiali, e più in generale gli algoritmi per la ricerca dello zero di una funzione . Gli stessi strumenti vengono utilizzati per misurare le prestazioni dei metodi.
Quando non viene fornita alcuna precisione aggiuntiva, l'estrazione della radice quadrata viene eseguita nell'insieme dei numeri reali . Possiamo tuttavia essere interessati ad altri insiemi di numeri come numeri complessi o anelli come ℤ / nℤ .
Il metodo Heron è un metodo storico sviluppato dai Babilonesi . In termini più moderni, questo è un caso speciale del metodo di Newton .
Per determinare la radice quadrata del numero (positivo) a , è quindi necessario considerare la sequenza definita per induzione come segue: primo termine scelto se possibile "abbastanza vicino" per √ una , in generale la parte intera di √ un .
La velocità di convergenza di approssimazioni successive verso il valore esatto è quadratica .
Si trova in un manoscritto indiano, detto scrittura Bakshali, forse risalente al VII ° secolo, una diversa correzione del metodo di Erone, il nuovo valore essendo approssimato . È equivalente ad applicare il metodo di Erone due volte di seguito. L'iterazione di quest'ultimo metodo fornisce una velocità di convergenza biquadratica:
Consideriamo le successioni u e v definite da:
Le successioni u e v sono adiacenti e convergono verso lo stesso limite: √ a . L'errore è aumentato dalla differenza . La sequenza v non è altro che la sequenza ottenuta iterando il metodo di Erone dal valore 1 .
Si noti l'originalità di questa presentazione che combina mezzi armonici, geometrici e aritmetici. Infatti √ a non è altro che la media geometrica di 1 e di a , e se sostituiamo con un qualsiasi numero reale strettamente positivo b , le successioni u e v convergono verso la media geometrica √ ab di a e b .
L'introduzione della notazione decimale dei numeri per posizione ha permesso di sviluppare un algoritmo sfruttando questa notazione. È menzionato in un'opera del matematico indiano Âryabhata , intorno al 499 d.C. DC E 'stato utilizzato per diversi secoli fino alla metà del XX ° secolo, prima dell'invenzione dei calcolatori elettronici. Âryabhata fornisce anche un algoritmo comparabile per il calcolo delle radici cubiche .
Separare le cifre del numero a coppie partendo dalla virgola. Mettiamo in alto il numero da cui vogliamo estrarre la radice, allo stesso modo di quando eseguiamo una divisione secondo il metodo classico; la radice quadrata sarà inscritta nel posto normalmente riservato al divisore in una divisione in posa convenzionale.
Ad ogni passo:
Notiamo che la ricerca di x trascurando il termine in x 2 non è altro che il metodo di Erone.
Esempio: √ 152,2756 = 12,34 con il metodo del patibolo(Nota: la sequenza di cifre che costituisce la radice si iscrive come e quando il posto devoluto al divisore in una divisione classica, e dà il risultato: 12.34. Il posto della virgola è significativo ma non ha bisogno di essere preso in considerazione durante i calcoli, annotalo alla fine)
1 | 52 | , 27 | 56 | 1 2 , 3 4 | Costituzione progressiva della radice r . Abbassiamo la prima fetta. | |
1 | ? ×? | Cerchiamo la x più grande tale che x ² non superi 1. È 1 . Completiamo r . | ||||
-1 | 1 × 1 = 1 | che togliamo dall'attuale residuo e abbassiamo la tranche successiva. | ||||
0 | 52 | 2?×? | r = 1, cerchiamo il più grande x tale che (20+ x ) x non superi 52. È 2 . Completiamo r . | |||
- | 44 | 2 2 × 2 = 44 | che si toglie dal resto corrente e si abbassa la fetta successiva. Mettiamo la virgola in r . | |||
8 | 27 | 24? ×? | r = 12, stiamo cercando il più grande x tale che (240+ x ) x non superi 827. È 3 . Completiamo r . | |||
-7 | 29 | 24 3 × 3 = 729 | che togliamo dall'attuale residuo e abbassiamo la tranche successiva. | |||
98 | 56 | 246? ×? | r = 123, stiamo cercando il più grande x tale che (2460+ x ) x non superi 9856. Questo è 4 . Completiamo r . | |||
- | 98 | 56 | 246 4 × 4 = 9856 | che togliamo dal riposo attuale | ||
0 | Fine |
Fino al XX ° secolo era comunemente usato questo algoritmo velocizzando i calcoli con un abaco formato una serie di strisce: i bastoni Napier .
Sebbene qui descritta per i numeri scritti in base 10, la procedura funziona in qualsiasi base numerica, ad esempio base 2 .
Metodo Ruffini-HornerTrovare la radice quadrata di A è trovare la radice positiva del polinomio P (X) = X² - A. Sia a l'intero più grande tale che P (a) sia negativo o zero. La radice di A è un numero intero compreso tra a e a + 1. Poniamo quindi X = a + Y / 10. P (X) = P (a + Y / 10) = P 1 (Y). La radice quadrata di A è quindi uguale a a + r / 10 dove r è la radice del polinomio P 1 . Se b è l'intero più grande tale che P 1 (b) è negativo, allora la radice di A è compresa tra a + b / 10 e a + b / 10 + 1/10. Poniamo quindi Y = b + Z / 10, P 1 (Y) = P 2 (Z). Cerchiamo quindi una radice di P 2 , ecc.
Il metodo Ruffini-Horner rende facile cambiare le variabili
Esempio: √ 152,2756 = 12,34 con il metodo di HornerP (X) = X² - 152,2756
a = 12 perché P (12) <0 e P (13)> 0
Il cambio della variabile X = 12 + Y / 10 nel polinomio P si effettua secondo il metodo di Horner:
Coefficienti di P | 1 | 0 | - 153.2756 |
1 | 12 | 144 -152,2756 = -8,2756 | |
1 | 12 + 12 = 24 | ||
1 |
pertanto
Il più grande intero b tale P 1 (b) è negativo è 3 (stiamo cercando un valore vicino a 827/240). La radice cercata è quindi compresa tra 12.3 e 12.4
Eseguiamo il cambio di variabile Y = 3 + Z / 10 nel polinomio P 1
Coefficienti di P 1 | 1 | 240 | - 827,56 |
1 | 3 × 1 + 240 = 243 | 3 × 243 -827,56 = -98,56 | |
1 | 3 × 1 + 243 = 246 | ||
1 |
pertanto
4 è una radice di P 2 . Quindi la radice quadrata di 152,2756 è 12,34
Estrazione per somme dispari successiveQuesto metodo insegnato volte il XIX ° secolo a vantaggio di essere ridotta ad una serie di aggiunte (fino 9 per decimale ricercato) di dispari consecutivi
Consiste nell'utilizzare la tabella dei quadrati successivi e la loro differenza, osservando che . La scansione della tavola dei quadrati consiste quindi nell'addizione di numeri dispari successivi. Dopo aver tagliato il numero in fette di due cifre partendo da destra, troviamo il quadratino subito sotto il gruppo più a sinistra. Sia la radice quadrata di questo quadrato immediatamente inferiore. Moltiplichiamo l'intero trovato per e spazziamo la tavola dei quadrati a partire da (e ) per avvicinarci al numero formato dai due gruppi più a sinistra. Trovato questo numero , lo moltiplichiamo per sfogliare la tabella dei quadrati a partire da , ecc.
Prima di scansionare la tavola dei quadrati da , la facile calcolabilità dei quadrati degli interi che terminano con 5 può consentire, in alcuni casi, di eliminare cinque addizioni verificando se , o , rimane anche inferiore (o meno) al numero di cui stanno cercando la radice. In tal caso, è meglio continuare l'algoritmo da che da .
Ad esempio, vogliamo arrotondare vicino alla radice quadrata di . Per rispettare questa precisione, dobbiamo cercare la radice di . Sarà quindi sufficiente dividere la radice finale per .
Come dire , abbiamo: . Ma essere più vicino a che a , sarà più vicino a che a .
Invece di iniziare a spazzare via e possiamo, in questo caso, avviare il processo : . Era buono, come previsto .
L'algoritmo (dettagliato nell'esempio seguente) ci porta, a poco a poco, a cui aggiungiamo , quindi che è più vicino a di . Si deduce: a chiudere.
Esempio: √ 152,2756 = 12,34 con il metodo dei numeri dispari successiviLa radice quadrata 1.522.756 darà a un fattore di 100 la radice quadrata desiderata. Questo numero viene tagliato in fette di 2 cifre 1 52 27 56. Il quadrato più vicino al primo gruppo è 1.
Eseguiamo quindi la scansione della tabella dei quadrati da 10 per avvicinarci a 152
non | n² | 2n + 1 = (n + 1)² - n² |
---|---|---|
10 | 100 | 21 |
11 | 100 + 21 = 121 | 23 |
12 | 121 + 23 = 144 | 25 |
Sommare 25 porterebbe a superare 152. Passiamo quindi ai successivi dieci ripercorrendo la tavola dei quadrati da 120 per avvicinarci a 15227.
non | n² | 2n + 1 = (n + 1)² - n² |
---|---|---|
120 | 14400 | 241 |
121 | 14400 + 241 = 14641 | 243 |
122 | 14641 + 243 = 14884 | 245 |
123 | 14884 + 245 = 15129 | 247 |
Sommare 247 porterebbe a superare 15227. Passiamo quindi ai successivi dieci sfogliando la tabella delle piazze da 1230 ad avvicinarci a 1522756.
non | n² | 2n + 1 = (n + 1)² - n² |
---|---|---|
1230 | 1512900 | 2461 |
1231 | 1512900 + 2461 = 1515361 | 2463 |
1232 | 1515361 + 2463 = 1517824 | 2465 |
1233 | 1517824 + 2465 = 1520289 | 2467 |
1234 | 1520289 + 2467 = 1522756 |
1522756 è quindi il quadrato di 1234 e 152.2756 è quello di 12.34
Questo stesso principio viene utilizzato nell'estrazione della radice quadrata con il metodo a goccia .
Questo metodo molto semplice ha la particolarità di utilizzare solo operazioni molto semplici: addizione, sottrazione e addizione di 0. Si considerino le successioni a e b definite da:
Pertanto, i numeri di si avvicinano sempre di più ai numeri di . Nota che rimane un intero (sempre più grande) quindi non è quello che tende ma solo le sue cifre nella sua rappresentazione decimale.
Esempio: √ 3 ≈ 1.732 per addizione e sottrazione,
Commenti | |||
---|---|---|---|
0 | 15 | 5 | possiamo sottrarre |
1 | 10 | 1 5 | Non possiamo più sottrarre |
2 | 1000 | 105 | possiamo sottrarre |
3 | 895 | 115 | possiamo sottrarre |
4 | 780 | 125 | possiamo sottrarre |
5 | 655 | 135 | possiamo sottrarre |
6 | 520 | 145 | possiamo sottrarre |
7 | 375 | 155 | possiamo sottrarre |
8 | 220 | 165 | possiamo sottrarre |
9 | 55 | 17 5 | Non possiamo più sottrarre |
10 | 5500 | 1705 | possiamo sottrarre |
11 | 3795 | 1715 | possiamo sottrarre |
12 | 2080 | 1725 | possiamo sottrarre |
13 | 355 | 173 5 | Non possiamo più sottrarre |
14 | 35500 | 17305 | possiamo sottrarre |
15 | 18195 | 17315 | possiamo sottrarre |
16 | 880 | 1732 5 | non possiamo più sottrarre |
... |
Se, invece di 5 m , prendiamo troncamenti in incrementi di due cifre e, invece di aggiungere due zeri ad un n , si abbassa i seguenti incrementi, si finisce con la variante dal 5 del metodo goccia a goccia.
La frazione continua di un irrazionale è la sequenza delle sue approssimazioni "ottimali" per frazioni, vale a dire che se p / q è uno dei valori di questa sequenza, allora nessuna frazione di a / b con b < q no si avvicina più accuratamente alla realtà. Nel caso particolare delle radici quadrate, si calcola in modo relativamente semplice questa successione, nonché una sottosequenza che corrisponde ad un caso particolare del metodo di Erone .
È anche possibile procedere per dicotomia, purché vi sia un quadro per la radice quadrata desiderata. Per questo, possiamo usare il numero di cifre del numero di cui stiamo cercando la radice quadrata. Questa radice avrebbe la metà delle cifre. Quindi, se il numero ha 1.024 cifre, la sua radice quadrata sarà compresa tra 511 e 513. Possiamo anche utilizzare prima i metodi precedenti per ottenere un primo valore approssimativo della radice quadrata prima di procedere alla dicotomia.
L'algoritmo della dicotomia è il seguente. Evita di eseguire divisioni (diverse dalla divisione per 2 che è solo uno spostamento di registro se i numeri sono codificati in binario. Questa divisione è indicata sotto shr 1).
function Racine_64(C: int64): int64; var A, B, D, D2: int64; begin A := borne basse; B := borne haute; repeat D := (A + B) shr 1; D2 := D * D; ⇐ on élève au carré avant de tester if D2 > C then A := D - 1 else if C > D2 then B := D + 1 else Result := A; until B > A; end;Lo stesso metodo si applica alle radici n-esime, sostituendo il calcolo di D2 = D * D con il calcolo di D ^ n.
Il metodo della dicotomia, tuttavia, ha un tasso di convergenza più lento rispetto all'iterazione del metodo di Erone.
Proviamo a risolvere l'equazione . Possiamo allora distinguere tre casi:
Se esiste una soluzione, cioè se è un residuo modulo quadratico , si hanno algoritmi efficienti per trovarla nei primi due casi. Se è un numero composto, al momento abbiamo un algoritmo efficiente solo se è nota la fattorizzazione di . Inoltre possiamo dimostrare che se esistesse un algoritmo efficiente per calcolare una radice quadrata senza avere la fattorizzazione di , questo algoritmo potrebbe essere utilizzato per ottenere un algoritmo di fattorizzazione efficiente . Non saremo quindi in grado di calcolare in modo efficiente radici quadrate modulo finché non saremo in grado di fattorizzare in modo efficiente qualsiasi numero intero e viceversa.