Negative number multiplication program [Booth's Algorithm]

By Sidharth Patnaik -
This program can be used for multiplying negative numbers. Basically it is just the Booth's Algorithm Implementation. Here the number is first converted to its binary form if the number is negative number then its then converted to its 2's compliment form. Then according to the algorithm, arithmetic right shifting is done.

Sample Output:



The Code:
#include <stdio.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]);
    }
}
 
int main(){
   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]);
     }
     return 0;
}


Description:
This is just an implementation of the algorithm, you can find any code like this anywhere from the web. Nothing new to say about it !













































Popular posts from this blog









Non Restoring Division Algorithm Implementation in C







By


Sidharth Patnaik



-














Image







This  is a Dynamic program for the implementation of the NON RESTORING  Division Algorithm in C Language. Non Restoring Division uses Left Shift Operations, Twos' Compliment and Binary Addition.   Screenshots[Demo]       The Code  #include<stdio.h> #include<malloc.h> int *a,*q,*m,*mc,*c,n,d; int powr(int x,int y) {  int s=1,i;  for(i=0;i<y;i++)    s=s*x;  return s; } void print(int arr[],int n) {  int i;  for(i=0;i<n;i++)   printf("%d ",arr[i]); } void bin(int n, int arr[]){     int r, i = 0;     do{         r = n % 2;         n /= 2;         arr[i] = r;         i++;     }while(n > 0);  } void set(int array[], int x){     int i,tmp[20]={0};     for(i = x -1; i >=0; i--)   tmp[x-1-i]=array[i];  for(i=0;i<x;i++)   array[i]=tmp[i];  } int len(int x) {  int i=0;  while(powr(2,i)<=x) i++;  return ++i; }  void addBinary(int a1[], int a2[]) {     int bi[2]={0},ca[20]={0};     int t=len(n),tmp=0;     int *su=(int*)malloc(sizeof(int)*len(n));  while(t...








Read more










Hackerrank String Reduction Solution







By


Sidharth Patnaik



-














Image







This is the solution to the program, solved in python. The Question can be found in the Algorithm domain of Hackerrank.  Problem Statement:  Given a string consisting of letters, a, b and c, we can perform the following operation: Take any two adjacent distinct characters and replace them with the third character. For example, if 'a' and 'c' are adjacent, they can replaced by 'b'. Find the smallest string which we can obtain by applying this operation repeatedly?   Screenshots[Demo]       The Code:  def cnt(x):      m={}      m['a']=0;m['b']=0;m['c']=0      for c in x:   if c not in m:              m[c]=1   else:       m[c]+=1      return m def red(x):      xm=cnt(x)      print x,xm      if((xm['a']==0 and xm['b']==0 ) or (xm['a']==0 and xm['c']==0 ) or (xm['b']==0 and xm['c']==0)):           return len(x);      if((xm['a']%2==0 and xm['b']%2==0 and xm['c']%2==0) or (...








Read more










Hackerrank Modified Kaprekar Numbers Solution







By


Sidharth Patnaik



-














Image







This is the solution to the Modified Kaprekar Numbers found in the implementation section of the algorithm domain in Hackerrank. A modified Kaprekar number  is a positive whole number n  with d  digits, such that when we split its square into two pieces - a right hand piece r with d digits and a left hand piece l that contains the remaining d or d−1 digits, the sum of the pieces is equal to the original number (i.e. l + r = n) .   Screenshot      The Code  def sendKap(x,s):  y=x*x  y=str(y)  s1=y[:len(y)/2:]  s2=y[len(y)/2::]  s3=int(s1)+int(s2)  if(s3==x):   s.append(str(x)) st=input() en=input() s=[] for i in range(st,en+1):  if(i>9):   sendKap(i,s)  elif(i==1):   s.append(str(i))  elif(i==9):   s.append(str(i)) if(len(s)==0):  print 'INVALID RANGE' else:  print ' '.join(s)  Got any problems feel free to comment them here !








Read more