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










Bit Stuffing Code Implementation in Java







By







-














Image







   This is an implementation of the Bit Stuffing  popularly used in data communication, also known as one of the concepts of Framing  data bits. To know more please  click here.     Sample Output:      This is a sample output with data binary data entered as 11001111110.      Program Code:     import java.util.*; public class BitStuffing {        public static void main(String[] args)       {               System.out.print("Enter the Binary message: ");               Scanner sn=new Scanner(System.in);               String data = sn.nextLine();               String res = new String();               String out=new String();               int counter = 0;               for(int i=0;i<data.length();i++)               {    if (data.charAt(i)!='1' && data.charAt(i)!='0')                         {                             System.out.println("Enter only Binary values!!!");                             return;                         }            ...








Read more