Tuesday, 14 May 2013

C program for Booth's multiplication algorithm


Pseudocode:

1.Start
2.Product = 0
3.Ask user to enter two decimal numbers: n1, n2
4.Convert them into binary and store in arrays num1 and num2
5.Two’s complement the numbers if they are negative
6.Two’s complement num2 and store as ncom
7.Create a copy of num1 as ncopy
8.Set q = 0
9.If num1[i] = = q, arithmetic shift product : ncopy
10.Else if num1[i] == 1 and q ==0, add ncom to product and arithmetic shift product : ncopy
11.Else add num2 to product and arithmetic shift product : ncopy
12.In each step set q = num1[i] after shift operation
13.Repeat steps 9,10,11 and 12 until all bits of num1 are shifted out
14.Display final result as product : ncopy
15.End

Program:
/*Program for implementing Booth's multiplication algorithm.*/
#include <stdio.h>
#include <conio.h>
#include <math.h>

int a=0,b=0,c=0,a1=0,b1=0,com[5]={1,0,0,0,0};
int anum[5]={0},anumcp[5] ={0},bnum[5]={0};
int acomp[5]={0},bcomp[5]={0},pro[5]={0},res[5]={0};

void binary(){
     a1 = fabs(a);
     b1 = fabs(b);
     int r, r2, i, temp;
     for(i = 0; i < 5; i++){
           r = a1 % 2;
           a1 = a1 / 2;
           r2 = b1 % 2;
           b1 = b1 / 2;
           anum[i] = r;
           anumcp[i] = r;
           bnum[i] = r2;
           if(r2 == 0){
                bcomp[i] = 1;
           }
           if(r == 0){
                acomp[i] =1;
           }
     }
   //part for two's complementing
   c = 0;
   for( i = 0; i < 5; i++){
           res[i] = com[i]+ bcomp[i] + c;
           if(res[i]>=2){
                c = 1;
           }
           else
                c = 0;
           res[i] = res[i]%2;
     }
   for(i = 4; i>= 0; i--){
     bcomp[i] = res[i];
   }
   //in case of negative inputs
   if(a<0){
      c = 0;
     for(i = 4; i>= 0; i--){
           res[i] =0;
     }
     for( i = 0; i < 5; i++){
           res[i] = com[i]+ acomp[i] + c;
           if(res[i]>=2){
                c = 1;
           }
           else
                c = 0;
           res[i] = res[i]%2;
     }
     for(i = 4; i>= 0; i--){
           anum[i] = res[i];
           anumcp[i] = res[i];
     }

   }
   if(b<0){
     for(i=0;i<5;i++){
           temp = bnum[i];
           bnum[i] = bcomp[i];
           bcomp[i] = temp;
     }
   }
}
void add(int num[]){
     int i;
   c = 0;
     for( i = 0; i < 5; i++){
           res[i] = pro[i]+ num[i] + c;
           if(res[i]>=2){
                c = 1;
           }
           else
                c = 0;
           res[i] = res[i]%2;
     }
     for(i = 4; i>= 0; i--){
     pro[i] = res[i];
           printf("%d",pro[i]);
     }
   printf(":");
   for(i = 4; i>= 0; i--){
           printf("%d",anumcp[i]);
     }
}
void arshift(){//for arithmetic shift right
     int temp = pro[4], temp2 = pro[0],i;
     for(i = 1; i <5  ; i++){//shift the MSB of product
           pro[i-1] = pro[i];
     }
     pro[4] = temp;
   for(i = 1; i < 5  ; i++){//shift the LSB of product
           anumcp[i-1] = anumcp[i];
     }
   anumcp[4] = temp2;
     printf("\nAR-SHIFT: ");//display together
   for(i = 4; i>= 0; i--){
           printf("%d",pro[i]);
     }
   printf(":");
   for(i = 4; i>= 0; i--){
           printf("%d",anumcp[i]);
     }
}

void main(){
     clrscr();
   int i, q=0;
     printf("\t\tBOOTH'S MULTIPLICATION ALGORITHM");
     printf("\nEnter two numbers to multiply: ");
     printf("\nBoth must be less than 16");
   //simulating for two numbers each below 16
     do{
           printf("\nEnter A: ");
           scanf("%d",&a);
           printf("Enter B: ");
           scanf("%d",&b);
     }while(a>=16 || b>=16);

     printf("\nExpected product = %d", a*b);
  

     binary();
     printf("\n\nBinary Equivalents are: ");
     printf("\nA = ");
     for(i = 4; i>= 0; i--){
           printf("%d",anum[i]);
     }
     printf("\nB = ");
     for(i = 4; i>= 0; i--){
           printf("%d",bnum[i]);
     }
   printf("\nB'+ 1 = ");
   for(i = 4; i>= 0; i--){
           printf("%d",bcomp[i]);
     }
     printf("\n\n");
     for(i=0;i<5;i++){
           if(anum[i] == q){//just shift for 00 or 11
           printf("\n-->");
                arshift();
         q = anum[i];
           }
           else if(anum[i] == 1 && q == 0){//subtract and shift for 10
           printf("\n-->");
         printf("\nSUB B: ");
                add(bcomp);//add two's complement to implement subtraction
                arshift();
         q = anum[i];
           }
           else{//add ans shift for 01
           printf("\n-->");
         printf("\nADD B: ");
                add(bnum);
                arshift();
         q = anum[i];
           }
     }
  
     printf("\nProduct is = ");
     for(i = 4; i>= 0; i--){
           printf("%d",pro[i]);
     }
   for(i = 4; i>= 0; i--){
           printf("%d",anumcp[i]);
     }
getch();
}

©Dixit Bhatta 2013

No comments:

Post a Comment

Was this post helpful? Ask any questions you have, I will try to answer them for you.

Follow by Email