Ошибка целочисленного умножения Карацубы из-за ошибки сегментации

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

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. После исправления первых двух проблем и повторного тестирования переполнение стека по-прежнему происходит. Итак, я сравнил ваш алгоритм с другим, который нашел в гугле:
   Разделяй и властвуй | Набор 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 доступен в "не суффиксном вкусе". (Заголовок с «.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-PC с 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).

$