Getting error in Karatsuba's multiplication program

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:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#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;
I don't have a lot of time to play right now, but if i get a chance I'll look at this someone this week.
e 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.

That is certainly a problem if you use values larger than can be held in an int. However, I think the bigger problem right now is that you use an uninitialized variable (that your compiler probably warns you about) in the karatsuba function, which has the identifier n1.

Line 63 should be int n1 = 0, n2 = 0;
Topic archived. No new replies allowed.