I am trying to find an efficient way for calculating N^N in java. As the result will be very large for large N, I used BigInteger as my result data type and N is integer. If N becomes large say N=10000000 then it takes more time to calculate the result. Is there any efficient way that will calculate it within a second.
-
15I doubt it. That is a pretty big number.– KeppilCommented May 14, 2013 at 19:48
-
1Do you really need that number? The whole number? Because it's unlikely that you need a 70 million digit number (in decimal) every second. If you only need parts of it, say, the first few digits, there are ways to help you.– CarstenCommented May 14, 2013 at 19:51
-
3Go buy a supercomputer!– TdornoCommented May 14, 2013 at 19:54
-
1@zch Sure it's possible, and not too hard, but not trivial to do in under a second. I'm still on the "this is not really what the OP needs" train.– CarstenCommented May 14, 2013 at 19:58
-
3This seems to require a longer discussion. Can we please continue it in the chat?– CarstenCommented May 14, 2013 at 20:17
1 Answer
Handle the log of the number, which is N ln(N)
, in your program. As N
grows, the size of N ln(N)
relative to N^N
shrinks faster and faster.
The way you would implement this depends on what you need to do. If you don’t need your N^N
inside the program, then just forget about it and do it on paper once the program outputs. When you’re handling numbers that big, its log/order of magnitude/the number of digits it has (all of those are synonymous) is most of the essential information. If your program outputs x
, you would report that the answer is around e^x
, and that would be about all you could say.
If you do need N^N
inside your program, then you should still calculate x = ln(N^N) = N ln(N)
. But then you’re going to have to come up with some creative way of going from x
to some value that your program can actually use.
-
Pretty solid answer. Only taking what you care about, leaving the rest behind.– MakotoCommented May 14, 2013 at 20:43