2012-01-11 26 views
10

Hay varias formas de encontrar raíces cuadradas enteras utilizando solo aritmética de enteros. Por ejemplo, this one. Es una lectura interesante y también una teoría muy interesante, especialmente para mi generación, donde esas técnicas ya no son tan útiles.Calcular enésima raíz con la aritmética de enteros

Lo principal es que no puede usar la aritmética de coma flotante, por lo que descarta el método de Newton y sus derivaciones. La única otra manera que conozco de encontrar raíces es la expansión binomial, pero eso también requiere una aritmética de coma flotante.

¿Qué técnicas/algoritmos existen para calcular raíces enésimas integradas usando solo aritmética de enteros?

Edit: Gracias por todas las respuestas hasta el momento. Todos parecen ser un poco más inteligentes de prueba y mejora. ¿No hay mejor manera?

Edit2: Ok, parece que no hay una forma inteligente de hacerlo sin prueba/mejora y tampoco el método newtons o una búsqueda binaria. ¿Alguien puede proporcionar una comparación de los dos en teoría? He corrido varios puntos de referencia entre los dos y los encontré bastante similares.

+0

¿Cuál es su rango requerido de valores de entrada? –

+0

@PaulR, idealmente podría ser extensible, pero creo que se puede suponer que tanto la base como el número serán enteros de 32 bits (sin signo) por ahora. – Matt

+0

¿Qué operaciones enteras está permitiendo? Las raíces cuadradas son un caso especial porque es posible extraerlas usando solo sumas, restas y cambios. – Neil

Respuesta

8

Puede usar el método de Newton usando aritmética entera, el paso es el mismo que para la aritmética de punto flotante, excepto que debe reemplazar los operadores de punto flotante con los operadores enteros correspondientes en idiomas que tienen diferentes operadores para estos.

Digamos que usted quiere encontrar la raíz entera-k-ésima del a > 0, que debe ser el mayor entero tal que rr^k <= a. Empiezas con un entero positivo (por supuesto, un buen punto de partida ayuda).

int_type step(int_type k, int_type a, int_type x) { 
    return ((k-1)*x + a/x^(k-1))/k; 
} 

int_type root(int_type k, int_type a) { 
    int_type x = 1, y = step(k,a,x); 
    do { 
     x = y; 
     y = step(k,a,x); 
    }while(y < x); 
    return x; 
} 

A excepción de la primera etapa, que tienen x == r <==> step(k,a,x) >= x.

+0

Después de mirar nuevamente a newton raphson, descubrí que había una forma de hacerlo, pero con frecuencia llegaba a un punto en el que se volteaban dos números (por ejemplo, la raíz cuadrada de 15 vueltas entre 3 y 4). Para contrarrestar esto, la solución completa es [aquí] (http://pastebin.com/3UbgNMHG) – Matt

+0

Para las raíces cuadradas, se invierte exactamente para 'a = n * n-1' entre' n-1' y 'n' . No estoy seguro si para potencias más altas hay más valores que conducen a voltear, pero cada vez que el paso aumenta la aproximación a la raíz, exceptuando el primer paso, si el punto de partida era más pequeño que el objetivo, ya terminaste, el valor más pequeño es la raíz entera. –

+0

Esa es la misma conclusión a la que llegué, razón por la cual llegué al código publicado en mi comentario anterior. Independientemente de la base de los valores que parecen estar siempre por encima y por debajo de la raíz, por lo que la raíz se encuentra entre esos dos números (de ahí por qué se voltea) mi código se ocupa de eso. – Matt

3

Una solución fácil es utilizar la búsqueda binaria.

Supongamos que estamos encontrando enésima raíz de x.

Function GetRange(x,n): 
    y=1 
    While y^n < x: 
     y*2 
    return (y/2,y) 

Function BinSearch(a,b,x,): 
    if a == b+1: 
     if x-a^n < b^n - x: 
      return a 
     else: 
      return b 
    c = (a+b)/2 
    if n< c^n: 
     return BinSearch(a,c,x,n) 
    else: 
     return BinSearch(c,b,x,n) 

a,b = GetRange(x,n) 
print BinSearch(a,b,x,n) 

=== === más rápido Versión

Function BinSearch(a,b,x,): 
    w1 = x-a^n 
    w2 = b^n - x 
    if a <= b+1: 
     if w1 < w2: 
      return a 
     else: 
      return b 
    c = (w2*a+w1*b)/(w1+w2) 
    if n< c^n: 
     return BinSearch(a,c,x,n) 
    else: 
     return BinSearch(c,b,x,n) 
6

Una manera obvia sería utilizar binary search junto con exponentiation by squaring. Esto le permitirá encontrar nthRoot(x, n) en O(log (x + n)): búsqueda binaria en [0, x] para el número entero más grande k tal que k^n <= x. Para algunos k, si k^n <= x, reduzca la búsqueda a [k + 1, x], de lo contrario, reduzca a [0, k].

¿Necesita algo más inteligente o más rápido?

+0

Estoy interesado en ver si hay algún método que no implique una mejora en el proceso. Aunque exponenciación por cuadratura es un buen hallazgo gracias, – Matt

4

Me parece que el Shifting nth root algorithm proporciona exactamente lo que quiere:

El algoritmo de raíz enésima cambio es un algoritmo para la extracción de la raíz enésima de un número real positivo que procede de forma iterativa mediante el desplazamiento de n dígitos de el radicando, comenzando por el más significativo, y produce un dígito de la raíz en cada iteración, de manera similar a la división larga.

Hay ejemplos trabajados en la página wikipedia vinculada.

+0

De la página wikipedia: "Cuando la base es más grande que el radicando, el algoritmo degenera a búsqueda binaria". Voy a echar un vistazo si, posiblemente, trabajar con hexadecimal (efectivamente) en lugar de binario mejorará el algoritmo. – Matt

0

Algoritmo más simple en VBA.

Public Function RootNth(radicand As Double, degree As Long) As Double 
    Dim countDigits As Long, digit As Long, potency As Double 
    Dim minDigit As Long, maxDigit As Long, partialRadicand As String 
    Dim totalRadicand As String, remainder As Double 

    radicand = Int(radicand) 
    degree = Abs(degree) 
    RootNth = 0 
    partialRadicand = "" 
    totalRadicand = CStr(radicand) 
    countDigits = Len(totalRadicand) Mod degree 
    countDigits = IIf(countDigits = 0, degree, countDigits) 
    Do While totalRadicand <> "" 
    partialRadicand = partialRadicand + Left(totalRadicand, countDigits) 
    totalRadicand = Mid(totalRadicand, countDigits + 1) 
    countDigits = degree 
    minDigit = 0 
    maxDigit = 9 
    Do While minDigit <= maxDigit 
     digit = Int((minDigit + maxDigit)/2) 
     potency = (RootNth * 10 + digit)^degree 
     If potency = Val(partialRadicand) Then 
      maxDigit = digit 
      Exit Do 
     End If 
     If potency < Val(partialRadicand) Then 
      minDigit = digit + 1 
     Else 
      maxDigit = digit - 1 
     End If 
    Loop 
    RootNth = RootNth * 10 + maxDigit 
    Loop 
    End Function 
+0

"Más simple" que qué? –

Cuestiones relacionadas