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++)
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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.