If we want to know the last ten digits of number *a ^{n}* – we have to evaluate expression

*a*. Using brute force approach, we have to do

^{n}mod 10^{10}*O(n)*( If you don’t understand big „O” notation, visit: Big O notation – it’s VERY important) multiplications and modulo divisions. When

*n*is greater than

*10*, it will take a lot of time. Fortunately, we can use more „mathematical” approach, which has

^{9}*O(log n)*complexity.

Firstly, we have to notice, that:

(1) a

^{2c}mod r = (a

^{c})

^{2}mod r

(2) a

^{2c+1}mod r = a*(a

^{c})

^{2}mod r

#! /usr/bin/env python # Author: Wojtek Jamrozy (www.wojtekrj.net) def modexp(a, n, m): bits = [] while n: bits.append(n%2) n /= 2 solution = 1 bits.reverse() for x in bits: solution = (solution*solution)%m if x: solution = (solution*a)%m return solution print modexp(2,34, pow(10,10)) print modexp(2,pow(10,20), pow(10,10)) |

output:

7179869184 1787109376 |

Function *pow(a,b)* is Python’s function, which computes *a ^{b}*

Function

*modexp(a, n, m)*computes

*a*. Here is example, which shows running of the function a=2, n=34, m=10

^{n}mod m^{10}

Firstly, we want to have bits of binary notation of

*n*in list

*bits*.

Before reversion,

*bits*have following content: [0, 1, 0, 0, 0, 1] (2

^{1}+ 2

^{5}= 33)

After reversion of list:

*bits*= [1, 0, 0, 0, 1, 0]

Bits of binary notation of

*n*are in order from “bigger” powers to “lower” ones.

I will use (b) for binary notation of number: 33 = 100001(b)

At the beggining,

*solution*= 2

^{0}mod 10

^{10}= 1. Then, during execution of

*for*loop,

*solution*has following values: 2

^{1(b)}mod 10

^{10}, 2

^{10(b)}mod 10

^{10}, 2

^{100(b)}mod 10

^{10}, 2

^{1000(b)}mod 10

^{10}, 2

^{10001(b)}mod 10

^{10}and finally 2

^{100010(b)}mod 10

^{10}.

Using (1) and (2) we can calcualte every

*solution’s*value if we know previous one.

Loop

*for*is executed for each element of

*bits*.

*Bits*size is

*log*, so the complexity of whole alghorithm is

_{2}n*O(log n)*

You can download code here:

**expon.py** (369 bytes, 879 hits)

Hi there,

Not enought information

Thank you

Eremeeff

Greatings,

Super post, Need to mark it on Digg

Thank you

AnnaHopn

Hello,

Super post, Need to mark it on Digg

Thank you

Elcoj