I have not done this, so I'm not sure. But there are some tricks.
You can first break up the computation to exploit repeated squaring.
Rather than n-1 multiplications, you can get away with log_2 n by
computing
n_1 = n^2
n_2 = n_1^2
n_3 = n_2^2
so that n_i = n^{2^i}
for i=1..N where n_N <= n and n_{N+1} > n
Let b_i be the i'th bit of n.
Then n^n = product_{ i | b_i = 1 } ( n_i )
Now as you say you can't afford to do the full multiply. So you'll
need two arbitrary precision multiplication algorithms keeping k
digits of precision each. The first is easy. Compute n^n as above
modulo 10^k (always throwing away higher order digits) to get the last
k digits.
The high order digits is the tricky part. I think the basic idea is
to implement floating point yourself. I.e. keep k+some extra digits
of mantissa plus an exponent to show where the decimal place is. The
problem is you always need to keep enough extra digits beyond k to be
sure rounding up won't affect to top k. There should be simple
algorithm to determine when you can stop.
Or you can take a chance and count on the fact that the probability of
carry out is limited for each digit, so with about 30 extra digits the
chances are pretty close to zero.
On Oct 3, 8:18 pm, g4ur4v <gauravyadav1...@gmail.com> wrote:
> can anyone please help me on how to approach this
> problem=>http://www.codechef.com/problems/MARCHA4
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
