0

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;
}
```