Invisible wrote:

> The difficulty, then, is coming up with an algorithm to compute the 
> least-significant digits of λ n → n 2^n without computing the entire 
> number. I'll have to go check my number theory; I don't recall the exact 
> details of the algorithm.

You're asking for the last 10 digits of the answer. In other words, the 
answer modulo 10^10. (Assuming you meant the last 10 *decimal* digits...)

In modular arithmetic,

   (X mod M) * (Y mod M) = (X * Y) mod M

In other words, we can reduce our running total to the least positive 
reside class mod 10^10 and still get the same answer. Handling 
billion-digit numbers is quite expensive, but piffling 10-digit numbers 
are no match for the GMP.

Unfortimately,

   (X mod M)^(Y mod M) ≠ (X^Y) mod M

But fortunately,

   (X mod M)^Y = (X^Y) mod M

due to the first theorum. Better still,

   A+B = Y ⇒ (X mod M)^A * (X mod M)^B = (X^Y) mod M

by the usual first law of logarithms. This gives us the binary 
exponentiation algorithm:

   x = 1;
   b = base;
   e = exponent;
   while (e>0)
     if odd(e) then x = x*b mod m;
     e = shift_right(e);
     b = b*b mod m;

At any time, you need to deal with numbers containing at most 20 digits.

So what's the answer? I make it

.....1,549,498,368

It took about 0.2 seconds to compute. I have very little confidence that 
this is correct though.

Post a reply to this message