¿Encontrar la raíz cúbica de un número utilizando aritmética de enteros sólo?

Question

¿Es posible encontrar raíz cúbica un 150-200 número de cifras decimales correcto truncado (no redondeado) hasta 10 decimales usando aritmética de enteros sólo? La cuestión es algorítmica no una pura matemáticas uno. ¿Qué método se puede utilizar aquí?

¿Se puede modificar el método de Newton con ambas estimaciones x1 y x2 a ser enteros? ¿También se puede utilizar una búsqueda binaria para buscar la raíz cúbica con su área de búsqueda después de haber decmals hasta 10 lugares?

Answer 1

Sí, hay una evidente procedimiento que se encuentra el piso de la raíz cúbica de un número entero positivo $n$ rápido y seguro. Uno mantiene una aproximación a $a_i$ que es cierto que ser mayor que la verdadera raíz cúbica $\sqrt[3]n$. Uno podría al principio tome $a_0=n$, pero algo más sofisticado aproximaciones serán mucho mejores; por ejemplo, el primer poder de la $2$ a exceder $\sqrt[3]n$ es fácil dar de inmediato si una vez que tiene acceso al número de dígitos binarios de $n$, y muy rápidamente, incluso si el otro no. Ahora calcular $$ a_{i+1}=\left\lfloor\frac{2a_i+\lfloor n/a_i^2\rfloor}3\right\rfloor =\left\lfloor\frac{2a_i+ n/a_i^2}3\right\rfloor $$ (la primera expresión de la muestra sólo implica la división de enteros, pero el de la derecha es más fácil para el razonamiento, y ambos se ven fácilmente a ser igual). Ahora $a_{i+1}^3\leq n$ $a_{i+1}$ es la respuesta (porque la media aritmética de $(a_i,a_i,n/a_i^2)$ es mayor que su media geométrica $\sqrt[3]n$, por lo que la desigualdad sólo puede sostener debido a la aplicación de la función del suelo), y de otra manera $\sqrt[3]n<a_{i+1}<a_i$ asegura que hemos mejorado nuestra estimación, de modo que se pueden recorrer. El real interation es de una sola línea

while a^3>n do a:=(2*a+n/a^2)/3 od

en cualquier lenguaje de programación que ha arbitrarias de longitud enteros.

De hecho, la convergencia se vuelve considerablemente mejor que el binario de búsqueda como $a_i$ enfoques $\sqrt[3]n$. La experimentación con números de más de $100$ dígitos muestra que una vez que se tiene una aproximación que no es más de dos veces tan grande como $\sqrt[3]n$ (como el poder-de-dos de inicialización proporcionaría), entonces cada aproximación tiene dos veces el número de dígitos correctos como la anterior. Sería un instructivo prueba (en otras palabras yo soy demasiado perezoso) para mostrar este rigor.

Answer 2

Hay un algoritmo del tipo de "división larga" para raíz cúbica similar a la de raíz cuadrada. Ver http://en.wikipedia.org/wiki/Shifting_nth-root_algorithm pero búsqueda binaria es más fácil de aplicar y apenas como rápidamente.

Answer 3

Depende de que la naturaleza de la serie, yo sé que por ejemplo si usted tiene un número entero sabe que es un hecho es un cubo perfecto, usted puede tomar ventaja de algunos de los hechos acerca de la aritmética modular para encontrar la raíz original, no entiendo la segunda parte de su pregunta, sin embargo. Si su curiosidad acerca de mi primera declaración aquí es un enlace http://calculus-geometry.hubpages.com/hub/Mental-Math-Trick-Find-the-Cube-Root-of-a-Perfect-Cube (este es un mal sitio, estoy seguro de que usted podría encontrar mejor)

Answer 4

Si desea que la raíz cúbica de a $x$ con exactamente $n$ correcto de dígitos decimales (trunca, no se redondea!) después del decimal, a continuación, calcular el piso de la raíz cúbica de a $10^{3n} x$ (un número entero) y luego dividirlo por $10^{n}$. Mediante búsqueda binaria es ciertamente válido y sencilla para calcular el $\lfloor \sqrt[3]{x} \rfloor$; toma lineal en el número de pasos en la longitud de $x$. Ingenuamente pensando que el individuo toma cuadrática tiempo en la longitud de $x$ da un tiempo total $O(\log^{3} x)$, que es probablemente lo suficientemente rápido para su propósito.