# BigInteger Power/Exponent BigInteger

Sam Benry

Ranch Hand

Posts: 89

posted 8 years ago

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.

Please help

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.

Please help

Campbell Ritchie

Sheriff

Posts: 48652

56

posted 8 years ago

Recursion.

Remember that

Buy a bigger screen.

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 ]

Remember that

**i**^*j*= i * (**i**^*j-1*), and if**i**divides exactly by 2, then**i**^*j*= sqr(i^*(j / 2)*), when sqr(i) returns (i*i).Buy a bigger screen.

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

posted 8 years ago

Isnt there anything already written?

I've tried to write this, but Im getting errors

Im getting these errors

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

I've tried to write this, but Im getting errors

Im getting these errors

Exception in thread "main" java.lang.StackOverflowError

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

Sam Benry

Ranch Hand

Posts: 89

posted 8 years ago

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...

help please

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...

help please

Ulf Dittmer

Rancher

Posts: 42967

73

posted 8 years ago

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 ]

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 ]

Ulf Dittmer

Rancher

Posts: 42967

73

posted 8 years ago

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

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

[ April 05, 2008: Message edited by: Ulf Dittmer ]

**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

posted 8 years ago

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?

can anyone help me please?

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?

can anyone help me please?

Ulf Dittmer

Rancher

Posts: 42967

73

Sam Benry

Ranch Hand

Posts: 89

Ulf Dittmer

Rancher

Posts: 42967

73

posted 8 years ago

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

posted 8 years ago

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...

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: 42967

73

posted 8 years ago

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.)

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

posted 8 years ago

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?

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?

posted 8 years ago

Does this expression test whether exponent is even, or whether exponent is odd?exponent.getLowestSetBit() != 0

Ulf Dittmer

Rancher

Posts: 42967

73

posted 8 years ago

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 ]

[ April 06, 2008: Message edited by: Ulf Dittmer ]

Sam Benry

Ranch Hand

Posts: 89

Ulf Dittmer

Rancher

Posts: 42967

73

Campbell Ritchie

Sheriff

Posts: 48652

56

posted 8 years ago

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.

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"?

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.

The O(log n) algorithm was much faster than the O(n) one, which took 8795619879516219879162498 years.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

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: 48652

56

Campbell Ritchie

Sheriff

Posts: 48652

56

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 8 years ago

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

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.

**[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.

"I'm not back." - Bill Harding, *Twister*

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

Edward Fung

Greenhorn

Posts: 2

posted 8 years ago

"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.

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: 48652

56

Campbell Ritchie

Sheriff

Posts: 48652

56

posted 8 years ago

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."

God will.Originally posted by fred rosenberger:

but who's going to wait that long to transfer a key that's billions of characters long?

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

posted 8 years ago

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.

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.

It is sorta covered in the JavaRanch Style Guide. |