HiveBrain v1.2.0
Get Started
← Back to all entries
patterncppModerate

Karatsuba C++ implementation

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
implementationkaratsubastackoverflow

Problem

I've written an algorithm for integer multiplication using the Karatsuba method in C++. This implementation is far from ideal, so any comments are welcome.

```
#define _CRT_SECURE_NO_WARNINGS

#include

#include
#include
#include
#include
#include
#include

const int MAX_LENGTH = 50000 * 2 + 1;

void add_leading_zeros(char* a, int n) {
int lena = strlen(a);
for (int i = lena - 1 + n; i >= n; --i) {
a[i] = a[i - n];
}
a[lena + n] = 0;
for (int i = 0; i = 0; --inda, --indb) {
int x = a[inda] - '0';
int y = indb >= 0 ? b[indb] - '0' : 0;

int cur = x + y + toAdd;

if (cur >= 10) {
toAdd = 1;
cur -= 10;
} else {
toAdd = 0;
}

res[inda] = cur + '0';
}

if (toAdd == 1) {
add_leading_zeros(res, 1);
res[0] = '1';
}
}

// assume that a > b
void sub(char a, char b, char* res) {
int lena = strlen(a);
int lenb = strlen(b);

//assert(lena >= lenb);

int toSub = 0;
for (int inda = lena - 1, indb = lenb - 1; inda >= 0; --inda, --indb) {
int x = a[inda] - '0';
int y = indb >= 0 ? b[indb] - '0' : 0;

if (toSub == 1) {
x--;
}
int cur;
if (x < y) {
cur = x + 10 - y;
toSub = 1;
} else {
cur = x - y;
toSub = 0;
}

res[inda] = cur + '0';
}
}

// returns a * 10^n
void mult10(char* a, int n) {
int lena = strlen(a);

if (lena == 1 && a[0] == '0') {
return;
}

for (int i = lena; i < lena + n; ++i) {
a[i] = '0';
}
a[lena + n] = 0;
}

char* CreateArray(int len) {
char* res = new char[len];
memset(res, 0, len);
return res;
}

// add leading zeros if needed
void make_equal_length(char a, char b) {
int lena = strlen(a);
int lenb = strlen(b);

int n = std::max(lena, lenb);

add_leading_zeros(a, n - lena);
add_leading_zeros(b, n - lenb);
}

void karatsuba(char x, char y, char* res) {
make_equal_length(x, y);

int len = strlen(x);
if (len == 1) {
int val = (x[0] - '0') * (y[0] - '0');
if

Solution

If you prefer programming in C-style, I suggest to use C.
If you want to use any part of C++, I suggest to embrace it fully.

I'll review only the main method for now,
I'm sure a lot more reviews will come from others.

You don't need the \n here. You can just drop it, it will work the same way:

scanf("%s\n%s", a, b);


The C++ equivalent:

std::cin >> a >> b;


This generates a compiler warning, for good reason:
the arguments of scanf should be pointers, but it's an int.
Why is this line there at all? I suggest to remove it.

scanf("%d", 1);

Code Snippets

scanf("%s\n%s", a, b);
std::cin >> a >> b;
scanf("%d", 1);

Context

StackExchange Code Review Q#64679, answer score: 12

Revisions (0)

No revisions yet.