Modular Exponentiation Algorithm

In this post I will be discussing a method to find (ab)%MOD. The problem is simple, we have been doing it from long time to find ab. But as b increases, we may think of writing a code for it. Say a simple method like this:

long long int modPow(long long int m, long long int n, long long int mod)
{
    long long int p = 1;
    for(int i = 0;i < n;i++) 
    { 
        p *= m; 
        p %= mod; 
    } 
    return mod; 
}  

Above mentioned function solves the need. But is not efficient. Complexity of the function is O(n) and hence cannot find required answer for large values of b or n(for n values > 108) in reasonable time. This can be optimised using Modular Exponentiation Algorithm. This algo solves the problem in O(log n) complexity. Here is the function:

 
long long int fastModPow(long long int a, long long int b, long long int mod) 
{ 
    long long int ans = 1; 
    while(b > 0)
    {
        if(b%2 == 1)
            ans = (ans*a)%mod;
        a = (a*a)%mod;
        b /= 2;
    }
    return ans;
}

How this function works?
Let us solve for 550. Leave the modulus as it is just an additional operation that is done commonly at each step.

bin(50) = 110010

Initial values    : ans = 1                      a = 5                      b = 50
Step 1            : ans = 1                      a = 5*5                      b = 25
Step 2            : ans = 1 * 52               a = 52 * 52               b = 12
Step 3            : ans = 52                      a = 54 * 54             b = 6
Step 4            : ans = 52                      a = 58 * 58              b = 3
Step 5            : ans = 52 * 516            a = 516 * 516            b = 1
Step 6            : ans = 518 * 532          a = 532 * 532            b = 0

We are left with ans = 550 which is the desired result. As we move from LSB to MSB in binary form of exponent, compare the respective steps shown above. The calculations followed are different for the bit values 1 and 0.

Advertisements

Multiplying large numbers in C/C++

Working with large numbers in C/C++ is always a problem. Those who have knowledge in Java/python tend to code in these languages for those particular problems. (Java has a BigInteger class where in there is no limit for integer range you work on. Python doesn’t have any limits on integers.) For those who wanted to handle large numbers in C/C++, lets discuss an approach for how to multiply large numbers.

We use arrays to store the numbers.
Why? Because we do not have any data type which could store big integers say around 10^3 digits.
How? Each digit of integer is stored in each index in the array. Lets store them in reverse order for simpler calculations.

Now we have two integers(A,B) in array each of length L1,L2 respectively. Product of these two numbers will be at most L1+L2. So lets take an empty Ans[] array of size 2*N.

Procedure :

Step 1 : Multiply index i of B with all the indexes j of A. Add the product to value in Ans[k] where 0 <= i < L2, 0 <= j < L1, k = i+j.
Step 2 : Repeat step 1 till i = L2. (Picture how you multiply two large numbers on a paper).
Step 3 :
for each i in range(0,L1+L2)
TMP = X/10. X = X%10. Y = Y+TMP.
X = A[i]
Y = A[i+1]
TMP = temporary variable.
Step 4 : reverse the array Ans, and that will be the final product.

Code:

#include <stdio.h>
#include <string.h>

int main()
{
    int a[100],b[100];
    int ans[200]={0};
    int i,j,tmp;
    char s1[101],s2[101];
    scanf(" %s",s1);
    scanf(" %s",s2);
    int l1 = strlen(s1);
    int l2 = strlen(s2);
    for(i = l1-1,j=0;i>=0;i--,j++)
    {
        a[j] = s1[i]-'0';
    }
    for(i = l2-1,j=0;i>=0;i--,j++)
    {
        b[j] = s2[i]-'0';
    }
    for(i = 0;i < l2;i++)
    {
        for(j = 0;j < l1;j++)
        {
            ans[i+j] += b[i]*a[j];
        }
    }
    for(i = 0;i < l1+l2;i++)
    {
        tmp = ans[i]/10;
        ans[i] = ans[i]%10;
        ans[i+1] = ans[i+1] + tmp;
    }
    for(i = l1+l2; i>= 0;i--)
    {
        if(ans[i] > 0)
            break;
    }
    printf("Product : ");
    for(;i >= 0;i--)
    {
        printf("%d",ans[i]);
    }
    return 0;
}

Input :
150353265326
22055653351

Output:
Product : 3316139500221184007426

Related problems : Small Factorials(FCTRL2)
My Solution for Small Factorials

Maximum Subarray Sum algorithm

This algorithm is used to find the maximum sum of a contiguous sub array in a given array of integers. If the set of integers include only positive integers, maximum sum would be sum of all the elements of array. But when the array include negative integers too, the problem comes of how to solve it efficiently.

A naive approach would be finding sum of elements of all sub arrays.

MaxSubarraySumNaive(a[])
    max = 0
    for i = 1 to n
        for j = i to n
            temp = 0
            for k = i to j
                temp = temp + a[i]
            if temp > max
                max = temp
    return max

That’s an O(n3) solution which is not at all appreciable. So let’s learn this algo which could solve this problem with an O(n) complexity.

MaxSubarraySum(a[])
    max_sum = 0
    temp = 0
    for i = 1 to n
        temp = max( 0 , temp+a[i] )
        max_sum = max( max_sum , temp )
    return max_sum

This short function solves the problem in real quick time. Working of the function with an example is shown below

For increasing i,
Array elements  : 1 -2 8 -1  6  3 -12  4 -16  5 10
temp values     : 1  0 8  7 13 16   4  8   0  5 15
max_sum values  : 1  1 8  8 13 16  16 16  16 16 16

Methods to check if a number is prime or not

One of the most common problem a competetive programmer solves is regarding prime numbers. A beginner, in general starts solving such problem by following the definition of prime numbers i.e. a prime number is that which is not divisible by any number other than 1 and itself.
So, following this, the pseudocode will be in this way..

n <- input
i <- 2
while i < n
    if n%i = 0
        "NOT A PRIME"
    i <- i+1
if i = n
    "PRIME"

It has an O(n) complexity. But the competetive programming never would ask a question that allows one to get their code accepted in time limit with such an approach. They would demand a much better approach.

A better approach would let us know the concept that ‘a number is not prime if it has a factor that is less than or equal to square root of n’. With this pseudocode can be..

while i*i <= n   //(loop will be iterated till 'i' is atmost square root of n)
    if n%i = 0
        "NOT A PRIME"
    i <- i+1
if i*i > n
    "PRIME"

This code has a complexity of O(sqrt(n)).

Now just think you need to check a if number of order 10^8 is prime or not, previous approach would take 10^8 iterations in solving. Whereas later takes just around 10^4 iterations in solving your problem.

Last Digit of exponent(a^b).

This is an editorial for the problem LASTDIG on SPOJ.

The problem asks us to find the last digit of the exponent a^b. It has many different ways to get solution.

Lets discuss three different approaches in solving this problem:

  • 1) Keep on multiplying the number ‘a’ for ‘b’ times and keep tracking the last digit that is to output in the end. Keeping track of last digit here implies, for larger values of ‘a’ and ‘b’, the product could cross the range of int or long.It takes a O(n) complexity. This could take a long time and might result in TLE(Time Limit Exceeded) as the limits in general to such a problem will be given to test for a faster approach that are discussed in other methods discussed below.
  • 2) Another approach to this problem could be this, with worst possible complexity being O(log n). For this we can keep squaring the number ‘a’ till the power(p) it raised to is the closest to ‘b’ and for the remaining (b-p) times, a is to be multiplied and and the last digit is finally printed out. A algorithm for this approach is
    long long int Fast_pow(long long int b, long long int e){
        long long int ans = 1;
        while (e > 0){
            if (e % 2 == 1)
                ans = (ans * b);
            e = e >> 1;
            b = (b * b);
        }
        return ans;
    }
    

    prod%10 is the answer.
    This method runs a lot faster than previous version. But the problem you start realising is for larger values of a and b, we are not allowed to store such big resultant product values in few languages. We can at most store a 64 bit value if we are using C/C++.

  • 3)In this method let us first know few facts that arises in calculating the last digit of a^b. On observing different exponents, we can say these few cases:
    – If last digit of a is ‘0’ or ‘1’ or ‘5’ or ‘6’, then always in powers of those numbers for any case of ‘b'(except b=0), last digit will be same.
    – If last digit of ‘a’ is 2, the sequence {6,2,4,8} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 3, the sequence {1,3,9,7} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 4, the sequence {6,4} follows for mod(2) of ‘b’.
    – If last digit of ‘a’ is 7, the sequence {1,7,9,3} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 8, the sequence {6,8,4,2} follows for mod(4) of ‘b’.
    – If last digit of ‘a’ is 9, the sequence {1,9} follows for mod(2) of ‘b’.
    Note: for b=0, answer should be 1 in any case of ‘a’. So here we can make a switch case program or if-else program to get the answer. This approach has a O(1) complexity.

    Related Problems : Arithmancy Challenge (HackerEarth), Last Digit (SPOJ). In the problem that is asked in SPOJ, you cannot use switch case as it exceeds size limit(700 bytes). In that case try solving it by using a 2D array. It cuts down the size of the code and thus could get an accepted submission. 🙂

Booth’s Algorithm for multiplication of signed binary numbers.

Booth’s Multiplication Algorithm is used to multiplication of two signed binary numbers. This algorithm was invented by Andrew Donald Booth in 1950. All it includes are addition of binary numbers and right shift operation.

Let us discuss a C program that calculates and displays multiplication of two signed binary numbers using Booth’s Algorithm in tabular form.

In the discussion let us first know Booth’s Algorithm.

For a given two numbers ‘q’ and ‘m’. Convert them to binary ‘Q’ and ‘M’. Also find 2’s compliment of ‘M’ as we need to use the value of -M.(Note that in signed binary -M is 2’s compliment of M).

Draw a table with 4 columns. First step no., second P(the value in accumulator), third multiplicand(Q), and fourth is previous state(Q-1).

Booth’s Algorithm has ‘N’ number of steps where ‘N’ is size of binary numbers that are being multiplied.(Remember that we need to take them in same size. If they are not same, make them zero by adding leading zeros or ones according to the number).

Set step no. to 0. Set P initially to zero. Fill in the Q register value equal to multiplicand. And Q-1 column as zero.

Now follow the following steps on comparing values of LSB of Q an Q-1.

Q – Q-1         Action
0 – 0        Right Shift.
0 – 1        Add M to P and Right Shift.
1 – 0        Add -M to P and Right Shift.
1 – 1        Right Shift.

The final product is combination of P-Q in signed binary number.

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

void rightShift();

int main()
{
    printf("\n");
    printf(" BOOTH's Algorithm\n"); //Printing out Booth's Algorithm for multiplication of signed binary numbers
    printf("0-0 Right Shift.\n");
    printf("0-1 Add M to P. Right Shift.\n");
    printf("1-0 Add -M to P. Right Shift.\n");
    printf("1-1 Right Shift.\n");
    printf("\n");
    printf("Enter two numbers that are to be multiplied : ");//taking two numbers as inputs
    int a,b;
    scanf("%d %d",&a,&b);
    int ap=a,bp=b;
    if(ap<0) //checking if any of the inputs are -ve
        ap*=-1;
    if(bp<0) bp*=-1; if(bp>ap) //taking greater VALUE as multiplicand
    {
        ap=bp+ap-(bp=ap);
        a=b+a-(b=a);
    }
    int t1=ap,t2=bp;
    int ab[35]={};
    int bb[35]={};
    int i=0;
    while(t1>0)
    {
        ab[i]=t1%2;
        i++;
        t1/=2;
    }
    ab[i]=0;
    int j=0;
    while(t2>0)
    {
        bb[j]=t2%2;
        j++;
        t2/=2;
    }
    while(j<=i) //equating bits to previous(ab) binary number(ab will either be larger or equal to bb).
        bb[j++]=0;
    int nb=i+1; //nb is number of bits
    i=0;j=0;
    while(i<nb/2) //converting VALUES to binary
    {
        ab[i]=ab[nb-i-1]+ab[i]-(ab[nb-i-1]=ab[i]);
        i++;
    }
    i=0;
    while(i<nb/2) { bb[i]=bb[nb-i-1]+bb[i]-(bb[nb-i-1]=bb[i]); i++; } int x[35]={0}; int y[35]={0}; i=0; if(a>=0) //taking actual binary numbers
    { //x is multiplicand and y is multiplier
        while(i<nb)
        x[i]=ab[i+++1];
    }
    else //2's complimant conversion
    {
        while(i<nb) { if(ab[i]==0) x[i]=1; else x[i]=0; i++; } i=1; x[nb-i]++; while(x[nb-i]==2) { x[nb-i]=0; i++; x[nb-i]++; } } i=0; if(b>=0)
    {
        while(i<nb)
            y[i]=bb[i+++1];
    }
    else //2's complimant conversion
    {
        while(i<nb) { if(bb[i]==0) y[i]=1; else y[i]=0; i++; } i=1; y[nb-i]++; while(y[nb-i]==2) { y[nb-i]=0; i++; y[nb-i]++; } } printf("\n"); //output starts here printf("Multiplicand (Q) %d -> ",a);
    i=0;
    while(i<nb) printf("%d",x[i++]); printf(" and Multiplier (M) %d -> ",b);
    i=0;
    while(i<nb)
        printf("%d",y[i++]);
    printf("\n");
    i=0;
    int ym[35]={0}; //calculating -ve of multiplier. we use that in Booth's algorithm. ym=-y .
    if(b<0)
    {
        while(i<nb)
        ym[i]=bb[i+++1];
    }
    else
    {
        while(i<nb) { if(bb[i]==0) ym[i]=1; else ym[i]=0; i++; } i=1; ym[nb-i]++; while(ym[nb-i]==2) { ym[nb-i]=0; i++; ym[nb-i]++; } } printf("we use -(M) i.e. %d -> ",-b);
    i=0;
    while(i<nb)
        printf("%d",ym[i++]);
    printf("\n");
    int q0=0;
    int p[35]={0}; //p here is value that is stored in accumulator. initially set to zero.
    int steps=nb;
    printf("\n");
    printf("Step No. "); //title of columns.
    i=0;
    while(i<nb)
    {
        if(i*2==nb || i*2==nb-1)
        printf("P");
        else
        printf(" ");
        i++;
    }
    printf(" ");
    i=0;
    while(i<nb)
    {
        if(i*2==nb || i*2==nb-1)
            printf("Q");
        else
            printf(" ");
        i++;
    }
    printf(" Q-1");
    printf("\n");
    j=0;

    while(steps--) //counting down steps.
    { // Booth's algorithm has steps that is equal to no. of bits in multiplier or multiplicand
        printf("%d         ",j++);
        i=0;
        while(i<nb)
            printf("%d",p[i++]);
        printf(" ");
        i=0;
        while(i<nb)
            printf("%d",x[i++]);
        printf(" ");
        printf("%d\n",q0);
        if(x[nb-1]==0 && q0==0) //0-0 condition
        {
            q0=x[nb-1];
            rightShift(p,x,nb);
        }
        else if(x[nb-1]==0 && q0==1) //0-1 condition
        {
            printf("        + ");
            i=0;
            while(i<nb)
                printf("%d",y[i++]);
            i=0;
            while(i<nb)
            {
                p[nb-i-1]+=y[nb-i-1];
                if(p[nb-i-1]==2)
                {
                    p[nb-i-1]=0;
                    if(nb-i-1!=0)
                    p[nb-i-2]++;
                }
                if(p[nb-i-1]==3)
                {
                    p[nb-i-1]=1;
                    if(nb-i-1!=0)
                    p[nb-i-2]++;
                }
                i++;
            }
            printf("\n          ");
            i=0;
            while(i<nb)
                printf("%d",p[i++]);
            printf("\n");
            q0=x[nb-1];
            rightShift(p,x,nb);
        }
        else if(x[nb-1]==1 && q0==0) //1-0 condition
        {
            printf("        + ");
            i=0;
            while(i<nb)
                printf("%d",ym[i++]);
            i=0;
            while(i<nb)
            {
                p[nb-i-1]+=ym[nb-i-1];
                if(p[nb-i-1]==2)
                {
                    p[nb-i-1]=0;
                    if(nb-i-1!=0)
                    p[nb-i-2]++;
                }
                if(p[nb-i-1]==3)
                {
                    p[nb-i-1]=1;
                    if(nb-i-1!=0)
                    p[nb-i-2]++;
                }
                i++;
            }
            printf("\n          ");
            i=0;
            while(i<nb)
                printf("%d",p[i++]);
            printf("\n");
            q0=x[nb-1];
            rightShift(p,x,nb);
        }
        else if(x[nb-1]==1 && q0==1) //1-1 condition
        {
            q0=x[nb-1];
            rightShift(p,x,nb);
        }
    }
    printf("%d         ",j);
    i=0;
    while(i<nb)
        printf("%d",p[i++]);
    printf(" ");
    i=0;
    while(i<nb)
        printf("%d",x[i++]);
    printf(" ");
    printf("%d\n",q0);
    printf("\n");

    printf("Product in signed binary number is : "); //printing out the product. it will be in signed binary representation
    i=0;
    while(i<nb)
        printf("%d",p[i++]);
    i=0;
    printf(" ");
    while(i<nb)
        printf("%d",x[i++]);
    printf("\n\n");
    return 0;
}

void rightShift(int p[],int x[],int nb)
{
    int i=0;
    while(nb-i-1)
    {
        x[nb-i-1]=x[nb-i-2];
        i++;
    }
    x[0]=p[nb-1];
    i=0;
    while(nb-i-1)
    {
        p[nb-i-1]=p[nb-i-2];
        i++;
    }
}

The result thus is combination of binary numbers in P and Q.

A brief explanation of what is done in the program:

Taken two decimal numbers, converted them to binary numbers, also found out 2’s compliment of multiplier(M). On each step comparing the values of LSB of Q and Q-1 on following steps as in Booth’s Algorithm completed all N steps. Note, after N steps, the value of Q will be same as when started. Right Shifts are to be done in such a way that MSB of P remains same as previous, LSB of P is MSB of Q, LSB of Q is Q-1 for new state.

Thus on completion of N steps, we get the product.

Example: for multiplying -5 and 10, above code gives following output

BOOTH's Algorithm
0-0   Right Shift.
0-1   Add M to P. Right Shift.
1-0   Add -M to P. Right Shift.
1-1   Right Shift.

Enter two numbers that are to be multiplied : -5 10

Multiplicand (Q) 10 -> 01010 and Multiplier (M) -5 -> 11011
we use -(M) i.e. 5 -> 00101

Step No.    P      Q    Q-1
0         00000  01010  0
1         00000  00101  0
        + 00101
          00101
2         00010  10010  1
        + 11011
          11101
3         11110  11001  0
        + 00101
          00011
4         00001  11100  1
        + 11011
          11100
5         11110  01110  0

Product in signed binary number is : 11110 01110

Hello World!

As in general every programmer starts with this simple code, I would here welcome the world to my blog.

#include <stdio.h>

int main()
{
    printf("Hello World!\n");
    printf("Welcome to my blog!\n");
    return 0;
}