Last M digits of expression A^N
mukesh tiwari
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
Mark Dickinson
The built-in pow function does exactly this, if you give it three
arguments:
>>> pow(12345, 67891, 17)
10
>>> 12345 ** 67891 % 17
10L
(Though this won't work for negative N.)
Mark
Gerald Britton
Mensanator
> 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
monkeys paw
> 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?
Dave Angel
> <div class="moz-text-flowed" style="font-family: -moz-fixed">mukesh
is equal to the number of bits in N, or the log-base-2 of N.
DaveA
Mark Dickinson
> 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