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 <sunny816.i...@gmail.com>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 <gene.ress...@gmail.com> 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 <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.
>>
>>
>
>
> --
> 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 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.
>
--
AMRIT
--
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.
