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

Fast Doubling method to find nth Fibonacci number

One among very common questions asked in maths category in competitive programming is Fibonacci Series.

For a question that asks to find nth term of Fibonacci series, a naive approach to solve is an iterative method like

#define MOD 1000000007
long long int fib(long long int n)
{
    if(n < 2)
        return n;
    long long int a = 0,b = 1,ans;
    int i = 1;
    while(i < n)
    {
        ans = (a+b) % MOD;
        a = b;
        b = ans;
        i++;
    }
    return ans;
}

Above function has an O(n) complexity. With all our patience we may use it to calculate for at most n = 10^9 which gives output in around 10-15 seconds.

But as n gets larger, it takes hours,days,months,years,decades and so on for increasing n.

So the question is can we optimise it? Do we have methods to find nth Fibonacci number in less than a second?

Yes. We have few methods to do this. Out of them matrix exponentiation is most commonly used concept. Another well known concept is fast doubling method, which we are going to learn now.

Fast doubling is based on two formulae

F(2n) = F(n)[2*F(n+1) – F(n)]
F(2n + 1) = F(n)2 + F(n+1)2

Let us consider n starts from 0 and F(0) = 0. So our Fibonacci series would be F(0) = 0, F(1) = 1, F(2) = 1, F(3) = 2, F(4) = 3, F(5) = 5, F(6) = 8 …

For calculating terms, F(2n) & F(2n + 1), lets have a record of F(n) & F(n+1). By following this statement and taking care of equations and data type overflow, code would be as follows,

#include <bits/stdc++.h>

using namespace std;

#define MOD 1000000007;
long long int a,b,c,d;

void fast_fib(long long int n,long long int ans[])
{
    if(n == 0)
    {
        ans[0] = 0;
        ans[1] = 1;
        return;
    }
    fast_fib((n/2),ans);
    a = ans[0];             /* F(n) */
    b = ans[1];             /* F(n+1) */
    c = 2*b - a;
    if(c < 0)
        c += MOD;
    c = (a * c) % MOD;      /* F(2n) */
    d = (a*a + b*b) % MOD;  /* F(2n + 1) */
    if(n%2 == 0)
    {
        ans[0] = c;
        ans[1] = d;
    }
    else
    {
        ans[0] = d;
        ans[1] = c+d;
    }
}

int main()
{
    long long int n;        /* nth value to be found */
    scanf("%lld",&n);
    long long int ans[2]={0};
    fast_fib(n,ans);
    printf("%lld\n",ans[0]);
    return 0;
}

This code has a complexity of O(log n) which is way too faster than previously discussed function.

Approach to solve Minesweeper Master

This problem(Minesweeper Master) has been asked in Google Codejam qualification round 2014. You can view the problem statement here Minesweeper Master.

The problem in short could be explained as, for a given number of rows(r) and columns(c) in a minesweeper grid, we need to prepare a layout that consists of (m) number of mines. The mines are to be represented by ‘*’, empty spaces are to be denoted by ‘.’.

Our layout should be such that we need to win in one click(Hoping you played the game before. Else it is described in the question). We denote the position that is to be clicked on the layout as ‘c’.

An approach to crack this problem:

Remember there may be number of layouts possible for a given set of number of rows(r), number of columns(c) and number of mines(m).

A prologue for our approach to this problem..

The positions on the layout where a mines can be placed or can be clicked are referred as blocks.
Keep in mind the constraint on number of mines is always atleast one less that r*c(total number of blocks).
In all the cases the block that is clicked at the end of making of layout would be the bottom most-right most block.

Here lets start..

Considering different cases,

1)
If either number of rows or number of columns(or both) is 1.

This case has a solution for whatever might the other attribute is. Remember that number of mines that would be in the layout are always less than r*c(that would be atleast one less than total number of blocks.)

Few cases for sample :

	1 4 3  
	4 1 2  
	1 1 0

Solutions for above :

	Case #1:
	***c
	Case #2:
	*
	*
	*
	c
	Case #3:
	c

2) If number of columns are two and number of mines are not one less than total number of blocks.

There are few subcases in this.

i) If number of mines are odd, it is never possible to get a solution.
ex:

	      5 2 3

lets say solution is

	      **
	      *.
	      ..
	      ..
	      .c

But this is wrong. Because on clicking at a position ‘c'(which is most optimal) we get it like

	      **
	      *.
	      11
	      00
	      00

Which is obviously not a solution since we are unable to win in one click.
ii) If number of mines is 2 less than total number of blocks, it is also not possible
ex:

	      5 2 8

lets say solution is

	      **
	      **
	      **
	      **
	      .c

On clicking at position marked ‘c’ we get

	      **
	      **
	      **
	      **
	      .2

So even this condition fails.

iii) In any other case a solution is possible.
ex:

	      5 2 4

Solution is

	      **
	      **
	      ..
	      ..
	      .c

on clicking at position marked ‘c’ we get

	      **
	      **
	      22
	      00
	      00

Which is a perfect solution as we can win in one click.

3) A similar cases are possible for if number of rows are two.

There are few subcases in this.

i) If number of mines are odd, it is never possible to get a solution.
ex:

 	      2 5 3

lets say solution is

	      **...
	      *...c

But this is wrong. Because on clicking at a position ‘c'(which is most optimal) we get it like

	      **100
	      *.100

Which is obviously not a solution since we are unable to complete the game in one click.

ii) If number of mines is 2 less than total number of blocks, it is also not possible
ex:

	      2 5 8

lets say solution is

	      ****.
	      ****c

On clicking at position marked ‘c’ we get

	      ****.
	      ****2

So even this condition fails.

iii) In any other case a solution is possible.
ex:

	       2 5 4

Solution is

	       **...
	       **..c

on clicking at position marked ‘c’ we get

	       **200
	       **200

Which is a perfect solution as we can win in one click.

4) If number of mines given is one less than total number of blocks.

Marking all the blocks leaving one as containing mines(‘*’), and the remaining with ‘c’ so that it is to be clicked. We are considering bottom-right block is clicked and so mark all other as ‘c’.

sample cases:

		input
	
		2 5 9
		4 4 15
	
		output
	
		Case #1:
		*****
		****c
		Case #2:
		****
		****
		****
		***c

5) Rest all cases.

Here for a better approach, mines are arranged in first r-3 rows in horizontal manner starting from left in every row. For the last 3 rows, they are arranged in vertical manner starting from top to bottom filling from left most column first and moving towards right.

i) A case in horizontal arranging
( If the last mine is to be placed in a block in the ‘c-1’th column.)

That would be a wrong approach. Lets see that case in a sample example for say

                6 5 9

Solution would be

	    	*****
	    	****.
	    	.....
	    	.....
	    	.....
	    	....c

But on clicking the block having ‘c’, we remain with

		*****
		****.
		23321
		00000
		00000
		00000

So on setting an offset for such a case, we can make place the last mine in first column of next row.( Note that there could be only two positions possible for such a case. First column – next row, or first column – last row, as we will be having c in last column- last row).

One of the correct approach is

		*****
		***..
		*....
		.....
		.....
		....c

On clicking on ‘c’ would turn

		*****
		***42
		*4210
		11000
		00000
		00000
		00000

ii) Now while placing mines in last 3 rows(placing them vertically as discussed above).
( A similar case just like above, that is if the last element has to be placed in second last row.)

It would be a wrong approach if we do not make an offset and correct that. Lets see a case

                6 5 20

Solution would be

	    	*****
	    	*****
	    	*****
	    	**...
	    	**...
	    	*...c

On clicking the block having ‘c’, we remain with

		*****
		*****
		*****
		**432
		**200
		*.100

A wrong solution indeed. So similar to previous we can make an offset and let the last mine appear in 3rd last row of next column.

		*****
		*****
		*****
		***..
		*....
		*...c

On clicking ‘c’,

		*****
		*****
		*****
		***42
		*5210
		*2000

A correct approach!!!

Here we can be sure that you will not cross the array boundary like you may not got to a[r-3][c] (‘0’ notation) position. Because that case implies you have (r*c)-1 number of mines to which solution has been already set.

iii) If any one block surrounding ‘c’ are having a mine.

Lets see this case with an example.

    		6 5 28

output is

	    	*****
	    	*****
	    	*****
	    	*****
	    	****.
	    	****c

So in this case on clicking on ‘c’ we are left with,

	    	*****
	    	*****
	    	*****
	    	*****
	    	****.
	    	****2

Game here could not be completed in one step, so there will be no solution. We can here again create an offset for searching if any of the three blocks and if true then print out ‘Impossible’.

Here again we may note that the case in which all three surrounding blocks having a mine is already cleared.

Here ends all the possible cases that may arise. Thus framing a perfect code from this algorithm we will be able to crack the problem.

 

Here is my code using above algorithm.

#include <stdio.h>

int main()
{
    int t;
    scanf("%d",&t);
    int turn =1;
    while(turn<=t)
    {
        int r,c,m;
        scanf("%d %d %d",&r,&c,&m);
        char a[60][60]={'.'};
        int i=0,j=0;
        for(i=0;i<r;i++) //initiating matrix with '.'
        {
            for(j=0;j<c;j++)
            {
                a[i][j]='.';
            }
        }
        int mines=m;
        int flag=0;  //at the end if flag is still zero, then the case is impossible.
        
        if(r==1 || c==1) // if either number of rows or number of columns is one. This case would always get accepted.
        {
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    if(mines>0)
                    {
                        a[i][j]='*';
                        mines--;
                    }
                    else break;
                }
            }
            a[r-1][c-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }

        if(c==2 && !(m == (r*c)-1))  //If number of columns is 2, and m is not equal to one less than total number of blocks
        {
            if(m%2==1)  //If number of mines are odd in this case, it would never be possible.
            {
                goto imp;
            }
            
            if(m>(r*c)-4)  //If (r*c)-4 < number of mines < (r*c)-1
            {
                goto imp;
            }
            
            for(i=0;i<r;i++)  //all remaining cases here will be possible.
            {
                for(j=0;j<c;j++)
                {
                    if(mines>0)
                    {
                        a[i][j]='*';
                        mines--;
                    }
                    else break;
                }
            }
            a[r-1][c-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }

        if(r==2 && !(m == (r*c)-1))  //If number of rows is 2, and m is not equal to one less than total number of blocks
        {
            if(m%2==1)  //If number of mines are odd in this case, it would never be possible.
            {
                goto imp;
            }
            
            if(m>(r*c)-4)  //If (r*c)-4 < number of mines < (r*c)-1
            {
                goto imp;
            }
            
            for(j=0;j<c;j++)  //all remaining cases here will be possible.
            {
                for(i=0;i<r;i++)
                {
                    if(mines>0)
                    {
                        a[i][j]='*';
                        mines--;
                    }
                    else break;
                }
            }
            a[r-1][c-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }
        
        if(mines == (r*c)-1)  //if number of mines is one less than total number of blocks. Solution is always possible.
        {
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    a[i][j]='*';
                }
            }
            a[r-1][j-1]='c';
            flag=1;
            printf("Case #%d:\n",turn);
            for(i=0;i<r;i++)
            {
                for(j=0;j<c;j++)
                {
                    printf("%c",a[i][j]);
                }
                printf("\n");
            }
            goto imp;
        }

        int h1=0;
        for(i=0;i<r-3;i++)  //rest all cases
        {
            for(j=0;j<c;j++)
            {
                if(mines==1 && j==c-2)  //if last mine is to be filled in second last column, it would be wrong case. Setting offset.
                {
                    h1=1;
                    break;
                }
                if(mines>0)
                {
                    a[i][j]='*';
                    mines--;
                }
            }
            if(h1==1)
                break;
        }

        if(h1==1)  // if last mine is to be placed in second last column, making a correct apprach.
        {
            a[i+1][0]='*';
            mines--;
        }

        int h2=0;
        for(j=0;j<c;j++)
        {
            for(i=r-3;i<r;i++)
            {
                if(mines==1 && i==r-2)  ////if last mine is to be filled in second last row, it would be wrong case. Setting offset.
                {
                    h2=1;
                    break;
                }
                if(mines==1 && j==c-2)
                {
                    goto imp;
                }
                if(mines>0)
                {
                    a[i][j]='*';
                    mines--;
                }
                else break;
            }
            if(h2==1)
                break;
        }

        if(h2==1)  // if last mine is to be placed in second last row, making a correct apprach.
        {
            a[r-3][j+1]='*';
            mines--;
            if(j+1==c-2)
                goto imp;
        }

        a[r-1][c-1]='c';

        if(a[r-2][c-2]=='*' || a[r-1][c-2]=='*' || a[r-2][c-1]=='*') //If 'c' is surrounded by mine
            goto imp;

        flag=1;
        printf("Case #%d:\n",turn);  //printing out the solution
        for(i=0;i<r;i++)
        {
            for(j=0;j<c;j++)
            {
                printf("%c",a[i][j]);
            }
            printf("\n");
        }

        imp:
        if(flag==0)  //printing out impossible if flag=0
        {
            printf("Case #%d:\n",turn);
            printf("Impossible\n");
        }

        turn++;
    }


    return 0;
}

You could also download complete solution for this link. Download

In C,  a[5] == 5[a]

Yeah!!! Looks funny but true.

In C array indexing is actually defined as

a[i] = *(a+i)

You can also make this as

a[i] = *(i+a)

As from our childhood math, we know, a+i and i+a are equal.

As pointers are memory addressing, a[i] that is defined as *(a+i) is address of i elements further from address of “a”. This is also equal to “a” from i elements from beginning of address space (i+a).

And yes

"ABCD"[2] == 2["ABCD"] == 'C'

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