patterncppModerate
Karatsuba C++ implementation
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
```
#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
I'm sure a lot more reviews will come from others.
You don't need the
The C++ equivalent:
This generates a compiler warning, for good reason:
the arguments of
Why is this line there at all? I suggest to remove it.
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.