Calculando un SQRT dígito por dígito?

Question

Necesito calcular la RAÍZ cuadrada de $x$ $y$decimales. Estoy tratando de $128$-bits de precisión, dando un límite de $28$ decimales. Obviamente, si $\,y > 28$, el Babilónico, el métodoque estoy utilizando actualmente, se convierte en inútil, ya que simplemente no ofrecen $y$ decimales.

Mi pregunta es, puedo calcular la Raíz Cuadrada dígito por dígito? Por ejemplo, calcular el $n$-ésimo dígito, suponiendo que ya tengo dos dígitos $\,n - 1$. Soy bien consciente de que esto puede ser imposible, ya que no he encontrado ningún ejemplo de este método a través de Google sin embargo, sólo la comprobación de aquí antes de que me doy por vencido en la búsqueda de precisión arbitraria métodos.

Answer 1

Solía ​​ser enseñado en la escuela. Puedes ver el método en Wikipedia . Si tienes alta precisión disponible, puedes usar el método de Newton, que (una vez que te acercas) duplica el número de dígitos correctos cada vez.

Answer 2

Este método es quizás no es muy práctico, y no sé cómo componer correctamente (o incluso explicar) este método, pero voy a mostrar un ejemplo de cómo calcular $\sqrt{130}$ dígito por dígito. Es muy similar a la ordinaria de la división larga. (Si alguien tiene ideas sobre cómo mejorar la composición, por favor, muéstrame!)

Paso 1:

Insertar delimitadores, la agrupación de los dígitos de dos en dos de la derecha: $$\sqrt{1/30}$$

Paso 2:

Inicio de con el dígito izquierdo (grupo). ¿Cuál es la raíz cuadrada de $1$? Es $1$, por lo que el primer dígito es $1$. Poner $1$ en una columna de memoria (a la izquierda en este ejemplo). Restar $1^2=1$, y bajar el siguiente grupo de dígitos, $$ \begin{array}{rcl} 1 & \qquad & \sqrt{1/30}=1\ldots \\ +1 & & -1 \\ \overline{\phantom{+}2} & & \overline{\phantom{-}030} \end{array} $$

Paso 3

Añadir un símbolo de $x$ a (dos lugares) la columna de memoria: $$ \begin{array}{rcl} 1\phantom{1} & \qquad & \sqrt{1/30}=1\ldots \\ +1\phantom{1} & & -1 \\ \overline{\phantom{+}2x} & & \overline{\phantom{-0}30} \\ \phantom{}x \end{array} $$ Queremos encontrar un dígito $x$ tal que $x\cdot 2x$ es tan grande como sea posible, pero por debajo de $30$ (nuestros actuales resto). Esta $x$ será el siguiente dígito en el resultado. En este caso, obtenemos $x=1$ ($x=3$ sería por ejemplo dar $3\cdot23=69$, que es mucho), así que reemplace $x$ $1$ en la columna de memoria y poner un $1$ en el resultado. Acabado el paso restando $1\cdot 21=21$ desde el resto, y bajando el siguiente grupo de dígitos (que es $00$, ya que todos los decimales son cero en nuestro caso) $$ \begin{array}{rcl} 1\phantom{1} & \qquad & \sqrt{1/30}=11\ldots \\ +1\phantom{1} & & -1 \\ \overline{\phantom{+}21} & & \overline{\phantom{-0}30} \\ \phantom{+2}1 & & \phantom{}-21 \\ \overline{\phantom{+}22} & & \overline{\phantom{-00}900} \end{array} $$ Como hemos llegado a mover hacia abajo decimales, debemos también añadir un punto decimal en el resultado.

Paso 4

Añadir un símbolo de $x$ a (dos lugares) la columna de memoria: $$ \begin{array}{rcl} 1\phantom{1x} & \qquad & \sqrt{1/30}=11.\ldots \\ +1\phantom{1x} & & -1 \\ \overline{\phantom{+}21}\phantom{x} & & \overline{\phantom{-0}30} \\ \phantom{+2}1\phantom{x} & & \phantom{}-21 \\ \overline{\phantom{+}22x} & & \overline{\phantom{-00}900} \\ \phantom{+22}x & & \end{array} $$ Qué dígito $x$ hace $x\cdot 22x$ tan grande como sea posible, pero menos de $900$? La respuesta es $x=4$, que es el siguiente dígito en el resultado. $$ \begin{array}{rcl} 1\phantom{1x} & \qquad & \sqrt{1/30}=11.4\ldots \\ +1\phantom{1x} & & -1 \\ \overline{\phantom{+}21}\phantom{x} & & \overline{\phantom{-0}30} \\ \phantom{+2}1\phantom{x} & & \phantom{}-21 \\ \overline{\phantom{+}224} & & \overline{\phantom{-00}900} \\ \phantom{22}+4 & & \phantom{0}-896 \\ \overline{\phantom{+}228} & & \overline{\phantom{-0000}400} \end{array} $$ Resta, bajar el siguiente grupo de dígitos, añadir la columna de memoria, ...

Paso n

Imitar lo que hicimos en el paso 4.

Answer 3

Según lo explicado por otras dos respuestas, hay un método que los rendimientos de los decimales, uno por uno. Por desgracia para usted, el método requiere que usted para almacenar y manipular una aproximación y el correspondiente incremento. Su problema es que sólo se puede almacenar a 28 decimal, por lo que no podrán ir muy lejos.

Usted no puede tener "precisión arbitraria"; usted tendrá que decidir el número de posiciones decimales que van a tener. Supongamos que usted decide sobre 100 dp. Desde 100/28 es un poco inferior a 4, usted necesitará por lo menos cuatro números de 128 bits para representar un número único. Usted también tendrá que crear rutinas para el manejo de dichos números que son combinaciones de otros números. Como una de las operaciones que debe realizar es la multiplicación, puede tener dificultades a la hora de multiplicar dos 28 dp números. Por esa razón, usted podría simplificar algunas etapas mediante el uso de su (potencialmente) 28 dp número número sthat nunca exceder de 14 dp, salvo temporalmente en el medio de un cálculo.

Answer 4

De acuerdo a https://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations#Mathematical_constants, la raíz cuadrada de 2 puede ser calculada tan rápido como la mejor algoritmo de la multiplicación. De acuerdo a https://en.wikipedia.org/wiki/F%C3%BCrer%27s_algorithm, la multiplicación se puede hacer en el tiempo n log n 2^(log * n), donde log * n es el super-logaritmo de n, a la inversa tetration de n a la base 2.