Queston on Karatsuba Recursion

Question

I'm trying to implement a recursive Karatsuba algorithm. I successfully coded a recursive algorithm for multiplication but it calculates ad and bc. However, for this program, I've tried noting down each intermediate value namely ac, bd, total, sum. Many values don't turn up as the expected value. I can't figure out where my code is getting messed up. I'm still an amateur programmer and I've spent already several hours trying to debug but now I have no choice but to post my large code here:

#include <iostream>
using namespace std;

int approxLog(int n, int b) {
    return !(n/b < 1) ? 1+approxLog(n/b, b) : 1;
}

int power(int b, int e) {
    return (e < 1) ? 1 : b*power(b, e-1);
}

int odd1(int n) {
    if(n%2 != 0)
        return n-1;
    else
        return n;
}

int odd2(int n) {
    if(n%2 == 0)
        return n/2;
    else
        return n/2 + 1;
}

void num_split (int num, int d, int *a, int *b) {
    int  i = 1, tmp = 0, j = 1, k = 0;
    while (i <= d/2) {
        tmp += (num%10)*power(10, i-1);
        num /= 10;
        i++;
    }
    *b = tmp;
    tmp = 0;
    while (i <= d) {
        tmp += (num%10)*power(10, j-1);
        num /= 10;
        i++;
        j++;
    }
    *a = tmp;
    tmp = 0;
}

long long int multiply(int x, int y, int n) {
    int a = 0, b = 0, c = 0, d = 0;
    int ac = 0, bd = 0, total = 0, sum = 0;
    int *ptr_a = &a;
    int *ptr_b = &b;
    int *ptr_c = &c;
    int *ptr_d = &d;
    num_split(x, n, ptr_a, ptr_b);
    num_split(y, n, ptr_c, ptr_d);

    if((x < 10) || (y < 10)) {
        return x*y;
    }
    else {
        ac = multiply(a, c, odd2(n));
        bd = multiply(b, d, n/2);
        total = multiply((a+b), (c+d), odd2(n));
        // cout << total <<  endl;
        sum = total - ac - bd;
        return power(10, odd1(n))*ac + power(10, n/2))*sum + bd;
    }
}

int main() {
    int x = 1234, y = 1234;
    int n = approxLog(x, 10);
    long long int product = multiply(x, y, n);
    cout << product << endl;

    return 0;
}

It's an algorithm to multiply two integers. It's more efficient than the conventional elementary school approach. But unfortunately I do not have the adequate knowledge to elaborate more. — Jithakrishna Prakash, May 23 '18 at 18:02
using power and modulo for multiplication seems to be not very effective implementation. Usually power of 2 is used as base so you can get rid of those and use bit operations instead. In case of base 10 you can do this on strings or BCD ... see my [Fast bignum square computation](https://stackoverflow.com/q/18465326/2521214) for comparison of more multiplication methods (Karatsuba with code included) — Spektre, May 24 '18 at 07:09

score 0 · Accepted Answer · answered May 23 '18 at 16:40

The problem is that in each recursion, you should take the approx. log of the the bigger of x and y. So the following alteration in your code would fix the problem (notice the commented out portions too!):

long long int multiply(int x, int y)//, int n)
{
    int a = 0, b = 0, c = 0, d = 0;
    int ac = 0, bd = 0, total = 0, sum = 0;
    int *ptr_a = &a;
    int *ptr_b = &b;
    int *ptr_c = &c;
    int *ptr_d = &d;
    int n = (x>y)?approxLog(x, 10):approxLog(y, 10);
    num_split(x, n, ptr_a, ptr_b);
    num_split(y, n, ptr_c, ptr_d);

    if((x < 10) || (y < 10)) {
        return x*y;
    }
    else {
        ac = multiply(a, c);//, odd2(n));
        bd = multiply(b, d);//, n/2);
        total = multiply((a+b), (c+d));//, odd2(n));
        cout << total <<  endl;
        sum = total - ac - bd;
        return power(10, odd1(n))*ac + power(10, (n/2))*sum + bd;
    }
}

int main() {
    int x = 134546, y = 1234;
    //int n = approxLog(x, 10);
    long long int product = multiply(x, y);//, n);
    cout<<"Karatsuba: "<<product<<endl;
    cout<<"Normal:    "<<x*y<<endl;

    return 0;
}

This community is so responsive! Thank you so much for the answer! I still didn't get why passing n as a parameter didn't work albeit a messy approach.. Nevertheless I'm quite happy that there weren't any major modifications to my code — Jithakrishna Prakash, May 23 '18 at 17:59
According to the algorithm, you need to set the value of n to the approxLog of the bigger number in every recursion. You were not passing that value. You could theoretically calculate it at the end of every recursion and pass the new value, but that would be wasteful. — mahesh, May 23 '18 at 19:57
Passing n wasn't the problem in itself, but not correctly calculating the value of n in every recursion was the root cause. Not passing n is a by-product of fixing the actual issue. — mahesh, May 23 '18 at 19:58

Queston on Karatsuba Recursion

1 Answers1