Неудачное умножение Карацубы с ошибкой сегментации

В вашем коде есть три серьезные проблемы:

1. result = (char)carry + result; не работает.
   Керри имеет значение между 0 (0 * 0) и 8 (9 * 9). Он должен быть преобразован в соответствующее значение ASCII:
   result = (char)(carry + '0') + result;,

2. Это приводит к следующей проблеме: перенос переносится, даже если 0, Есть if заявление отсутствует:
   if (carry/* != 0*/) result = (char)(carry + '0') + result;,

3. После исправления первых двух проблем и повторного тестирования переполнение стека все еще происходит. Итак, я сравнил ваш алгоритм с другим, который я нашел в Google:
   Разделяй и властвуй | Набор 4 (алгоритм Карацубы для быстрого умножения)
   (и, возможно, это было ваше происхождение, потому что это выглядит очень похоже). Не копая глубже, я исправил то, что выглядело как простая ошибка переноса:
   return P1 * pow(10, 2 * sh) + P2 * pow(10, sh) + P3;
   (Я заменил length от 2 * sh а также length/2 от sh как я видел в гугл-коде. Для меня стало очевидным, что в отладчике длина может иметь нечетные значения, так что sh а также length/2 разные значения.

После этого ваша программа стала работать.

Я изменил main() функция, чтобы проверить это немного сложнее:

#include <cmath>
#include <iostream>
#include <string>

using namespace std;

string intToStr(int i)
{
string text;
do {
text.insert(0, 1, i % 10 + '0');
i /= 10;
} while (i);
return text;
}

// Method to make strings of equal length
int makeEqualLength(string &fnum, string &snum)
{
int l1 = (int)fnum.length();
int l2 = (int)snum.length();
return l1 < l2
? (fnum.insert(0, l2 - l1, '0'), l2)
: (snum.insert(0, l1 - l2, '0'), l1);
}

int singleDigitMultiplication(const string& fnum, const string& snum)
{
return ((fnum[0] - '0') * (snum[0] - '0'));
}

string addStrings(string& s1, string& s2)
{
int length = makeEqualLength(s1, s2);
int carry = 0;
string result;
for (int i = length - 1; i >= 0; --i) {
int fd = s1[i] - '0';
int sd = s2[i] - '0';
int sum = (fd + sd + carry) % 10 + '0';
carry = (fd + sd + carry) / 10;
result.insert(0, 1, (char)sum);
}
if (carry) result.insert(0, 1, (char)(carry + '0'));
return result;
}

long int multiplyByKaratsubaMethod(string fnum, string snum)
{
int length = makeEqualLength(fnum, snum);
if (length == 0) return 0;
if (length == 1) return singleDigitMultiplication(fnum, snum);

int fh = length / 2;
int sh = length - fh;

string Xl = fnum.substr(0, fh);
string Xr = fnum.substr(fh, sh);
string Yl = snum.substr(0, fh);
string Yr = snum.substr(fh, sh);

long int P1 = multiplyByKaratsubaMethod(Xl, Yl);
long int P3 = multiplyByKaratsubaMethod(Xr, Yr);
long int P2
= multiplyByKaratsubaMethod(addStrings(Xl, Xr), addStrings(Yl, Yr))
- P1 - P3;
return P1 * pow(10, 2 * sh) + P2 * pow(10, sh) + P3;
}

int main()
{
int nErrors = 0;
for (int i = 0; i < 1000; i += 3) {
for (int j = 0; j < 1000; j += 3) {
long int result
= multiplyByKaratsubaMethod(intToStr(i), intToStr(j));
bool ok = result == i * j;
cout << i << " * " << j << " = " << result
<< (ok ? " OK." : " ERROR!") << endl;
nErrors += !ok;
}
}
cout << nErrors << " error(s)." << endl;
return 0;
}

Примечания об изменениях, которые я сделал:

1. Что касается std Библиотека: Пожалуйста, не смешивайте заголовки с «.h» и без. Каждый заголовок std Библиотека доступна в «non-суффикс-вкус». (Заголовок с «.h» является либо заголовком C, либо старомодным.) Заголовки библиотеки C были адаптированы для C ++. У них есть старое имя с префиксом «c» и без суффикса «.h».
   Таким образом, я заменил #include <math.h> от #include <cmath>,

2. Я не мог удержаться, чтобы сделать makeEqualLength() немного короче.

3. Пожалуйста, обратите внимание, что много методов в std использование std::size_t вместо int или же unsigned, std::size_t имеет соответствующую ширину, чтобы сделать индекс массива и арифметику указателя, то есть «ширину машинного слова». Я долгое время считал, что int а также unsigned должен иметь «ширину машинного слова» и не заботиться о size_t, Когда мы изменили в Visual Studio с x86 (32 бита) на x64 (64 бита), я усвоил сложный путь, который я очень ошибался: std::size_t 64 бит сейчас, но int а также unsigned все еще 32 бит. (MS VC ++ не является исключением. Другие производители компиляторов (но не все) делают это так же.)
   Я вставил несколько приведений типа C, чтобы удалить предупреждения из вывода компилятора. Такие приведения для удаления предупреждений (независимо от того, используете ли вы C-броски или лучше C-броски), всегда следует использовать с осторожностью и следует понимать как подтверждение: Уважаемый компилятор. Я вижу, у вас есть проблемы, но я (верю) знаю и уверяю вас, что это должно работать нормально.

4. Я не уверен в вашем намерении использовать long int в некоторых местах. (Возможно, вы перенесли этот код из оригинального источника, не заботясь о нем.) Как вы наверняка знаете, фактический размер всех int типы могут отличаться в зависимости от наилучшей производительности целевой платформы. Я работаю на Intel-ПК с Windows 10, используя Visual Studio. sizeof (int) == sizeof (long int) (32 бита). Это не зависит от того, компилирую ли я код x86 (32 бита) или код x64 (64 бита). То же самое верно для gcc (на cygwin в моем случае), а также на любом Intel-ПК с Linux (AFAIK). Для предоставленного большего типа, чем int ты должен выбрать long long int,

Я сделал пример сеанса в Cygwin на Windows 10 (64 бит):

$ g++ -std=c++11 -o karatsuba karatsuba.cc

$ ./karatsuba
0 * 0 = 0 OK.
0 * 3 = 0 OK.
0 * 6 = 0 OK.

и т. д.

999 * 993 = 992007 OK.
999 * 996 = 995004 OK.
999 * 999 = 998001 OK.
0 error(s).

$