On Feb 5, 8:14 pm, mukesh tiwari <mukeshtiwari.ii...@gmail.com> wrote: > 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.
By the way, given that your M is fairly tiny compared with A and N, a little bit of elementary number theory (e.g., Euler's theorem) could save you a lot of time here. For example, pow(a, n, 10**5) is equivalent to pow(a, 5 + (n - 5) % 40000, 10**5) for any n >= 5. Not sure if this is the kind of thing you're looking for. -- Mark -- http://mail.python.org/mailman/listinfo/python-list
