we have to find X^N let it would be N YlogX=log(N) antiLog(YlogX)=N antilog for base 10 is power of 10 so 10^(YlogX)=N and if we want to find 3^5 pow(10,5log3)---> pow(10,2.3856062735)=243 and if u want to find first 2 digits pow(10,(2.3856062735-1))=24.3=24
On Tue, Oct 4, 2011 at 1:46 AM, sunny agrawal <[email protected]>wrote: > For Last K Gene has posted the right Approach. > For First K > Hint : Logarithms log(N^N) = NlgN > > On Tue, Oct 4, 2011 at 1:14 AM, Gene <[email protected]> wrote: > >> 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 <[email protected]> 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 [email protected]. >> To unsubscribe from this group, send email to >> [email protected]. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> >> > > > -- > Sunny Aggrawal > B.Tech. V year,CSI > Indian Institute Of Technology,Roorkee > > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- AMRIT -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
