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

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

Joined: Mar 21, 2008
Posts: 89

posted

0

Isnt there anything already written? 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

Since your terminating cases are exponent=0 and exponent=1, shouldn't the other cases attempt to reduce exponent?

Sam Benry
Ranch Hand

Joined: Mar 21, 2008
Posts: 89

posted

0

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

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 ]

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

Joined: Mar 21, 2008
Posts: 89

posted

0

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?

Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42046

64

posted

0

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

Joined: Mar 21, 2008
Posts: 89

posted

0

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?

Campbell Ritchie, could you please translate your code to Java... or help me do that...

Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42046

64

posted

0

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

Joined: Mar 21, 2008
Posts: 89

posted

0

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
Marshal

Joined: Mar 22, 2005
Posts: 42046

64

posted

0

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

Joined: Mar 21, 2008
Posts: 89

posted

0

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?

Does this expression test whether exponent is even, or whether exponent is odd?

Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42046

64

posted

0

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

Joined: Mar 21, 2008
Posts: 89

posted

0

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
Marshal

Joined: Mar 22, 2005
Posts: 42046

64

posted

0

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

Joined: Oct 13, 2005
Posts: 39079

23

posted

0

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

Joined: Oct 13, 2005
Posts: 39079

23

posted

0

Originally posted by Campbell Ritchie: Buy a bigger screen.

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

Joined: Jan 30, 2000
Posts: 18671

posted

0

Just for the heck of it though, here's one way to do it, without recursion:

"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

Joined: Oct 13, 2005
Posts: 39079

23

posted

0

Thank you, and welcome to the Ranch. It is nice to see something useful arising from such an old discussion.

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

There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors

Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 39079

23

posted

0

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

Joined: Apr 29, 2008
Posts: 2

posted

0

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.