Сначала немного фона:
- Я первый постер, студент университета (не программист).
- Это не домашнее задание, я делаю это только для развлечения.
- Мой опыт программирования состоит из одного семестра (3 месяца) C ++ и некоторого QBasic в старшей школе.
- Да, я посмотрел библиотеки GMP и Bignum; очень сложно выучить материал из необработанных кодов, особенно без понимания намерений программистов. Кроме того, я хочу научиться делать это для себя.
Я кодирую функцию умножения для сколь угодно больших целых чисел. Я использую символьные массивы для представления этих чисел, с + или - в конце, чтобы служить в качестве часового (например, «12345+», «31415-»).
В настоящее время я реализую алгоритм Карацубы. Проблема в том, что при рекурсивном и динамическом назначении памяти эта функция в 5 раз медленнее, чем простой метод.
Я мог бы использовать некоторые советы о том, как сократить время работы.
char* dam(char* one, char* two){ // Karatsuba method
char* zero = intochar(0, 0);
int size_a = char_size(one) - 1;
int size_b = char_size(two) - 1;
if(compare(one, zero) == 0 || compare(two, zero) == 0)
return zero; // if either array is zero, product is zero
delete[] zero;
if(size_a < 4 && size_b < 4) // if both numbers are 3 digits or less, just return their product
return multiplication(one, two);
// is the product negative?
bool negative = one[size_a] == two[size_b]? false : true;
int digits = size_a > size_b ? size_a : size_b;
digits += digits & 1; // add one if digits is odd
int size = digits / 2 + 1; // half the digits plus sentinel
char* a, *b; // a and b represent one and two but with even digits
if(size_a != digits)
a = pad_char(one, digits - size_a); // pad the numbers with leading zeros so they have even digits
else
a = copy_char(one);
if(size_b != digits)
b = pad_char(two, digits - size_b);
else
b = copy_char(two);
char* a_left = new char[size]; // left half of number a
char* a_rite = new char[size]; // right half of number a
char* b_left = new char[size];
char* b_rite = new char[size];
memcpy(a_left, a, size - 1);
a_left[size - 1] = a[digits];
memcpy(a_rite, a + size - 1, size);
memcpy(b_left, b, size - 1);
b_left[size - 1] = b[digits];
memcpy(b_rite, b + size - 1, size);
delete[] a;
delete[] b;
char* p0 = dam(a_left, b_left); // Karatsuba product = p1*10^n + (p0+p2-p1)*10^(n/2) + p2
char* p2 = dam(a_rite, b_rite);
deduct(a_left, a_rite);
deduct(b_left, b_rite);
char* p1 = dam(a_left, b_left);
char* p3 = intochar(0, digits - 1); // p3 = p0 + p2 - p1
append(p3, p0); // append does naive addition
append(p3, p2);
deduct(p3, p1);
delete[] a_left;
delete[] a_rite;
delete[] b_left;
delete[] b_rite;
int sum_size = 2 * digits; // product of two numbers can have a maximum of n1 + n2 digits
char* sum = new char[sum_size + 1];
memset(sum, 0, sum_size);
if(negative)
sum[sum_size] = '-';
else
sum[sum_size] = '+';
char* left = extend_char(p0, digits, false); // extend returns a new array with trailing zeros
char* mid = extend_char(p3, size - 1, false);
append(sum, left);
append(sum, mid);
append(sum, p2);
delete[] p0;
delete[] p1;
delete[] p2;
delete[] p3;
delete[] left;
delete[] mid;
return sum;}