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 ]

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

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 ]

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

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?

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

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

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

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?

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

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

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

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

Sheriff

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.

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

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