A tutorial on Fast Modulo Multiplication (Exponential Squaring)

exponentiation
maths
tutorial

#1

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 :slight_smile:

  • 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 <iostream>
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 :slight_smile:

I will describe here the most naive method of performing repeated squaring. As found on Wikipedia, the main formula is:

alt text

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 :slight_smile:

  • Useful problems to practice this new concept:

Kisses & Hugs;

Chef and segments;

  • 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 :wink: ) this is where this method actually excels and provides really good methods for tackling hard problems :slight_smile:

Best regards,

Bruno


#2

Very nice @Kuruma ,also key to problem CHMOD asked in recent August 2013 long challenge,thanks for the tutorial :slight_smile:


#3

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;
}

#4

return should be res%MOD; otherwise ( x ^0 )%1 will return 1


#5

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.


#6

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


#7

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


#8

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?


#9

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.


#10

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


#11

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). :slight_smile:


#12

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.


#13

https://www.youtube.com/watch?v=wAyrtLAeWvI&list=PL2_aWCzGMAwLz3g66WrxFGSXvSsvyfzCO&index=7 great explanation by mycodeschool...


#14

@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 . :slight_smile:


#15

thanks @kurma that’s really helpfull


#16

in the wikipedia solution can’t we directly return base1%1000000007


#17

Hey, I don’t clearly understand the implementation. As per the formula above for the fast-exponentiation method given on wikipedia, why don’t we write it’s implementation as given below.

long long fast_exp_1(long long x, int n)
{
	if(n==1)
		return x;
	if(!(n&1))
		return fast_exp_1(pow(x,2),n/2) % MOD;
	else
		return (x*fast_exp_1(pow(x,2),(n-1)/2)) % MOD;
}

Your help is really appreciated. Thanks in advance :slight_smile:


#18

Thanks added this to the tutorial :smiley:


#19

very well explained bro…it makes a 10/10 tutorial…:slight_smile:


#20

I’m really glad you liked it :smiley: