sir i need one complete example on karatsuba method for better understanding,please.

[pavant...@gmail.com]

Hi,

I have a question about what is happening in this video at 00:00:02 -

http://www.youtube.com/watch?v=gqb-kOfihE0#t=2s.

sir i need one complete example on karatsuba method for better understanding,please..

Thanks!

---

Reference Key - ag9zfm5wdGVsbW9vYzIwMTNyIgsSFVN0dWRlbnRRdWVzdGlvbkVudGl0eRiAgICAwdfBCAyiARZuc19ucHRlbF9pbnRlcm5hbF9tb29j

[online...@nptel.iitm.ac.in]

Here is one solution

#include <stdio.h>
#include <string.h>
#include <math.h>

// calculate the number of digits in a number
int num_size(int num) {
    char num_str[10];

    sprintf(num_str, "%d", num);
    return strlen(num_str);
}

// find maximum of two numbers
int max(int num1, int num2) {
    if(num2 > num1)
    return num2;
    return num1;
}

// split a number into two at a position
void split(int num, int pos, int *high, int *low) {
    *low = num % (int)pow(10, pos);
    *high = (num - *low)/pow(10, pos);
}

// Karatsuba multiplication
long int multiply(int num1, int num2) {
    int m, m2;
    int low1, low2, high1, high2;
    long int z0, z1, z2;

    if((num1 < 10) || (num2 < 10))
    return num1*num2;

    // calculates the size of the numbers
    m = max(num_size(num1), num_size(num2));
    m2 = m/2;
    // printf("m=%d m2=%d\n", m, m2);

    // split the digit sequences about the middle
    split(num1, m2, &high1, &low1);
    split(num2, m2, &high2, &low2);
    // printf("1st no %d %d, 2nd no %d %d\n", high1, low1, high2, low2);

    // 3 calls made to numbers approximately half the size
    z0 = multiply(low1, low2);
    z1 = multiply((low1+high1), (low2+high2));
    z2 = multiply(high1, high2);
    return (z2*pow(10,(2*m2))) + ((z1-z2-z0)*pow(10,(m2))) + (z0);
}

// main
int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%ld", multiply(a, b));
    return 0;
}