Last M digits of expression A^N
Dave Angel
davea at ieee.org
Sat Feb 6 17:59:44 EST 2010
monkeys paw wrote:
> <div class="moz-text-flowed" style="font-family: -moz-fixed">mukesh
> tiwari wrote:
>> Hello everyone. I am kind of new to python so pardon me if i sound
>> stupid.
>> I have to find out the last M digits of expression.One thing i can do
>> is (A**N)%M but my A and N are too large (10^100) and M is less than
>> 10^5. The other approach was repeated squaring and taking mod of
>> expression. Is there any other way to do this in python more faster
>> than log N.
>
> How do you arrive at log N as the performance number?
>
>>
>> def power(A,N,M):
>> ret=1
>> while(N):
>> if(N%2!=0):ret=(ret*A)%M
>> A=(A*A)%M
>> N=N//2
>> return ret
>
Because the N= N/2 operation in the loop means that the number of loops
is equal to the number of bits in N, or the log-base-2 of N.
DaveA
More information about the Python-list
mailing list