Sunday, 26 May 2013

C program for implementing Restoring Division algorithm

/*Program for implementing Restoring Division algorithm.*/
#include <stdio.h>
#include <conio.h>
#include <math.h>

int a=0,b=0,c=0,com[5]={1,0,0,0,0},s=0;
int anum[5]={0},anumcp[5] ={0},bnum[5]={0};
int acomp[5]={0},bcomp[5]={0},rem[5]={0},quo[5]={0},res[5]={0};

void binary(){
     a = fabs(a);
     b = fabs(b);
     int r, r2, i, temp;
     for(i = 0; i < 5; i++){
           r = a % 2;
           a = a / 2;
           r2 = b % 2;
           b = b / 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];
   }
}
void add(int num[]){
     int i;
     c = 0;
     for( i = 0; i < 5; i++){
           res[i] = rem[i]+ num[i] + c;
           if(res[i]>=2){
                c = 1;
           }
           else
                c = 0;
           res[i] = res[i]%2;
     }
     for(i = 4; i>= 0; i--){
           rem[i] = res[i];
           printf("%d",rem[i]);
     }
     printf(":");
     for(i = 4; i>= 0; i--){
           printf("%d",anumcp[i]);
     }
}
void shl(){//for shift left
     int i;
     for(i = 4; i > 0  ; i--){//shift the remainder
           rem[i] = rem[i-1];
     }
     rem[0] = anumcp[4];
     for(i = 4; i > 0  ; i--){//shift the remtient
           anumcp[i] = anumcp[i-1];
     }
     anumcp[0] = 0;
     printf("\nSHIFT LEFT: ");//display together
     for(i = 4; i>= 0; i--){
           printf("%d",rem[i]);
     }
     printf(":");
     for(i = 4; i>= 0; i--){
           printf("%d",anumcp[i]);
     }
}

void main(){
     clrscr();
     int i;
     printf("\t\tRESTORING DIVISION 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 Quotient = %d", a/b);
     printf("\nExpected Remainder = %d", a%b);
     if(a*b <0){
           s = 1;
     }

     binary();
     printf("\n\nUnsigned Binary 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-->");
     //division part
     shl();
     for(i=0;i<5;i++){
           printf("\n-->"); //start with subtraction
           printf("\nSUB B: ");
           add(bcomp);
           if(rem[4]==1){//simply add for restoring
                printf("\n-->RESTORE");
                printf("\nADD B: ");
                anumcp[0] = 0;
                add(bnum);
           }
           else{
                anumcp[0] = 1;
           }
           if(i<4)
                shl();

     }
     printf("\n----------------------------");
     printf("\nSign of the result = %d",s);
     printf("\nRemainder is = ");
     for(i = 4; i>= 0; i--){
           printf("%d",rem[i]);
     }
     printf("\nQuotient is = ");
     for(i = 4; i>= 0; i--){
           printf("%d",anumcp[i]);
     }
getch();

}

3 comments:

  1. hey bro can i get the explanation for this?.......

    ReplyDelete
    Replies
    1. Hi Sailesh,
      I think you can get a good description of the algorithm in any book related with Computer Architecture. I would personally recommend "Computer System Architecture" by Morris Mano.

      Regarding my program, the following algorithm should help:
      1. Start
      2. Quotient = 0, Remainder =0 and Sign = 0
      3. Ask user to enter two decimal numbers: n1, n2
      4. Convert their absolute values into binary and store in arrays num1 and num2
      5. Two’s complement num2 and store as ncom
      6. Create a copy of num1 as ncopy
      7. If the product is negative, set sign = 1
      8. Shift left Remainder : ncopy; counter = 0
      9. Add ncom to Remainder
      9.1 Set LSB of ncopy as 0.
      9.2 If result is negative, restore the remainder
      9.3 Otherwise, Set LSB of ncopy as 1.
      10. If counter < bits in num1, Shift left Remainder : ncopy
      11. counter = counter + 1
      12. Repeat 9, 10 and 11 until all bits of num1 are traced
      13. Display final result as Sign, Remainder : ncopy
      14. End

      Delete

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

Follow by Email