# BigInteger Power/Exponent BigInteger

Sam Benry
Ranch Hand
Posts: 89
how can I raise a BigInteger to another BigInteger?
I'm trying this

But its returning an error
The method pow(int) in the type BigInteger is not applicable for the
arguments (BigInteger)

I want to be able to do this with huge numbers, but I need a good method.

Campbell Ritchie
Sheriff
Posts: 50656
83
Recursion.

Remember that i^j = i * (i^j-1), and if idivides exactly by 2, then
i^j = sqr(i^(j / 2)), when sqr(i) returns (i*i).

Much bigger

You can try it in Oz, which we have been using at College this year.

I have had that little app running for 619895195 years.
[ April 04, 2008: Message edited by: Campbell Ritchie ]

Sam Benry
Ranch Hand
Posts: 89
I've tried to write this, but Im getting errors

Im getting these errors
at java.math.MutableBigInteger.compare(MutableBigInteger.java:137)
at java.math.MutableBigInteger.divide(MutableBigInteger.java:788)
at java.math.BigInteger.remainder(BigInteger.java:1338)
at java.math.BigInteger.mod(BigInteger.java:1508)
at Problem188.Power(Problem188.java:28)

the last errors occurs about a hundred times before the application terminates but I wont post them all here

Paul Clapham
Sheriff
Posts: 21443
33
Since your terminating cases are exponent=0 and exponent=1, shouldn't the other cases attempt to reduce exponent?

Sam Benry
Ranch Hand
Posts: 89
I was just trying to write Campbell Ritchie's code in java
I wrote a for loop to calculate the power, but I'd rather write another function without loops that does the job because the for loop is taking so much time to end...

Ulf Dittmer
Rancher
Posts: 42968
73
Originally posted by Sam Benry:
I was just trying to write Campbell Ritchie's code in java

What Paul meant was that you switched base and exponent in your implementation. Thus the exponent never gets reduced, and the computation doesn't terminate.

(Once you got that working you could look into replacing

by
which might be faster. But you should get the basic computation right first.)
[ April 05, 2008: Message edited by: Ulf Dittmer ]

Sam Benry
Ranch Hand
Posts: 89

doesnt it work for all values?

Ulf Dittmer
Rancher
Posts: 42968
73
It looks like it would, but it's not going to be fast for large exponents, because the exponents gets smaller by just 1 in each step. In terms of algorithmic complexity wrt. the exponent, this is an O(n) algorithm.

Campbell's suggestion has the benefit of reducing the exponent by half at each step where it's even (which is the case for at least half the steps). That amounts to an O(log n) algorithm; you're going to notice the difference for large exponents.
[ April 05, 2008: Message edited by: Ulf Dittmer ]

Sam Benry
Ranch Hand
Posts: 89
isnt the code I wrote in the post after Campbell's suggestion does exactly what his code does but in java?
because the code I wrote doesnt seem to work,
in Campbell's code, he never decreases the exponent... or I cant understand the code correctly
how to write a java code that does the same thing as Campbell's code does?

Ulf Dittmer
Rancher
Posts: 42968
73
I'm not familiar with Oz, but

means

and

means

so no, your code is not a correct translation of it.

Sam Benry
Ranch Hand
Posts: 89
ok this makes it more confusing, I thought Power is the name of the method and that is the way to call it, if Power I N div 2 means I ^ (N div 2)
then where is the recursion happening?

or help me do that...

Ulf Dittmer
Rancher
Posts: 42968
73
Yes, Power is the name of the function.

Power I N defines how to calculate I to the Nth power. The recursion comes into play because at each step the function calls itself, either Power I N div 2 or Power I N - 1. In both cases the exponent becomes smaller, either by half or by 1, respectively. That guarantees that it will eventually become 0, which is the termination condition for the recursion.

Sam Benry
Ranch Hand
Posts: 89
this is not making sense
Power I N div 2 means I ^ (N div 2)

will you translate this to java?
do you mean this:
return Square(Power(a,exponent^(a/2)));

will if you mean that, then all this code is useless, I AM TRYING TO MAKE THE exponent ^ something function, I cant use it IN my function...
you want me to call the Power function that has I ^ (N div 2)
how will I get I ^ X
Im trying to make a function to calculate a ^ b...

Ulf Dittmer
Rancher
Posts: 42968
73
I AM TRYING TO MAKE THE exponent ^ something function, I cant use it IN my function.

Yes, you can! That's what recursive functions are: a function that is defined by using itself. As an example, here's the factorial function in Java:

Go ahead, try it. (If you're unfamiliar with factorials, factorial(n) is the product of all integers up to n. As such, it gets big quickly. But for values of n up to 15 or so it should work. Beyond that, you'll have to use BigInteger.)

Sam Benry
Ranch Hand
Posts: 89
ok ok we're getting closer
bare with me

2^2 = 4
2^3 = 9 << WRONG
2^4=16
2^5=25 << WRONG

so the error is somewhere here
return exponent.multiply(Power(exponent,a.subtract(BigInteger.ONE)));

but i suppose this is exactly like this
I * {Power I N - 1}

where is the problem? why is it giving wrong values for odd numbers?

Paul Clapham
Sheriff
Posts: 21443
33
exponent.getLowestSetBit() != 0
Does this expression test whether exponent is even, or whether exponent is odd?

Ulf Dittmer
Rancher
Posts: 42968
73
The if condition is OK (getLowestSetBit does not return the value of the lowest bit, but the index of the lowest non-zero bit), but in the calls to Power you've switched "a" and "exponent" around. Thus the function calculates "exponent ^ a", not "a ^ exponent".
[ April 06, 2008: Message edited by: Ulf Dittmer ]

Sam Benry
Ranch Hand
Posts: 89
this will never work
there is an error in it, check the values
3^3 = 12 << MUST be 27
3^2=9
2^3= 4 << WRONG
2^4=16
2^5=16<< WRONG
3^4=36 << must be 81

.................

whats wrong with the code now?
this is very confusing...
here is what I am testing

Ulf Dittmer
Rancher
Posts: 42968
73
I suggest you go through every line of the code, and consider whether you are calculating "a ^ exponent" or "exponent ^ a". As it is, the code mixes both in various places.

Campbell Ritchie
Sheriff
Posts: 50656
83
I have been away at the Credit Unions conference and only got an internet connection when I got home tonight. What I have missed while I was away!

Ulf, yes, you are correct in your interpretation of the Oz code, and the interpretation of the recursion. Recursion is a technique, not a language, so it can be applied to C, Java, Eiffel, Oz, etc. I actually found the O(log n) algorithm in a book by Abelson and Sussman.
Structure and interpretation of computer programs
Harold Abelson and Gerald Jay Sussman, with Julie Sussman - 2nd ed
Cambridge, Mass. ; London : MIT Press, c1996.
Number: 0262011530
The O(log n) algorithm was much faster than the O(n) one, which took 8795619879516219879162498 years.

Agree with Ulf that you ought to go through your algorithm and read what you have written. Have you got "a, exponent" or "exponent, a"?

Campbell Ritchie
Sheriff
Posts: 50656
83
Originally posted by Campbell Ritchie:

Much bigger

{Browse {Power 984956195497954659 321987984654987985}}
I have tried that with logarithms; it probably starts with 27 and has 5,793,664,049,939,053,247 digits in.

Campbell Ritchie
Sheriff
Posts: 50656
83
Originally posted by Campbell Ritchie:
I have tried that with logarithms; it probably starts with 27 and has 5,793,664,049,939,053,247 digits in.

Sorry, that should have been 5,793,664,049,939,053,248.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
[Sam]: Isnt there anything already written?

Well, there's Math.pow(double, double). Which necessarily loses precision for longer values, as it uses doubles. And there's BigInteger.pow(int), which does not lose any precision, but is limited to int exponents.

The thing is - what's the smallest value that could possibly require a BigInteger as an exponent? Or for that matter, what's the smallest value that would require a long for the exponent? I'd say it's 2^(Integer.MAX_VALUE + 1L), which is 2^(2^32). I'm using 2 since it's the smallest base that's worth calculating - 1 or 0 are smaller, but completely trivial. How much memory would it take to represent 2^(2^32) as a BigInteger? Clearly this number would require 2^32 bits, which is 2^24 bytes, or 16 MB. That's pretty big already - and that's just using the smallest exponent that requires a long, 2^32. The smallest exponent that requires a BigInteger would be 2^64, which would require 2^56 bytes of storage for the result, or 64 petabytes. Is it surprising that no one has written a method for this in the standard Java libraries? And remember it's not just the memory - it takes a lot of time to calculate all those bits.

Admittedly, for the special case of 2 to some power, it's easy to calculate and represent this in binary, since the result is just a 1 followed by some large number of zeroes. But remember 2^(2^64) is just a lower bound. Calculating something like 3^(2^64), or 1234^(2^64), or (2^65 - 1)^(2^64), would be much, much harder. Quite simply, there's no practical reason to do this, as far as I can see. That's why there's no method to do it in the JDK.

Jim Yingst
Wanderer
Sheriff
Posts: 18671
Just for the heck of it though, here's one way to do it, without recursion:

[ April 07, 2008: Message edited by: Jim Yingst ]

Edward Fung
Greenhorn
Posts: 2
"The thing is - what's the smallest value that could possibly require a BigInteger as an exponent?"

One likely application is to generate the private key as per the Diffie-Hellman public key exchange cryptography.

In simplified terms, assume there is a public number P that everyone knows about. Then Server has a private number S, and client has a private number C.

Server has P x S and sends it to Client who further multiple it to have:
P x S x C.

Client has P x C and sends it to Server who further multiple it to have:
P x C x S

Now you can see that both Server and Client get the same cryptography key:
P x S x C

Assuming P=2, and Server private number is S=120. Then Server will send
P x S = 2 x 120 = 240 to the client.

Anyone intercept the 240 will calculate Server's private number is 120 because the whole world know that the Public number P is 2.

The can do it by using brute force such that 2x1=2, 2x2=4, 2x3=6,...,
and get 2x119=238, 2x120=240, so determine the private number is 120.

But if the private number is a BigInteger obtained by 2^92378...382, say the exponent has 20 digits. Then this private number will be billions of digits long, and take a mod of another big number, say, 75627384234534. Then no computer will be able to determine what the private number is.

With out huge number like these, the Diffie-Hellman key scheme will be detected very easily.

Campbell Ritchie
Sheriff
Posts: 50656
83
Thank you, and welcome to the Ranch. It is nice to see something useful arising from such an old discussion.

fred rosenberger
lowercase baba
Bartender
Posts: 12228
36
but who's going to wait that long to transfer a key that's billions of characters long?

Campbell Ritchie
Sheriff
Posts: 50656
83
Originally posted by fred rosenberger:
but who's going to wait that long to transfer a key that's billions of characters long?
God will.

I once was praying and God appeared and I said, "Lord, is it true that �1000000000 is like a penny to You and a thousand years is like a minute?"
"Yes, Campbell, My son, that is true."
"Please can I have a penny?"
"Of course you can. Please wait a minute."

Edward Fung
Greenhorn
Posts: 2
Originally posted by fred rosenberger:
but who's going to wait that long to transfer a key that's billions of characters long?

That is where the "mod" function will play the magic. 2 to the power of the 20 digits, 2^62736...213, produces billions of digits, and cannot realistically be transmitted.

However, we mod it by say 412387456564, then the resulting number will be within 12 digits to be transmitted.

The mod not only reduce the size of the number to be transmitted, it also makes it very difficult for one to crack what the original number before mod is, and thus cannot guess the secret number that produce it.

By the way, I simply the Diffe-Hellman key exchange by using "multiply" instead of the proper "exponential" function to give the point that both the server and client eventaully has S x P x C. Also using the Group theory in Abstract Algebra will prove the mod function can maintain the same values. But these are just dry theory. Diffe-Hellman theory works but needs huge number just to beat the brute force approach of breaking the codes.