Compute x to x power in the most optimal way possible

Question

Possible Duplicate:
The most efficient way to implement an integer based power function pow(int, int)

I know this question is pretty easy but my requirement is that I want to compute x to power x where x is a very large number in the best optimize way possible. I am not a math geek and therefore need some help to figure out the best way possible.

In java, we can use BigInteger but how to optimize the code? Any specific approach for the optimization?

Also using recursion will the large value of x, makes the code slow and prone to stack overflow error?

Eg: 457474575 raise to power 457474575

You can calculate all the powers of two up to x and multiply all the powers of two which add up to x. Even if you use recursion you wouldn't get more than log2(log2(x)) levels of recursion. — Peter Lawrey, Jun 09 '11 at 14:32
How do you intend to represent the answer? The calculation you give will have literally billions of digits. Do you need all of them? — David Thornley, Jun 09 '11 at 14:32
@learner, There will be 3,961,897,695 digits which you cannot have in a String. — Peter Lawrey, Jun 09 '11 at 14:34
Is x always an integer, or can it be a floating point number too? Do you need full precision on the answer, or only the order of magnitude? — Charles Brunet, Jun 09 '11 at 14:37
He asks for x^x not x^n - there is possibly a more efficient algorithm for that case. — Nordic Mainframe, Jun 09 '11 at 15:16

score 12 · Answer 1 · answered Jun 09 '11 at 14:34

12

You do realize that the answer to your example is going to be a very very large number, even for a BigInteger? It will have 3961897696 digits!

The best way to work with really large numbers, if you don't need exact precision, is to work with their logarithms instead. To take x to the x power, take the log of x and multiply it by x. If you need to convert it back take e to the x exp(x), except in this case it will almost certainly overflow.

answered Jun 09 '11 at 14:34

Mark Ransom

299,747
42
398
622

+1: You can't have a String in Java that long. ;) – Peter Lawrey Jun 09 '11 at 14:35
+1. I wrote basically the same answer (and deleted it again) – sellibitze Jun 09 '11 at 14:36
`pow(x,x)` -- giving new meaning to the term *arbitrary precision arithmetic*! – Ben Voigt Jun 09 '11 at 14:39
How do you guys compute the number of digits so precisely? – Martijn Courteaux Jun 09 '11 at 15:01
@Martijn Courteaux, the log10 representation of an integer, rounded up, is the number of digits. E.g. `log10(1234)` is 3.091, rounded up makes 4. – Mark Ransom Jun 09 '11 at 15:42

score 1 · Answer 2 · answered Jun 09 '11 at 14:33

1

This is one of the simplest optimized approaches:

x^1*x^1=x^2
x^2*x^2=x^4
etc...
x^x = x^(x/2)*x^(x/2)*remainder

answered Jun 09 '11 at 14:33

Šimon Tóth

35,456
20
106
151

score 1 · Answer 3 · answered Jun 09 '11 at 14:42

1

((BigInteger) 457474575).pow(457474575);

answered Jun 09 '11 at 14:42

toto2

5,306
21
24

+1: You cannot cast to a BigInteger and you can only do powers up to Integer.MAX_VALUE, but I like your thinking. – Peter Lawrey Jun 09 '11 at 14:45

Compute x to x power in the most optimal way possible

3 Answers3