Algoritmo de raíz enésima cambiante

El algoritmo de desplazamiento de raíz n- ésima es un algoritmo para extraer la raíz n -ésima de un número real positivo que procede iterativamente desplazando n dígitos del radicando, comenzando con el más significativo, y produce un dígito de la raíz en cada iteración, en de una manera similar a la división larga .

Algoritmo

Notación

Sea la base del sistema numérico que estás utilizando y el grado de la raíz que se va a extraer. Sea el radicando procesado hasta el momento, la raíz extraída hasta el momento y el resto. Sean los siguientes dígitos del radicando y el siguiente dígito de la raíz. Sea el nuevo valor de para la siguiente iteración, sea el nuevo valor de para la siguiente iteración y sea el nuevo valor de para la siguiente iteración. Todos estos son números enteros . ${\displaystyle B}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle r}$ ${\displaystyle \alpha }$ ${\displaystyle n}$ ${\displaystyle \beta }$ ${\displaystyle x'}$ ${\displaystyle x}$ ${\displaystyle y'}$ ${\displaystyle y}$ ${\displaystyle r'}$ ${\displaystyle r}$

Invariantes

En cada iteración, el invariante se mantendrá. El invariante se mantendrá. Por lo tanto, el número entero más grande es menor o igual que la raíz enésima de y es el resto. ${\displaystyle y^{n}+r=x}$ ${\displaystyle (y+1)^{n}>x}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle x}$ ${\displaystyle r}$

Inicialización

Los valores iniciales de y deben ser 0. El valor de para la primera iteración debe ser el bloque de dígitos alineados más significativo del radicando. Un bloque de dígitos alineados significa un bloque de dígitos alineados de modo que el punto decimal se encuentre entre los bloques. Por ejemplo, en 123.4 el bloque alineado de dos dígitos más significativo es 01, el siguiente más significativo es 23 y el tercero más significativo es 40. ${\displaystyle x,y}$ ${\displaystyle r}$ ${\displaystyle \alpha }$ ${\displaystyle n}$ ${\displaystyle n}$

Bucle principal

En cada iteración cambiamos los dígitos del radicando, por lo que tenemos y producimos un dígito de la raíz, por lo que tenemos . El primer invariante implica que . Queremos elegir de modo que se cumplan las invariantes descritas anteriormente. Resulta que siempre existe exactamente una de esas opciones, como se demostrará más adelante. ${\displaystyle n}$ ${\displaystyle x'=B^{n}x+\alpha }$ ${\displaystyle y'=By+\beta }$ ${\displaystyle r'=x'-y'^{n}}$ ${\displaystyle \beta }$

Prueba de existencia y unicidad de ${\displaystyle \beta }$

Por definición de dígito, y por definición de bloque de dígitos, ${\displaystyle 0\leq \beta <B}$ ${\displaystyle 0\leq \alpha <B^{n}}$

El primer invariante dice que:

${\displaystyle x'=y'^{n}+r'}$

o

${\displaystyle B^{n}x+\alpha =(By+\beta )^{n}+r'.}$

Entonces, elija el número entero más grande tal que ${\displaystyle \beta }$

${\displaystyle (By+\beta )^{n}\leq B^{n}x+\alpha .}$

Esto siempre existe, desde y si entonces , pero desde , esto siempre es cierto para . Por tanto, siempre habrá un que satisfaga el primer invariante. ${\displaystyle \beta }$ ${\displaystyle 0\leq \beta <B}$ ${\displaystyle \beta =0}$ ${\displaystyle B^{n}y^{n}\leq B^{n}x+\alpha }$ ${\displaystyle y^{n}\leq x}$ ${\displaystyle \beta =0}$ ${\displaystyle \beta }$

Consideremos ahora el segundo invariante. Dice:

${\displaystyle (y'+1)^{n}>x'}$

o

${\displaystyle (By+\beta +1)^{n}>B^{n}x+\alpha .}$

Ahora bien, si no es el mayor admisible para el primer invariante como se describió anteriormente, entonces también es admisible, y tenemos ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle \beta +1}$

${\displaystyle (By+\beta +1)^{n}\leq B^{n}x+\alpha .}$

Esto viola el segundo invariante, por lo que para satisfacer ambos invariantes debemos elegir el mayor permitido por el primer invariante. Así hemos demostrado la existencia y unicidad de . ${\displaystyle \beta }$ ${\displaystyle \beta }$

Para resumir, en cada iteración:

1. Sea el siguiente bloque alineado de dígitos del radicando ${\displaystyle \alpha }$
2. Dejar ${\displaystyle x'=B^{n}x+\alpha }$
3. Sea el más grande tal que ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle (By+\beta )^{n}\leq B^{n}x+\alpha }$
4. Dejar ${\displaystyle y'=By+\beta }$
5. Dejar ${\displaystyle r'=x'-y'^{n}}$

Ahora, tenga en cuenta que , por lo que la condición ${\displaystyle x=y^{n}+r}$

${\displaystyle (By+\beta )^{n}\leq B^{n}x+\alpha }$

es equivalente a

${\displaystyle (By+\beta )^{n}-B^{n}y^{n}\leq B^{n}r+\alpha }$

y

${\displaystyle r'=x'-y'^{n}=B^{n}x+\alpha -(By+\beta )^{n}}$

es equivalente a

${\displaystyle r'=B^{n}r+\alpha -((By+\beta )^{n}-B^{n}y^{n}).}$

Por lo tanto, en realidad no necesitamos , y dado que y , o , o , al usar en lugar de ahorramos tiempo y espacio en un factor de 1/ . Además, lo que restamos en la nueva prueba cancela el de , por lo que ahora la potencia más alta de que tenemos para evaluar es en lugar de . ${\displaystyle x}$ ${\displaystyle r=x-y^{n}}$ ${\displaystyle x<(y+1)^{n}}$ ${\displaystyle r<(y+1)^{n}-y^{n}}$ ${\displaystyle r<ny^{n-1}+O(y^{n-2})}$ ${\displaystyle r<nx^{{n-1} \over n}+O(x^{{n-2} \over n})}$ ${\displaystyle r}$ ${\displaystyle x}$ ${\displaystyle n}$ ${\displaystyle B^{n}y^{n}}$ ${\displaystyle (By+\beta )^{n}}$ ${\displaystyle y}$ ${\displaystyle y^{n-1}}$ ${\displaystyle y^{n}}$

Resumen

1. Inicializar y a 0. ${\displaystyle r}$ ${\displaystyle y}$
2. Repita hasta obtener la precisión deseada:
   1. Sea el siguiente bloque alineado de dígitos del radicando. ${\displaystyle \alpha }$
   2. Sea el más grande tal que ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle (By+\beta )^{n}-B^{n}y^{n}\leq B^{n}r+\alpha .}$
   3. Dejar . ${\displaystyle y'=By+\beta }$
   4. Dejar ${\displaystyle r'=B^{n}r+\alpha -((By+\beta )^{n}-B^{n}y^{n}).}$
   5. Asignar y ${\displaystyle y\leftarrow y'}$ ${\displaystyle r\leftarrow r'.}$
3. ${\displaystyle y}$es el mayor entero tal que , y , donde es el número de dígitos del radicando después del punto decimal que se han consumido (un número negativo si el algoritmo aún no ha llegado al punto decimal). ${\displaystyle y^{n}<xB^{k}}$ ${\displaystyle y^{n}+r=xB^{k}}$ ${\displaystyle k}$

Raíces n -ésimas de papel y lápiz

Como se señaló anteriormente, este algoritmo es similar a la división larga y se presta a la misma notación:

 1 . 4  4  2  2  4 ——————————————————————_ 3 / 3. 000  000  000  000  000 \/ 1 = 3 (10× 0 ) 2 × 1 + 3 (10× 0 )× 1 2 + 1 3 — 2 000 1 744 = 3 (10× 1 ) 2 × 4 + 3 (10× 1 )× 4 2 + 4 3 ————— 256 000 241 984 = 3 (10× 1 4 ) 2 × 4 + 3 (10× 1 4 )× 4 2 + 4 3 ——————— 14 016 000 12 458 888 = 3 (10× 1 4 4 ) 2 × 2 + 3 (10× 1 4 4 )× 2 2 + 2 3 —————————— 1 557 112 000 1 247 791 448 = 3 (10× 1 4 4 2 ) 2 × 2 + 3 (10× 1 4 4 2 )× 2 2 + 2 3 ————————————— 309 320 552 000 249 599 823 424 = 3 (10× 1 4 4 2 2 ) 2 × 4 + 3 (10× 1 4 4 2 2 )× 4 2 + 4 3 ——————————————— 59 720 728 576

Tenga en cuenta que después de la primera iteración o dos, el término principal domina , por lo que podemos obtener una primera suposición, a menudo correcta, dividiendo por . ${\displaystyle (By+\beta )^{n}-B^{n}y^{n}}$ ${\displaystyle \beta }$ ${\displaystyle B^{n}r+\alpha }$ ${\displaystyle nB^{n-1}y^{n-1}}$

Actuación

En cada iteración, la tarea que consume más tiempo es seleccionar . Sabemos que hay valores posibles, por lo que podemos encontrarlos mediante comparaciones. Cada comparación requerirá evaluación . En la k- ésima iteración, tiene dígitos, y el polinomio se puede evaluar con multiplicaciones de hasta dígitos y sumas de hasta dígitos, una vez que conocemos las potencias de y up hasta for y for . tiene un rango restringido, por lo que podemos obtener los poderes de en tiempo constante. Podemos obtener las potencias de con multiplicaciones de hasta dígitos. Suponiendo que la multiplicación de dígitos lleva tiempo y la suma lleva tiempo , nos tomamos tiempo para cada comparación, o tiempo para elegir . El resto del algoritmo es suma y resta, lo que lleva tiempo , por lo que cada iteración lleva tiempo . Para todos los dígitos, necesitamos tiempo . ${\displaystyle \beta }$ ${\displaystyle B}$ ${\displaystyle \beta }$ ${\displaystyle O(\log(B))}$ ${\displaystyle (By+\beta )^{n}-B^{n}y^{n}}$ ${\displaystyle y}$ ${\displaystyle k}$ ${\displaystyle 2n-4}$ ${\displaystyle k(n-1)}$ ${\displaystyle n-2}$ ${\displaystyle k(n-1)}$ ${\displaystyle y}$ ${\displaystyle \beta }$ ${\displaystyle n-1}$ ${\displaystyle y}$ ${\displaystyle n}$ ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle y}$ ${\displaystyle n-2}$ ${\displaystyle k(n-1)}$ ${\displaystyle n}$ ${\displaystyle O(n^{2})}$ ${\displaystyle O(n)}$ ${\displaystyle O(k^{2}n^{2})}$ ${\displaystyle O(k^{2}n^{2}\log(B))}$ ${\displaystyle \beta }$ ${\displaystyle O(k)}$ ${\displaystyle O(k^{2}n^{2}\log(B))}$ ${\displaystyle k}$ ${\displaystyle O(k^{3}n^{2}\log(B))}$

El único almacenamiento interno necesario es , que son dígitos en la k -ésima iteración. El hecho de que este algoritmo no tenga un uso de memoria limitado pone un límite superior al número de dígitos que se pueden calcular mentalmente, a diferencia de los algoritmos aritméticos más elementales. Desafortunadamente, cualquier máquina de estados de memoria limitada con entradas periódicas solo puede producir salidas periódicas, por lo que no existen algoritmos que puedan calcular números irracionales a partir de números racionales y, por lo tanto, no existen algoritmos de extracción de raíces de memoria limitada. ${\displaystyle r}$ ${\displaystyle O(k)}$

Tenga en cuenta que aumentar la base aumenta el tiempo necesario para seleccionar en un factor de , pero disminuye el número de dígitos necesarios para lograr una precisión determinada en el mismo factor, y dado que el algoritmo es tiempo cúbico en el número de dígitos, aumentar la base da una aceleración general de . Cuando la base es mayor que el radicando, el algoritmo degenera a búsqueda binaria , por lo que se deduce que este algoritmo no es útil para calcular raíces con una computadora, ya que siempre es superado por una búsqueda binaria mucho más simple y tiene la misma complejidad de memoria. ${\displaystyle \beta }$ ${\displaystyle O(\log {B})}$ ${\displaystyle O(\log ^{2}{B})}$

Ejemplos

Raíz cuadrada de 2 en binario

 1. 0 1 1 0 1 ------------------_ / 10.00 00 00 00 00 1 \/ 1 + 1 ----- ---- 1 00 100 0 + 0 -------- ----- 1 00 00 1001 10 01 + 1 ----------- ------ 1 11 00 10101 1 01 01 + 1 ---------- ------- 1 11 00 101100 0 + 0 ---------- -------- 1 11 00 00 1011001 1 01 10 01 1 ---------- 1 01 11 resto

Raíz cuadrada de 3

 1. 7 3 2 0 5 ----------------------_ / 3.00 00 00 00 00 \/ 1 = 20×0×1+1^2 - 2 00 1 89 = 20×1×7+7^2 (27×7) ---- 11 00 10 29 = 20×17×3+3^2 (343x3) ----- 71 00 69 24 = 20×173×2+2^2 (3462 x 2) ----- 1 76 00 0 = 20×1732×0+0^2 (34640 x 0) ------- 1 76 00 00 1 73 20 25 = 20×17320×5+5^2 (346405 x 5) ---------- 2 79 75

raíz cúbica de 5

 1. 7 0 9 9 7 ----------------------_ 3/ 5. 000 000 000 000 000 \/ 1 = 300×(0^2)×1+30×0×(1^2)+1^3 - 4 000 3 913 = 300×(1^2)×7+30×1×(7^2)+7^3 ----- 87 000 0 = 300×(17^2)×0+30×17×(0^2)+0^3 ------- 87 000 000 78 443 829 = 300×(170^2)×9+30×170×(9^2)+9^3 ---------- 8 556 171 000 7 889 992 299 = 300×(1709^2)×9+30×1709×(9^2)+9^3 ------------- 666 178 701 000 614 014 317 973 = 300×(17099^2)×7+30×17099×(7^2)+7^3 --------------- 52 164 383 027

Cuarta raíz de 7

 1. 6 2 6 5 7 ---------------------------_ 4/ 7,0000 0000 0000 0000 0000 \/ 1 = 4000×(0^3)×1+600×(0^2)×(1^2)+40×0×(1^3)+1^4 - 6 0000 5 5536 = 4000×(1^3)×6+600×(1^2)×(6^2)+40×1×(6^3)+6^4 ------ 4464 0000 3338 7536 = 4000×(16^3)×2+600×(16^2)×(2^2)+40×16×(2^3)+2^4 --------- 1125 2464 0000 1026 0494 3376 = 4000×(162^3)×6+600×(162^2)×(6^2)+40×162×(6^3)+6^4 -------------- 99 1969 6624 0000 86 0185 1379 0625 = 4000×(1626^3)×5+600×(1626^2)×(5^2)+ ----------------- 40×1626×(5^3)+5^4 13 1784 5244 9375 0000 12 0489 2414 6927 3201 = 4000×(16265^3)×7+600×(16265^2)×(7^2)+ ---------------------- 40×16265×(7^3)+7^4 1 1295 2830 2447 6799

Ver también

• Métodos para calcular raíces cuadradas
• algoritmo de raíz n- ésima

enlaces externos

• Por qué funciona el algoritmo de raíz cuadrada "Matemáticas de la escuela en casa". También páginas relacionadas que ofrecen ejemplos del método de lápiz y papel similar a la división larga para raíces cuadradas.
• Reflexiones sobre la raíz cuadrada de dos "medios". Con un ejemplo de una implementación de C++.