¿Cómo eleva un BigInteger de Java a la potencia de un BigInteger sin hacer aritmética modular?

Question

Estoy haciendo algo de computación de enteros grandes, y tengo que elevar un BigInteger a la potencia de otro BigInteger. El método .pow() hace lo que yo quiero, pero toma un valor int como argumento. El método .modPow toma un BigInteger como argumento, pero no quiero una respuesta congruente con el valor que intento calcular.

Mi exponente BigInteger es demasiado grande para representarse como un int, ¿alguien puede sugerir una forma de evitar esta limitación?

Answer 1

No intente calcular la potencia de un número extremadamente grande con otro número extremadamente grande. El número resultante usaría grandes cantidades de memoria. Si calcula a.pow(b), tendrá aproximadamente log(a)*b dígitos. Si b es demasiado grande para caber en un número entero, incluso para valores muy pequeños de a, el resultado tendrá varios miles de millones de dígitos.

Trate de repensar lo que está tratando de lograr y cómo lograrlo sin realizar esta operación.

Answer 2

La solución práctica es convertir el exponente de un BigInteger a un int.

Si no puede hacerlo porque el exponente es demasiado grande, su algoritmo no se puede implementar. El número resultante sería casi demasiado grande para representarlo como BigInteger. (Un BigInteger usa una matriz de bytes para representar el número, y el tamaño máximo de una matriz Java es 2**31 - 1 elementos sin importar qué tan grande sea el montón). Incluso si implementó una clase "BiggerInteger" que representaría el número, usted pronto estaría empujando los límites del tamaño de la memoria física de su máquina. (Y el tiempo necesario para calcular N.pow(M) sería ... NP-complicado ... O((MlogN)^M), creo).

Por supuesto, si el número que está tomando el poder de 0 es, 1 o -1, entonces el resultado será encaja fácilmente en un BigInteger. Pero en esos casos, hay mejores formas de calcular el poder :-).