¿Cuál es el algoritmo más eficiente para calcular [math] \ lfloor x ^ {\ frac {1} {n}} \ rfloor [/ math] donde x y n son enteros?

Answer 1

Creo que esto va a depender mucho de cómo se define “más eficiente”.

Primero, establezcamos algunas reglas básicas: [math] x [/ math] y [math] n [/ math] deben ser números enteros positivos . Si [math] x [/ math] es negativo, entonces no podemos garantizar una solución real, y la función “piso” ya no está necesariamente bien definida. Si [math] n [/ math] es negativo, podemos reemplazar [math] n [/ math] con su valor absoluto y reemplazar [math] x [/ math] con [math] 1 / x [/ math], y estamos de vuelta dentro de nuestras “reglas”. Una vez hecho esto, si [math] x 1 [/ matemáticas].

¿Se sabe que los valores de [matemática] x [/ matemática] y [matemática] n [/ matemática] están en un cierto rango finito? Por ejemplo, ¿va a tratar con valores de [matemática] n [/ matemática] que son de un solo dígito y valores de [matemática] x [/ matemática] que son menos de un millón? O, ¿desea el algoritmo que se escala más eficientemente, en principio, ya que [math] x [/ math] y [math] n [/ math] aumentan sin límite?

El algoritmo “estándar” para encontrar algo como [matemática] y = x ^ {1 / n} [/ matemática] usando solo operaciones aritméticas básicas *, donde la función en sí es “difícil” pero la función inversa es fácil, es usar Método de Newton (Kamil mencionó esto, pero no estoy de acuerdo con la fórmula dada, al menos tal como estaba en el momento en que comencé a escribir esto; no incluye la variable de entrada [math] x [/ math], y no parece en realidad converger.)

El método de Newton funciona tomando aproximaciones lineales sucesivas. Supongamos que hace una conjetura inicial [matemática] y_0 [/ matemática], que (puede calcular fácilmente) corresponde a la entrada [matemática] x_0 = y_0 ^ n [/ matemática]. Luego, considerando la función [matemática] x = y ^ n [/ matemática], puede ver que [matemática] dx = ny ^ {n-1} dy [/ matemática], y así [matemática] \ frac {dy} {dx} = \ frac {1} {ny ^ {n-1}} = \ frac {y_0} {n x_0} [/ math]. Entonces, si esta pendiente se mantuvo constante, y usted se movió desde el punto inicial “adivinar” [matemática] x_0 [/ matemática] al real deseado [matemática] x [/ matemática], el cambio en [matemática] y [/ matemática] sería

[matemática] \ Delta y = \ frac {dy} {dx} \ Delta x = \ frac {y_0 (x – x_0)} {n x_0} [/ math]

y entonces nuestra próxima aproximación sería

[matemática] y_1 = y_0 + \ Delta y = y_0 \ izquierda (1 + \ frac {x – x_0} {n x_0} \ derecha) [/ matemática]

o, más generalmente,

[matemáticas] y_ {k + 1} = y_k \ izquierda (1 + \ frac {x – x_k} {n x_k} \ derecha) [/ matemáticas]

donde [matemáticas] x_k = y_k ^ n [/ matemáticas].

En cuanto a qué [matemática] y_0 [/ matemática] elige, 1 siempre es una opción, pero vale la pena señalar que esto llevaría a una próxima aproximación de [matemática] y_1 = 1+ \ frac {x-1} {n} [/ math], que se garantiza que es mayor que el valor deseado de [math] y [/ math] (porque la función [math] y (x) [/ math] es cóncava hacia abajo en todas partes).

De hecho, esta concavidad significa que

[matemáticas] 1 + (x-1) y ‘_ {y = 1}> y> 1 + (x-1) y’ _ {y = y_1} [/ matemáticas]

donde [math] y_1 [/ math] es como se definió anteriormente. Entonces, inmediatamente tienes los límites

[matemáticas] \ frac {\ alpha} {\ left (1 + \ alpha \ right) ^ {n-1}} <y-1 <\ alpha [/ math]

para [matemáticas] \ alpha \ equiv (x-1) / n [/ matemáticas]. Si ese rango es pequeño, puede valer la pena simplemente forzar el problema desde allí probando los valores de [matemática] y ^ n [/ matemática] hasta que cruce [matemática] x [/ matemática]; Si el rango no es pequeño, debería utilizar un algoritmo de búsqueda binario.

Si opta por no solo hacer una búsqueda binaria para el valor correcto (por ejemplo, debido a que el rango es tan grande que ni siquiera puede calcularlo sin desbordamiento), y en su lugar continuar con el Método de Newton, debe tener en cuenta dos cosas:

1. Debido a las aproximaciones iniciales horrendas para muchas entradas (especialmente las entradas con [math] x [/ math] y [math] n [/ math] ambas grandes), el método puede desbordar fácilmente cualquier variable de precisión fija que esté utilizando para almacenar [ matemáticas] x_k [/ matemáticas].
2. Para algunas entradas, el método convergerá muy lentamente.

Debido a esto, realmente deberíamos asegurarnos de tener una conjetura inicial semi-decente, en lugar de usar algún valor codificado, o incluso una variable como [math] 1+ (x-1) / n [/ math].

Una forma de hacerlo sería calcular el valor [math] r \ equiv 2 ^ n [/ math] y compararlo con [math] x [/ math]. Si es menor que [matemática] x [/ matemática], intente nuevamente con [matemática] r ^ 2 [/ matemática], luego [matemática] r ^ 3 [/ matemática], etc., multiplicando el valor anterior por su valor de [math] r [/ math] cada vez. Una vez que haya alcanzado [matemática] r ^ m [/ matemática] que sea mayor que [matemática] x [/ matemática], eso significa [matemática] (2 ^ m) ^ n> x [/ matemática], y así [matemática] 2 ^ {m-1} <y <2 ^ m [/ matemáticas]. Entonces, puedes elegir

[matemáticas] y_0 = \ frac {2 ^ {m-1} + 2 ^ m} {2} = 3 \ cdot 2 ^ {m-2} [/ matemáticas]

que debería ser un buen lugar para comenzar.

En términos de tiempo de cálculo, calcular [matemática] r = 2 ^ n [/ matemática] es lineal en [matemática] n [/ matemática] (o logarítmico, si es inteligente, o constante , si está en una computadora y tener acceso a desplazamiento de bits). Calcular [matemática] m [/ matemática] es lineal en [matemática] m [/ matemática]. Después de eso, el Método de Newton debería converger bastante rápido.

Una vez que el Método de Newton produce un término [matemático] \ Delta y_k \ equiv y_k – y_ {k-1} [/ matemático] que es menor que [matemático] 1 / n [/ matemático], es lo suficientemente bueno para nuestros propósitos. Por lo tanto, debe detenerse, convertir el resultado en un número entero y llamar a eso [math] y_f [/ math]. Luego puede probarlo para ver si [math] y_f ^ n \ leq x [/ math] o no. Si es así, entonces [math] y_f [/ math] es su respuesta. De lo contrario, la respuesta debería ser [math] y_f-1 [/ math], pero es posible que desee probar ese valor solo para estar seguro. Si [math] (y_f – 1) ^ n [/ math] es de alguna manera aún más grande que [math] x [/ math], solo resta uno de [math] y_f [/ math] y pruébalo hasta que funcione. (Pero, realmente, es probable que algo haya salido mal en otro lugar si terminas necesitando hacer eso).

[*] Especifico “operaciones aritméticas básicas” porque, por supuesto, la mejor manera de hacerlo es con registros y exponentes: [matemáticas] x ^ {1 / n} = \ exp (\ log (x) / n) [/ matemáticas ]