On Feb 5, 2:18 pm, Mark Dickinson <dicki...@gmail.com> wrote: > On Feb 5, 8:14 pm, mukesh tiwari <mukeshtiwari.ii...@gmail.com> 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. > > > 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 > > The built-in pow function does exactly this,
It doesn't do 'exactly' that. M is the number of digits. If you want 17 digits, the third number should 10**17. Using 17 directly will give you a 2-digit answer as shown. Try this instead: >>> pow(12345,67891,10**17) 50553131103515625 > if you give it three > arguments: > > >>> pow(12345, 67891, 17) > 10 > >>> 12345 ** 67891 % 17 > > 10L > > (Though this won't work for negative N.) > > Mark -- http://mail.python.org/mailman/listinfo/python-list