Wednesday, May 14, 2014

Karatsuba Algorithm

This is a C code implementing Karatsuba Algorithm for integer multiplications using recursive function calls that I programmed while taking "Algorithms: Design and Analysis, Part 1" courses from free Stanford online course provided at Coursera. It's been a while since I used C, but this is a good start to stir up my old memories and get into the world of Algorithms.
#include 
#include 

int count;

int Karatsuba(int a, int b)
{
   int temp1 = 0;
   int temp2 = 0;
   count++;

   if(a/10 == 0){ // a is a single digit
      if(b/10 == 0){ // b is also a single digit
         return a*b; // return the product a*b
      }
      else {  // b is not a single digit
         temp1 = Karatsuba(0,b/10);
         temp2 = Karatsuba(a,b%10);
         return 100*temp1 + 10*(Karatsuba(a,b/10+b%10) - temp1 - temp2) + temp2;
      }
   }
   else{  // a is not a single digit
      if(b/10 == 0){ // b is a single digit
         temp1 = Karatsuba(a/10,0);
         temp2 = Karatsuba(a%10,b);
         return 10*(Karatsuba(a/10+a%10,b) - temp1 - temp2) + temp2;
      }
      else{          // b is not a single digit
         temp1 = Karatsuba(a/10,b/10);
         temp2 = Karatsuba(a%10,b%10);
         return 100*temp1 + 10*(Karatsuba(a/10+a%10,b/10+b%10) - temp1 - temp2) + temp2;
      }
   }
}


int main(int argc, char** argv)
{
   int x, y;

   printf("First Number: ");
   scanf("%d", &x);

   printf("Second Number: ");
   scanf("%d", &y);

   printf("Grade School Algorithm: %d * %d = %d\n", x, y, x*y);
   printf("Karatsuba Algorithm: %d * %d = %d \n", x, y, Karatsuba(x,y));
   printf("Number of Karatsuba Function Calls: %d\n", count);
   _getch();
   return 0;
}

No comments :

Post a Comment