For performing exponentiation we can take the linear route or we can take the binary route. What is the main idea behind it
Suppose you are to calculate ( x^p) mod n
You can do this in a linear fashion and using the following property of modular operations
(a*b) mod n = (a mod n * b mod n) mod n
but that is O(n) time complexity and we can do better.
Observe the following
exponential(x,p) = exponential(x,p/2)<<2 // if p is even
x*exponential(x,(p-1)/2)<<2 // if p is odd
Now the number of times the functions is called is log2(b), which is a definite improvement over the linear case. But we can still do better by expressing the power in its binary form. Read the following wikipedia article for understanding
right to left binary method
following is C++ code for modular exponentiation .
Here is problem on SPOJ using the above concept http://www.spoj.com/problems/ZSUM/ .
Comments are welcome.
Suppose you are to calculate ( x^p) mod n
You can do this in a linear fashion and using the following property of modular operations
(a*b) mod n = (a mod n * b mod n) mod n
but that is O(n) time complexity and we can do better.
Observe the following
exponential(x,p) = exponential(x,p/2)<<2 // if p is even
x*exponential(x,(p-1)/2)<<2 // if p is odd
Now the number of times the functions is called is log2(b), which is a definite improvement over the linear case. But we can still do better by expressing the power in its binary form. Read the following wikipedia article for understanding
right to left binary method
following is C++ code for modular exponentiation .
Here is problem on SPOJ using the above concept http://www.spoj.com/problems/ZSUM/ .
Comments are welcome.
