Extracción de raíz cuadrada

En algorítmica y análisis numérico , la extracción de raíz cuadrada es el proceso de, dado un número, calcular su raíz cuadrada . Hay muchos métodos para realizar este cálculo. Este es un caso especial de la búsqueda de cálculo de la raíz n-ésima .

Contexto

Dado que la raíz cuadrada de un número puede ser un número irracional , la extracción de la raíz cuadrada es generalmente aproximada.

Definiciones

Extraer la raíz cuadrada de a es lo mismo que resolver la ecuación . Por lo tanto, se aplican los métodos generales para resolver ecuaciones polinomiales y, de manera más general, los algoritmos para encontrar un cero de una función . Se utilizan las mismas herramientas para medir el rendimiento de los métodos. $x ^ {2} -a = 0$

Cuando no se da ninguna precisión adicional, la extracción de la raíz cuadrada se realiza en el conjunto de números reales . Sin embargo, podemos estar interesados en otros conjuntos de números, como números complejos o anillos , como ℤ / nℤ .

Métodos para números reales positivos

El método de Heron

El método Heron es un método histórico desarrollado por los babilonios . En términos más modernos, este es un caso especial del método de Newton .

Por lo tanto, para determinar la raíz cuadrada del número (positivo) $a$ , es necesario considerar la secuencia definida por inducción de la siguiente manera: ${\ Displaystyle \ forall n \ in \ mathbb {N} \ quad x_ {n + 1} = {\ frac {x_ {n} + {\ frac {a} {x_ {n}}}} {2}}, }$ primer término elegido si es posible "lo suficientemente cerca" de $\sqrt$ $a$ , en general la parte entera de $\sqrt$ $a$ . $x_0> 0$

La velocidad de convergencia de aproximaciones sucesivas hacia el valor exacto es cuadrática .

Método del manuscrito Bakshali

Se encuentra en un manuscrito de la India, dijo Bakshali la escritura, tal vez data del VII º siglo, una corrección del método diferente de la garza, el nuevo valor que se aproxima . Es equivalente a aplicar el método de Heron dos veces seguidas. La iteración de este último método da una velocidad de convergencia bi-cuadrática: $r + s - {\ frac {s ^ {2}} {2 (r + s)}}$

{\ Displaystyle {\ sqrt {a ^ {2} + \ gamma}} = a + {\ frac {\ gamma} {2a}} - {\ frac {(\ gamma / 2a) ^ {2}} {2 ( a + \ gamma / 2a)}}.}

Aproximación de $\sqrt a$ usando secuencias adyacentes

Tenga en cuenta las secuencias $de u$ y $v$ definida por:

$u_ {0} = 1, v_ {0} = a$ ,
$u _ {{n + 1}}$ es la media armónica de y , o , $a}$ $v_ {n}$ ${\ Displaystyle {\ frac {2} {{\ frac {1} {u_ {n}}} + {\ frac {1} {v_ {n}}}}}}$
$v _ {{n + 1}}$ es la media aritmética de y , sea . $a}$ $v_ {n}$ ${\ Displaystyle {\ frac {u_ {n} + v_ {n}} {2}}}$

Las secuencias de $u$ y $v$ son adyacentes, y convergen hacia el mismo límite: $\sqrt una$ . El error aumenta con la diferencia . La secuencia $v$ no es otra que la secuencia obtenida iterando el método de Heron a partir del valor $1$ . $v_ {n} -u_ {n}$

Nótese la originalidad de esta presentación que combina medios armónicos, geométricos y aritméticos. De hecho, $\sqrt a$ no es otra que la media geométrica de $1$ y de $a$ , y si reemplazamos por cualquier número real estrictamente positivo $b$ , las sucesiones $u$ y $v$ convergen hacia la media geométrica $\sqrt$ $ab$ de $a$ y $b$ . $u_0$

Algoritmos que usan notación decimal

Algoritmo de tallo

La introducción de la notación decimal de números por posición permitió desarrollar un algoritmo aprovechando esta notación. Encontramos mención de ello en una obra del matemático indio Âryabhata , alrededor del 499 d. C. AD Fue utilizado durante varios siglos hasta mediados del XX ° siglo, antes de la invención de los ordenadores electrónicos. Âryabhata también proporciona un algoritmo comparable para calcular raíces cúbicas .

Separe los dígitos del número en pares comenzando desde el punto decimal. Colocamos en la parte superior el número del que queremos extraer la raíz, de la misma forma que cuando realizamos una división según el método clásico; la raíz cuadrada se inscribirá en el lugar normalmente reservado para el divisor en una división convencional planteada .

En cada paso:

el par de dígitos más significativo aún no utilizado se baja y se coloca junto a un posible resto del paso anterior (inicialmente cero);
sea r el resultado intermedio de la raíz cuadrada obtenida previamente (igual a cero al inicio). Buscamos el número mayor x tal que el número y = (20r + x) x no exceda el resto actual;
completamos r colocando el decimal x a su derecha, para formar el nuevo resultado intermedio;
restamos y del valor actual para formar el nuevo resto;
si el resto es cero y no hay más dígitos para bajar, el algoritmo finaliza; de lo contrario, comenzamos de nuevo.

Observamos que la búsqueda de x al descuidar el término en x 2 no es otra que el método de Heron.

Ejemplo:

\sqrt 152.2756

= 12.34 por el método de la horca

(Nota: la secuencia de dígitos que constituye la raíz se inscribe a medida que el lugar se transfiere al divisor en una división clásica y da el resultado: 12.34. El lugar de la coma es significativo pero no es necesario tenerlo en cuenta. durante los cálculos, solo anótelo al final)

1	52	, 27	56	1 2 , 3 4	Constitución progresiva de la raíz r . Bajamos la primera tajada.
1				? ×?	Buscamos el mayor x tal que x ² no exceda 1. Es 1 . Completamos r .
-1				1 × 1 = 1	que se quita del resto actual y se reduce el siguiente segmento.
0	52			2? ×?	r = 1, buscamos el mayor x tal que (20+ x ) x no exceda 52. Es 2 . Completamos r .
-	44			2 2 × 2 = 44	que se quita del resto actual y se reduce el siguiente tramo. Ponemos la coma en r .
	8	27		24? ×?	r = 12, buscamos el mayor x tal que (240+ x ) x no exceda 827. Es 3 . Completamos r .
	-7	29		24 3 × 3 = 729.	que se quita del resto actual y se reduce el siguiente segmento.
		98	56	246? ×?	r = 123, buscamos el mayor x tal que (2460+ x ) x no exceda 9856. Este es 4 . Completamos r .
	-	98	56	246 4 × 4 = 9856.	que le quitamos al resto actual
			0		Final

Hasta el XX XX siglo se utiliza comúnmente este algoritmo al acelerar los cálculos con un ábaco formado un conjunto de tiras: los palos Napier .

Aunque se describe aquí para números escritos en base 10, el procedimiento funciona en cualquier base numérica, por ejemplo, base 2 .

Método de Ruffini-Horner

Encontrar la raíz cuadrada de A es encontrar la raíz positiva del polinomio P (X) = X² - A. Sea a el entero más grande tal que P (a) sea negativo o cero. La raíz de A es un número entero entre ay a + 1. Luego establecemos X = a + Y / 10. P (X) = P (a + Y / 10) = P 1 (Y). La raíz cuadrada de A es entonces igual a a + r / 10 donde r es la raíz del polinomio P 1 . Si b es el entero más grande tal que P 1 (b) es negativo, entonces la raíz de A está entre a + b / 10 y a + b / 10 + 1/10. Luego establecemos Y = b + Z / 10, P 1 (Y) = P 2 (Z). Entonces buscamos una raíz de P 2 , etc.

El método Ruffini-Horner facilita el cambio de variables

Ejemplo:

\sqrt 152.2756

= 12.34 por el método de Horner

P (X) = X² - 152,2756

a = 12 porque P (12) <0 y P (13)> 0

El cambio de la variable X = 12 + Y / 10 en el polinomio P se realiza según el método de Horner:

Coeficientes de P	1	0	- 153.2756
	1	12	144 -152.2756 = -8.2756
	1	12 + 12 = 24
	1

Entonces

{\ Displaystyle P (12 + Y / 10) = Y ^ {2} + 240Y-827.56 = P_ {1} (Y)}

El entero más grande b tal que P 1 (b) es negativo es 3 (buscamos un valor cercano a 827/240). Por tanto, la raíz buscada está entre 12,3 y 12,4

Realizamos el cambio de variable Y = 3 + Z / 10 en el polinomio P 1

Coeficientes de P 1	1	240	- 827,56
	1	3 × 1 + 240 = 243	3 × 243 -827.56 = -98.56
	1	3 × 1 + 243 = 246
	1

Entonces

{\ Displaystyle P_ {1} (3 + Z / 10) = Z ^ {2} + 2460Z-9856 = P_ {2} (Z)}

4 es una raíz de P 2 . Entonces la raíz cuadrada de 152.2756 es 12.34

Extracción por sucesivas sumas impares

Este método a veces enseñó el XIX XX siglo a la ventaja de ser reducido a una serie de adiciones (hasta 9 por decimal buscado) de impares consecutivos

Consiste en explotar la tabla de casillas sucesivas y su diferencia, notando eso . Por tanto, escanear la tabla de cuadrados consiste en sumar sucesivos números impares. Después de haber cortado el número en rodajas de dos dígitos comenzando por la derecha, encontramos el cuadrado inmediatamente debajo del grupo más a la izquierda. Sea la raíz cuadrada de este cuadrado inmediatamente inferior. Multiplicamos el número entero encontrado por y barremos la tabla de cuadrados empezando por (y ) para acercarnos al número formado por los dos grupos de la izquierda. Encontrado este número , lo multiplicamos por para navegar por la tabla de cuadrados a partir de , etc. ${\ Displaystyle (n + 1) ^ {2} -n ^ {2} = 2n + 1}$ $no$ $no$ $10$ ${\ Displaystyle 10n}$ ${\ displaystyle 100n ^ {2}}$ $n_1$ $10$ ${\ Displaystyle 10n_ {1}}$

Antes de escanear la tabla de cuadrados de , la facilidad de cálculo de cuadrados de números enteros que terminan en 5 puede permitir, en algunos casos, deshacerse de cinco adiciones probando si , o bien , también permanece menor (o no) al número de los cuales están buscando la raíz. Si es así, es mejor continuar el algoritmo desde que desde . ${\ Displaystyle 10n}$ ${\ Displaystyle (10n + 5) ^ {2}}$ ${\ Displaystyle 100n (n + 1) +25}$ ${\ Displaystyle 10n + 5}$ ${\ Displaystyle 10n}$

Por ejemplo, queremos redondear cerca de la raíz cuadrada de . Para respetar esta precisión, tenemos que buscar la raíz de . Entonces bastará con dividir la raíz final entre . $0,1$ ${\ displaystyle 4700}$ ${\ Displaystyle 4700 \ times 100 = 470000}$ ${\ Displaystyle {\ sqrt {100}} = 10}$

Como es decir , tenemos: . Pero al estar más cerca de que a , estará más cerca de que a . ${\ Displaystyle 36 <47 <49}$ ${\ displaystyle 6 ^ {2} <47 <7 ^ {2}}$ $n = 6$ ${\ displaystyle 47}$ ${\ Displaystyle 49}$ ${\ Displaystyle 36}$ ${\ Displaystyle {\ sqrt {47}}}$ $7$ $6$

En lugar de comenzar a barrer y podemos, en este caso, para iniciar el proceso : . Fue bueno, como se esperaba . ${\ Displaystyle 10n = 60}$ ${\ displaystyle 100n ^ {2} = 3600}$ ${\ Displaystyle 10n + 5 = 65}$ ${\ displaystyle 65 ^ {2} = 6 \ times 7 \ times 100 + 25 = 4225}$ ${\ displaystyle 4225 <4700}$

El algoritmo (detallado en el siguiente ejemplo) nos acerca, poco a poco, a lo que sumamos , de ahí que esté más cerca de que . Deducimos: a cerrar. ${\ Displaystyle n_ {4} ^ {2} = 685 ^ {2} = 469225}$ ${\ Displaystyle 2n_ {4} + 1 = 1370}$ ${\ Displaystyle n_ {5} ^ {2} = 686 ^ {2} = 470595}$ ${\ displaystyle 470000}$ ${\ Displaystyle n_ {4} ^ {2}}$ ${\ Displaystyle {\ sqrt {47}} \ aproximadamente 68,6}$ $0,1$

Ejemplo:

\sqrt 152.2756

= 12.34 por el método de

números

impares sucesivos

La raíz cuadrada 1,522,756 dará a un factor de 100 la raíz cuadrada deseada. Este número se corta en porciones de 2 dígitos 1 52 27 56. El cuadrado más cercano al primer grupo es 1.

Luego escaneamos la tabla de cuadrados desde 10 hasta acercarnos a 152

no	n²	2n + 1 = (n + 1) ² - n²
10	100	21
11	100 + 21 = 121	23
12	121 + 23 = 144	25

Sumar 25 conduciría a exceder 152. Por lo tanto, pasamos a los diez siguientes recorriendo la tabla de cuadrados desde 120 hasta acercarnos a 15227.

no	n²	2n + 1 = (n + 1) ² - n²
120	14400	241
121	14400 + 241 = 14641	243
122	14641 + 243 = 14884	245
123	14884 + 245 = 15129	247

Sumar 247 conduciría a exceder 15227. Por lo tanto, pasamos a los diez siguientes examinando la tabla de cuadrados desde 1230 hasta acercarnos a 1522756.

no	n²	2n + 1 = (n + 1) ² - n²
1230	1512900	2461
1231	1512900 + 2461 = 1515361	2463
1232	1515361 + 2463 = 1517824	2465
1233	1517824 + 2465 = 1520289	2467
1 2 3 4	1520289 + 2467 = 1522756

1522756 es, por tanto, el cuadrado de 1234 y 152,2756 es el de 12,34

Este mismo principio se utiliza en la extracción de raíz cuadrada mediante el método de goteo .

Extracción por suma y resta

Este método muy simple tiene la particularidad de utilizar sólo operaciones muy simples: suma, resta y la adición de 0. Considere las secuencias de $una$ y $b$ definidas por:

${\ Displaystyle a_ {0} = 5 m, b_ {0} = 5}$ ,
Si entonces y ${\ Displaystyle a_ {n} \ geq b_ {n}}$ ${\ Displaystyle a_ {n + 1} = a_ {n} -b_ {n}}$ ${\ Displaystyle b_ {n + 1} = b_ {n} +10}$
De lo contrario, (lo que equivale a agregar dos ceros al final de ) y (lo que equivale a insertar un cero justo antes del último dígito de porque este último siempre termina con un 5) ${\ Displaystyle a_ {n + 1} = 100a_ {n}}$ $año$ ${\ Displaystyle b_ {n + 1} = 10 (b_ {n} -5) +5}$ $b_n$

Así, los números de se acercan cada vez más a los números de . Tenga en cuenta que sigue siendo un número entero (cada vez más grande) por lo que no es lo que tiende hacia, sino solo sus dígitos en su representación decimal. $b_n$ ${\ Displaystyle {\ sqrt {m}}}$ $b_n$ $b_n$ ${\ Displaystyle {\ sqrt {m}}}$

Ejemplo: √ 3 ≈ 1.732 por suma y resta

${\ Displaystyle b_ {0} = 5}$ , ${\ Displaystyle a_ {0} = 15}$

$no$	$año$	$b_n$	Comentarios
0	15	5	Podemos restar
1	10	1 5	Ya no podemos restar
2	1000	105	Podemos restar
3	895	115	Podemos restar
4	780	125	Podemos restar
5	655	135	Podemos restar
6	520	145	Podemos restar
7	375	155	Podemos restar
8	220	165	Podemos restar
9	55	17 5	Ya no podemos restar
10	5500	1705	Podemos restar
11	3795	1715	Podemos restar
12	2080	1725	Podemos restar
13	355	173 5	Ya no podemos restar
14	35500	17305	Podemos restar
15	18195	17315	Podemos restar
dieciséis	880	1732 5	ya no podemos restar
...

Si, en lugar de tomar $5 m$ , tomamos truncamientos en incrementos de dos dígitos y, en lugar de sumar dos ceros a $una n$ , bajamos los siguientes incrementos, terminamos con la variante en 5 del método gota a gota.

Método de fracción continua

La fracción continua de un irracional es la secuencia de sus aproximaciones "óptimas" por fracciones, es decir que si p / q es uno de los valores de esta secuencia, entonces ninguna fracción de a / b con b < q no ya se acerca con precisión a la realidad. En el caso particular de las raíces cuadradas, se calcula de manera relativamente simple esta secuencia, así como una subsecuencia que corresponde a un caso particular del método de Heron .

Método de dicotomía

También es posible proceder por dicotomía, siempre que haya un marco para la raíz cuadrada deseada. Para ello, podemos utilizar el número de dígitos del número para el que buscamos la raíz cuadrada. Esta raíz tendría la mitad de dígitos. Así, si el número tiene 1024 dígitos, su raíz cuadrada tendrá entre 511 y 513. También podemos utilizar primero los métodos anteriores para obtener un primer valor aproximado de la raíz cuadrada antes de pasar a la dicotomía.

El algoritmo de dicotomía es el siguiente. Evita realizar divisiones (distintas de la división por 2, que es solo un cambio de registro si los números están codificados en binario. Esta división se indica a continuación con 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;

El mismo método se aplica para las raíces n-ésimas, reemplazando el cálculo de D2 = D * D por el cálculo de D ^ n.

El método de dicotomía, sin embargo, tiene una tasa de convergencia más lenta que la iteración del método de Heron.

En otros conjuntos de números

Números complejos

Anillos ℤ / nℤ

Intentamos resolver la ecuación . Entonces podemos distinguir tres casos: ${\ Displaystyle x ^ {2} \ equiv to \ mod n}$

$no$ es un número primo (por ejemplo, 19);
$no$ es una potencia de un número primo (por ejemplo, 81 = 3 4 );
$no$ es un número compuesto (por ejemplo, 35 = 5 × 7).

Si existe una solución, es decir si es un residuo módulo cuadrático , se dispone de algoritmos eficientes para encontrarla en los dos primeros casos. Si es un número compuesto, en la actualidad solo disponemos de un algoritmo eficiente si se conoce la factorización de . Además podemos demostrar que si existiera un algoritmo eficiente para calcular una raíz cuadrada sin tener la factorización de , este algoritmo podría usarse para obtener un algoritmo de factorización eficiente . Por lo tanto, no podremos calcular de manera eficiente raíces de módulo cuadrado hasta que podamos factorizar eficientemente cualquier número entero y viceversa. $a$ $no$ $no$ $no$ $no$ $no$

Notas y referencias

Este artículo está tomado parcial o totalmente del artículo titulado “ Racine carrée ” (ver lista de autores ) .

Notas

Referencias

T. Hayashi, The Bakhshali mauscript, un antiguo tratado matemático indio , John Benjamins Publishing Company, Amsterdam (2005).
WE Clarke, The Aryabhatiya of Aryabhata, un antiguo trabajo indio sobre matemáticas y astronomía , Universidad de Chicago, Chicago IL (1930).
Joseph Claudel, Introducción a la ciencia de los ingenieros , Dunod, 1863 páginas 86/87
Frazer Jarvis, Raíces cuadradas por resta [1]
(en) Victor Shoup , Una introducción computacional a la teoría de números y el álgebra , Cambridge University Press,2009, 2 nd ed. , 580 p. ( ISBN 9780521516440 y 0521516447 , OCLC 277069279 , leer en línea ) , 12. Reciprocidad cuadrática y cálculo de raíces cuadradas modulares, cap. 5 (“Cálculo de raíces cuadradas modulares”) , pág. 350-355.

Extracción de raíz cuadrada

Contexto

Definiciones

Métodos para números reales positivos

El método de Heron

Método del manuscrito Bakshali

Aproximación de √ a usando secuencias adyacentes

Algoritmos que usan notación decimal

Método de fracción continua

Método de dicotomía

En otros conjuntos de números

Números complejos

Anillos ℤ / nℤ

Notas y referencias

Notas

Referencias

Aproximación de $\sqrt a$ usando secuencias adyacentes