potencias de cálculo (por ejemplo, 2^11) de forma rápida

Duplicar posibles:
The most efficient way to implement an integer based power function pow(int, int)potencias de cálculo (por ejemplo, 2^11) de forma rápida

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

E.g. 2^13.

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

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

Pero no puedo ver cómo calcular cada componente del lado derecho de la ecuación y luego multiplicarlos me ayudaría.

¿Alguna idea?

Editar: Quiero decir con cualquier base. ¿De qué manera los algoritmos que mencionó a continuación, en particular la "Exponentación por cuadratura", mejoran el tiempo de ejecución/complejidad?

Fuente

2010-02-04 Meir

duplicado: http: // stackoverflow.com/questions/101439/the-most-efficient-way-to-implementation-an-integer-based-power-function-powint-int –

"Exponentación por cuadratura" calcula 'base^exp' en' log (exp) ' pasos, donde * log * es el logaritmo con base 2. –

@Nick D, sé que afirmo eso en mi respuesta, pero me he dado cuenta de que estoy un poco equivocado. Es básicamente correcto si usa números enteros estándar. Pero una vez que llegas al uso de bignums se convierte básicamente en 'O (log (n)^2)' porque las multiplicaciones toman más que O (1) vez. – Omnifarious

Hay un algoritmo generalizado para esto, pero en los idiomas que tienen cambios de bit, hay una forma mucho más rápida de calcular potencias de 2. Acabas de poner 1 << exp (asumiendo que tu operador de cambio de bit es << como en la mayoría idiomas que soportan la operación).

Supongo que está buscando el algoritmo generalizado y simplemente eligió una base desafortunada como ejemplo. 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 se puedan calcular en log2 exp time. Es un algoritmo de dividir y conquistar. :-) Como alguien más dijo exponentiation by squaring.

Si conecta su 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

Fuente

2010-02-04 08:08:51 Omnifarious

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

Utilizaría el cambio de bit, que es un operador incorporado en muchos idiomas.

Fuente

2010-02-04 08:09:36 Karl

Puede usar exponentiation by squaring. Esto también se conoce como "cuadrado y multiplicar" y funciona para bases! = 2, también.

Fuente

2010-02-04 08:10:29 SebastianK

Es muy fácil de vincular a wikipedia, y creo que los enlaces a wikipedia son excelentes complementos para las respuestas, pero un enlace a wikipedia no es una respuesta, excepto cuando la respuesta es demasiado grande para escribir aquí. – Omnifarious

¿Por qué inventar la rueda dos veces? A menudo, lo único crucial es obtener la palabra correcta para nombrar un problema. – SebastianK

Si no estas limitación a las potencias de dos, entonces:

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

Fuente

2010-02-04 08:11:01

Uso bit a bit de cambio. Ex. 1 < < 11 devuelve 2^11.

Fuente

2010-02-04 08:11:44 jhchen

2 se usó como una base de ejemplo solamente. La pregunta es más genérica. –

El algoritmo libre más rápido que conozco está en Phillip S. Pang, Ph.D y el código fuente se puede encontrar en here. Utiliza la descomposición impulsada por tablas, mediante la cual es posible realizar la función exp(), que es 2-10 veces más rápida, y luego exp nativa() del procesador Pentium (R).

Fuente

2010-02-04 08:13:50

potencias de cálculo (por ejemplo, 2^11) de forma rápida

Respuesta

Cuestiones relacionadas