You are not logged in. Please login at www.codechef.com to post your questions!

×

# A tutorial on Fast Modulo Multiplication (Exponential Squaring)

 46 39 Hello @all, This tutorial will cover the topic of Fast Modulo Multiplication (also known as Exponential Squaring or Repeated Squaring). This is a very useful technique to have under your arsenal as a competitive programmer, especially because such technique often appears on Maths related problems and, sometimes, it might be the difference between having AC veredict or TLE veredict, so, for someone who still doesn't know about it, I hope this tutorial will help :) Main reason why the usage of repeated squaring is useful This technique might seem a bit too complicated at a first glance for a newbie, after all, say, we want to compute the number 310. We can simply write the following code and do a simple for loop: #include using namespace std; int main() { int base = 3; int exp = 10; int ans = 1; for(int i = 1; i <= exp; i++) { ans *= base; } cout << ans; return 0; }  The above code will correctly compute the desired number, 59049. However, after we analyze it carefully, we will obtain an insight which will be the key to develop a faster method. Apart from being correct, the main issue with the above method is the number of multiplications that are being executed. We see that this method executes exactly exp-1 multiplications to compute the number nexp, which is not desirable when the value of exp is very large. Usually, on contest problems, the idea of computing large powers of a number appears coupled with the existence of a modulus value, i.e., as the values being computed can get very large, very fast, the value we are looking to compute is usually something of the form: nexp % M , where M is usually a large prime number (typically, 109 + 7). Note that we could still use the modulus in our naive way of computing a large power: we simply use modulus on all the intermediate steps and take modulus at the end, to ensure every calculation is kept within the limit of "safe" data-types. The fast-exponentiation method: an implementation in C++ It is possible to find several formulas and several ways of performing fast exponentiation by searching over the internet, but, there's nothing like implementing them on our own to get a better feel about what we are doing :) I will describe here the most naive method of performing repeated squaring. As found on Wikipedia, the main formula is: A brief analysis of this formula (an intuitive analysis if you prefer), based both on its recursive formulation and on its implementation allows us to see that the formula uses only O(log2n) squarings and O(log2n) multiplications! This is a major improvement over the most naive method described in the beginning of this text, where we used much more multiplication operations. Below, I provide a code which computes baseexp % 1000000007, based on wikipedia formula: long long int fast_exp(int base, int exp) { if(exp==1) return base; else { if(exp%2 == 0) { long long int base1 = pow(fast_exp(base, exp/2),2); if(base1 >= 1000000007) return base1%1000000007; else return base1; } else { long long int ans = (base* pow(fast_exp(base,(exp-1)/2),2)); if(ans >= 1000000007) return ans%1000000007; else return ans; } } }  The 2k-ary method for repeated squaring Besides the recursive method detailed above, we can use yet another insight which allows us to compute the value of the desired power. The main idea is that we can expand the exponent in base 2 (or more generally, in base 2k, with k >= 1) and use this expansion to achieve the same result as above, but, this time, using less memory. Below you can find the code provided in the comment by @michal27: ll fast_exp(int base, int exp) { ll res=1; while(exp>0) { if(exp%2==1) res=(res*base)%MOD; base=(base*base)%MOD; exp/=2; } return res%MOD; }  These are the two most common ways of performing repeated squaring on a live contest and I hope you have enjoyed this text and have found it useful :) Useful problems to practice this new concept: Further analysis and generalizations Besides the simple method explained here, applied only to the computation of large powers of a given number, it turns out that this method is widely used in the fast computation of powers of matrices and, as we shall see on a later tutorial (hopefully, not so later ;) ) this is where this method actually excels and provides really good methods for tackling hard problems :) Best regards, Bruno asked 12 Aug '13, 19:59 2★kuruma 17.5k●72●143●208 accept rate: 8% 1 very well explained bro...it makes a 10/10 tutorial...:) (12 Aug '13, 23:01) kunal3614★ 1 I'm really glad you liked it :D (12 Aug '13, 23:13) kuruma2★ actually this tutorial is awesome....I m stucked how can any1 explain so simple...I want to learn programming , algorithm in your guidence please provide me some source to read your blog, tutorial any material produced by you or any1 like you.... thanks for appreaciation... (04 Jul '15, 03:30)

15 Answers:
 20 I want to add solution I often use on competition and I think is easier to implement and also has only O(1) memory complexity. Your program has O(log n) memory complexity because of recursion. Here I use the fact that I can divide exp to sum of powers of two. So the base^exp can be expressed as multiple of base^poweroftwo. So I just in one while cycle decompose exp as binary number and in base I create appropriate power of base (just square of previous base). In the code, ll stands for long long int. And MOD is choosed modulo. ll fast_exp(int base, int exp) { ll res=1; while(exp>0) { if(exp%2==1) res=(res*base)%MOD; base=(base*base)%MOD; exp/=2; } return res; }  answered 12 Aug '13, 20:51 5★michal27 1.1k●2●10●17 accept rate: 13% Thanks added this to the tutorial :D (12 Aug '13, 22:14) kuruma2★ can somebody explain this solution (11 Dec '16, 16:05)
 1 Very nice @Kuruma ,also key to problem CHMOD asked in recent August 2013 long challenge,thanks for the tutorial :) answered 12 Aug '13, 20:15 1★faiz 85●3 accept rate: 0% good post i like it (12 Aug '13, 23:59) I am really glad to hear it, @driftking (13 Aug '13, 00:06) kuruma2★
 1 I got AC in kisses and hugs only after converting base into long long int maybe the statement  base=(base*base)%MOD;  was the cause of overflow. answered 30 Mar '14, 02:04 4★grv95 9●1●2 accept rate: 0%
 0 return should be res%MOD; otherwise ( x ^0 )%1 will return 1 answered 12 Aug '13, 23:30 1 accept rate: 0% 1 you are right, fixed it (12 Aug '13, 23:35) kuruma2★ in majority, you don't use 1 as modulo but yes, you are right :) (12 Aug '13, 23:55) michal275★
 0 This may give wrong results (for example, for 999,999,999 and 1000,000,000) because of pow() function which uses double. Instead of pow(), for squaring, if we simply multiply the numbers, we will get correct result i.e. 570312504, 140625001. link text answered 30 Jul '14, 15:28 82●2●4●7 accept rate: 25%
 0 when it comes to modulo of 10^9 it gives some bogus solution 504271345 instead of 4 . https://www.hackerrank.com/challenges/k-candy-store/submissions/code/10592914 answered 20 Dec '14, 22:00 0★ism_syed 1 accept rate: 0% It's not visible, can you share it somewhere else? Probably there is overflow in your code... (20 Dec '14, 23:09) Hey,i am not getting how your recursion takes %(100000007) at every recursive step to avoid overflow..Can you explain this little bit.I mean to say how recursion work here?Does it calculate a^b and then calculate %(100000007) or it calculates ((a1%(100000007)*(a2%100000007)...)%(100000007).If the answer is latter can you please explain how (06 Mar '15, 01:05) doodle902★
 0 I have small doubt regarding fast_exp(int base, int exp) function. I think it may return wrong answer in case exp is 1. As for that case the modulo operation is not happening. Can anyone explain? answered 02 Jan '16, 22:50 1 accept rate: 0%
 0 Hey Guys, just a small note who may be having problems using the above functions. For large values of base and exp you should prefer long long int as data types of base and exponent in fn. Also, second recursive function is better. IF you use int data types you may run into run time error, overflow. answered 03 Apr '16, 16:03 5★kush2327 11●2 accept rate: 0%
 0 Great tutorial .... Just a heads-up ... the first method caused a RunTime error (SIGSEGV) . I think that it was caused because of the fact that it is a recursive approach and that it takes up too much of memory . The second method is much better .... but you should initialize both the exp and base as long long int answered 10 Apr '16, 16:42 3★codwotin 1 accept rate: 0%
 0 You can make it even faster by using bitwise operators to check for parity (n&1 instead of n%2==1) and to divide by two (n=n>>1 instead of n=n/2). :) answered 11 Apr '16, 22:20 282●6 accept rate: 11%
 0 This is truly a great psot thanks for sharing. Excellent and decent post. I found this much informative, as to what I was exactly searching for. Thanks for such post and please keep it up. answered 12 Apr '16, 11:43 0★jameslee 1 accept rate: 0%
 0 https://www.youtube.com/watch?v=wAyrtLAeWvI&list=PL2_aWCzGMAwLz3g66WrxFGSXvSsvyfzCO&index=7 great explanation by mycodeschool... answered 11 Jul '16, 10:58 2★vivek96 518●2●11 accept rate: 7%
 0 @kuruma One thing I would like to add .. your code fails when the exp = 0 , Output should be 1 but your code doesn't produce any output . Adding and if statement will do the job . :) answered 28 Jul '17, 02:14 563●1●4 accept rate: 8%
 0 thanks @kurma that's really helpfull answered 22 Nov '17, 01:45 10●1 accept rate: 0%
 0 in the wikipedia solution can't we directly return base1%1000000007 answered 04 Dec '17, 22:53 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• link:[text](http://url.com/ "title")
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×983
×604
×108

question asked: 12 Aug '13, 19:59

question was seen: 60,965 times

last updated: 04 Dec '17, 22:53