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.– KeppilMay 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.– CarstenMay 14, 2013 at 19:51
-
3Go buy a supercomputer!– TdornoMay 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.– CarstenMay 14, 2013 at 19:58
-
3This seems to require a longer discussion. Can we please continue it in the chat?– CarstenMay 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.– MakotoMay 14, 2013 at 20:43