If we want to know the last ten digits of number an – we have to evaluate expression an mod 1010. Using brute force approach, we have to do 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 109, it will take a lot of time. Fortunately, we can use more „mathematical” approach, which has O(log n) complexity.
Firstly, we have to notice, that:
(1) a2c mod r = (ac)2 mod r
(2) a2c+1 mod r = a*(ac)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))
Function pow(a,b) is Python’s function, which computes ab
Function modexp(a, n, m) computes an mod m. Here is example, which shows running of the function a=2, n=34, m=1010
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] (21 + 25 = 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 = 20 mod 1010 = 1. Then, during execution of for loop, solution has following values: 21(b) mod 1010, 210(b) mod 1010, 2100(b) mod 1010, 21000(b) mod 1010, 210001(b) mod 1010 and finally 2100010(b) mod 1010.
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 log2n, so the complexity of whole alghorithm is O(log n)
You can download code here:
expon.py (369 bytes, 879 hits)