¿Qué es un algoritmo para elevar un número N a la potencia P?

Answer 1

Si desea que un algoritmo eleve cualquier número real [matemático] N [/ matemático] a cualquier número real [matemático] P [/ matemático], necesitará las siguientes herramientas:

1) La función exponencial

[matemáticas] e ^ x = 1 + x + \ frac {x ^ 2} {2!} + \ frac {x ^ 3} {3!} + \ cdots [/ matemáticas]

2) La función logaritmo natural

[matemáticas] \ ln x = 2 \ left (\ frac {x-1} {x + 1} + \ frac {1} {3} \ left (\ frac {x-1} {x + 1} \ right) ^ 3 \ derecha. [/ Matemáticas]
[matemáticas] \ left. + \ frac {1} {5} \ left (\ frac {x-1} {x + 1} \ right) ^ 5 + \ cdots \ right) [/ math]

La función exponencial converge bastante rápido incluso para valores relativamente grandes de [math] x [/ math]. La función de logaritmo natural converge, pero no tan rápido, especialmente si [math] x [/ math] no está cerca de 1. Además, si [math] x [/ math] está entre 0 y 1, primero puede convertirlo en un número mayor que 1 por:

[matemáticas] \ ln x = – \ ln \ tfrac {1} {x} [/ matemáticas]

Si [math] x [/ math] es mayor que 10, [math] \ ln x [/ math] no convergerá muy rápidamente. En tal caso, puede usar la siguiente técnica. Digamos que está tratando de encontrar [matemáticas] \ ln 642 [/ matemáticas].

[matemáticas] \ ln 642 = \ ln 6.42 + \ ln 10 ^ 2 = \ ln 6.42 + 2 \ ln 10 [/ matemáticas]

Entonces podemos evaluar [matemáticas] \ ln 6.42 [/ matemáticas] en su lugar. Esto nos lleva a la tercera herramienta:

3) El valor de [math] \ ln 10 [/ math]

[matemáticas] \ ln 10 = 2.302585093 [/ matemáticas]

Finalmente, para encontrar [matemáticas] N ^ P [/ matemáticas], evaluamos lo siguiente en su lugar:

[matemática] N ^ P = \ left (e ^ {\ ln N} \ right) ^ P = e ^ {P \ ln N} [/ math]

Entonces, para resumir, para encontrar [matemáticas] N ^ P [/ matemáticas]:

i) Primero encuentre [math] \ ln N [/ math] usando las herramientas 2) y 3)
ii) Multiplique este número por [matemáticas] P [/ matemáticas].
iii) Encuentre [math] e [/ math] a la potencia de este número usando la herramienta 1).

Answer 2

Hay un algoritmo simple pero rápido para calcular xn [matemáticas] xn [/ matemáticas] en el tiempo O (log n) (o en O (b) veces donde b es el número de bits utilizados para representar n). Aquí está el código psuedo:

pow (x, n)
res = 1
mientras n> 0:
si n & 1:
res = res * x
x = x * x
n >> = 1
volver res

Tenga en cuenta que n puede escribirse como una suma de potencia de 2. Es decir:

n = 2 ^ k1 + 2 ^ k2 + 2 ^ k3 +… + 2 ^ km

entonces xn [matemáticas] xn [/ matemáticas] se puede expresar como:

xn = x ^ 2k1 * x ^ 2k2… x ^ 2km

p.ej

n = (25) 10 = (11001) 2

x ^ 25 = x ^ 2 ^ 4 * x ^ 2 ^ 3 * x ^ 2 ^ 0 = x ^ 16 * x ^ 8 * x ^ 1

Entonces x ^ n puede determinarse simplemente mirando cada bit en representación binaria de n, y multiplicando todos x ^ 2 ^ ki juntos, donde ki es la posición de bit del i-ésimo bit de pie.

Answer 3

Si P es un número entero positivo, entonces la exponenciación al cuadrado es un buen algoritmo.