3

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.

24
  • 15
    I doubt it. That is a pretty big number.
    – Keppil
    Commented May 14, 2013 at 19:48
  • 1
    Do 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.
    – Carsten
    Commented May 14, 2013 at 19:51
  • 3
    Go buy a supercomputer!
    – Tdorno
    Commented 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.
    – Carsten
    Commented May 14, 2013 at 19:58
  • 3
    This seems to require a longer discussion. Can we please continue it in the chat?
    – Carsten
    Commented May 14, 2013 at 20:17

1 Answer 1

8

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.

1
  • Pretty solid answer. Only taking what you care about, leaving the rest behind.
    – Makoto
    Commented May 14, 2013 at 20:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.