#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; }
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.
Subscribe to:
Post Comments
(
Atom
)
No comments :
Post a Comment