I have made a Biginteger class that performs multiplication operation according to Karatsuba's algorithm. But it seems that the code is not working perfectly.In the class I have made a function named karatsuba(BigInteger a1, BigInteger b1)that performs the Multilplication operation. There might be problems in this function as I have tried to store the original digits(neglecting the leading zeros) of the two big integer values into two integers or there might be problems in somewhere else. Can anyone provide me the corrected version of this function? My code is given below:

#include <stdio.h>
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
using namespace std;

#define MAX_DIGIT 100

class BigInteger {
    char d[MAX_DIGIT + 1]; // holds the number
    int ndigit; // returns total digits

public:
    BigInteger() {
        d[0] = '+'; // positive number
        ndigit = 0;

        for (int k = 1; k <= MAX_DIGIT; k++)
            d[k] = 0;
    }

    BigInteger(int num) {
        if (num < 0) {
            num = -num;
            d[0] = '-';
        }
        else
            d[0] = '+';

        int r;
        int k = MAX_DIGIT;
        ndigit = 0;

        do {
            r = num % 10;
            d[k] = r;
            num = num / 10;
            ndigit++;
            k--;

        } while (num != 0);

        while (k > 0)
            d[k--] = 0;
    }

    void print() {
        if (d[0] == '-')
            printf("-");

        for (int k = MAX_DIGIT - ndigit + 1; k <= MAX_DIGIT; k++) {
            printf("%d", d[k]);
        }
    }

    int min(int n1, int n2) { // returns min
        return (n1 < n2) ? n1 : n2;
    }

    int karatsuba(BigInteger a1, BigInteger b1) {
        int n1, n2 = 0;

        for (int i = MAX_DIGIT - a1.ndigit + 1; i <= MAX_DIGIT; i++) {
            n1 = 10 * n1 + a1.d[i];
        }

        for (int i = MAX_DIGIT - b1.ndigit + 1; i <= MAX_DIGIT; i++) {
            n2 = 10 * n2 + b1.d[i];
        }

        char s1[MAX_DIGIT]; // holds the string
        char s2[MAX_DIGIT];
        sprintf(s1, "%d", n1); // converts int to string
        sprintf(s2, "%d", n2); // string is in s1 and s2

        int l1, l2, l;
        int i, mask1 = 1;
        int a, b, c, d;
        int res1, res2, res3;
        l1 = strlen(s1); // returns number of digits
        l2 = strlen(s2);

        if (n1 == 0 || n2 == 0)   //base condition 
            return (0);

        l = min(l1, l2);   // returns minimum of the two

        if (l > 1) {
            for (i = 1; i <= l / 2; i++)
                mask1 = mask1 * 10;
            a = n1 / mask1;
            b = n1 % mask1;
            c = n2 / mask1;
            d = n2 % mask1;
            res1 = karatsuba(a, c);
            res2 = karatsuba(b, d);
            res3 = karatsuba(a + b, c + d);

            if (l % 2 == 0)
                return (res1 * pow(10, l) +
                        (res3 - res1 - res2) * pow(10, l / 2) + res2);
            else
                return (res1 * pow(10, l - 1) +
                        (res3 - res1 - res2) * pow(10, l / 2) + res2);
        }

        return (n1 * n2);
    } // end karastuba function

}; // end class

int main() {
    return 0;
}

One thing I noticed is that your algorithm is using the literal value of char instead of offsetting it by 48 to get the integer value represented by the char.

Edited 2 Years Ago by tinstaafl

This article has been dead for over six months. Start a new discussion instead.