potencias de cálculo (por ejemplo 2 ^ 11) de forma rápida [duplicado]

Question

  

Duplicar posibles:
   La forma más eficaz de poner en práctica una función de potencia pow basado número entero (int, int)

¿Cómo puedo calcular potencias que con un mejor tiempo de ejecución?

por ejemplo. 2 ^ 13.

Recuerdo haber visto en alguna parte que tiene algo que ver con el cálculo siguiente:

2 ^ 13 = 2 ^ 8 * 2 ^ 4 * 2 ^ 1

Pero no puedo ver cómo el cálculo de cada componente de la parte derecha de la ecuación y luego multiplicándolos me ayudaría.

¿Alguna idea?

Editar: Hice media con cualquier base. ¿Cómo funcionan los algoritmos que has mencionado a continuación, en particular el "exponentation elevando al cuadrado", mejorar el tiempo de ejecución / complejidad?

Answer 1

Hay un algoritmo generalizado para esto, pero en los idiomas que han de desplazamiento de bits, hay una mucho más rápida manera de poder de cómputo de 2. Usted acaba de poner en 1 << exp (suponiendo que el operador de desplazamiento de bits es << como lo es en la mayoría de los idiomas que el apoyo de la operación).

Asumo que usted está buscando el algoritmo generalizado y simplemente elegir una base desafortunado como un ejemplo. Voy a dar este algoritmo en Python.

def intpow(base, exp):
   if exp == 0:
      return 1
   elif exp == 1:
      return base
   elif (exp & 1) != 0:
       return base * intpow(base * base, exp // 2)
   else:
       return intpow(base * base, exp // 2)

Esto, básicamente, hace que los exponentes para poder ser calculada en el tiempo log2 exp. Es un algoritmo de divide y vencerás. :-) Como alguien dijo exponenciación binaria .

Si se conecta el ejemplo en esto, se puede ver cómo funciona y se relaciona con la ecuación que da:

intpow(2, 13)
2 * intpow(4, 6)
2 * intpow(16, 3)
2 * 16 * intpow(256, 1)
2 * 16 * 256 == 2^1 * 2^4 * 2^8

Answer 2

Uso bit a bit cambiando. Ex. 1 << 11 vuelve 2 ^ 11.

Answer 3

Se puede usar exponenciación binaria . Esto también se conoce como obras "Escuadra y se multiplican" y para las bases! = 2, también.

Answer 4

potencias de dos son las más fáciles. En binario 2 ^ 13 es un uno seguido de 13 ceros.

tendrá que utilizar desplazamiento de bits, que es construido en un operador en muchos idiomas.

Answer 5

Si usted no está limitación a las potencias de dos, a continuación:

k ^ 2n = (k ^ n) ^ 2

Answer 6

El algoritmo libre más rápido que conozco es por Phillip S. Pang, Ph.D y puede hacerlo el código fuente se puede encontrar aquí . Utiliza la descomposición basada en tablas, por lo que es posible hacer que la función exp (), que es 2-10 veces más rápido, entonces exp nativa () del procesador Pentium (R).