завершается сигналом SIGSEGV (Ошибка границы адреса) в рекурсивной функции

Я пытаюсь реализовать алгоритм Карацубы для умножения. Я вроде следую за псевдокодом в этой вики страница. Но я всегда получаю эту ошибку:

завершается сигналом SIGSEGV (ошибка границы адреса)

Когда я заменил строки, которые вызывают рекурсию, чем-то другим:

z0 = multiply(a, c);
z1 = multiply(b, d);
z2 = multiply(a+b, c+d);

ошибка исчезла.

Вот мой код:

#include <iostream>
#include <math.h>

long int multiply(int x, int y);
int get_length(int val);

int main()
{
int x = 0, y = 0;
long int result = 0;

std::cout << "Enter x: ";
std::cin >> x;
std::cout << "Enter y: ";
std::cin >> y;

result = multiply(x, y);
std::cout << "Result: " << result << std::endl;
return 0;
}

long int multiply(int x, int y)
{
if(x < 10 || y < 10) {
return x * y;
}

int x_len = get_length(x);
int y_len = get_length(y);

long int z0 = 0 , z1 = 0, z2 = 0;
int a = 0, b = 0, c = 0, d = 0;

a = x / pow(10, x_len);
b = x - (a * pow(10, x_len));
c = y / pow(10, y_len);
d = y - (c * pow(10, y_len));

z0 = multiply(a, c);
z1 = multiply(b, d);
z2 = multiply(a+b, c+d);

return (pow(10, x_len) * z0) + (pow(10, x_len/2) * (z2 - z1 - z0)) + z1;
}

int get_length(int val)
{
int count = 0;
while(val > 0) {
count++;
val /= 10;
}
return count;
}

1

Решение

Я нашел причину проблемы.
Это было из-за этих строк:

a = x / pow(10, x_len);
b = x - (a * pow(10, x_len));
c = y / pow(10, y_len);
d = y - (c * pow(10, y_len));

Так должно быть x_len / 2 вместо x_len и то же самое с y_len, Поскольку это приводит к тому, что рекурсия бесконечна.

2

Другие решения

Вы используете pow Функция для целочисленных полномочий. Это не целочисленная функция. Код свой pow функция, которая подходит для вашего приложения. Например:

int pow(int v, int q)
{
int ret = 1;
while (q > 1)
{
ret*=v;
q--;
}
return ret;
}

Убедитесь, что поставили int pow(int, int); на вершине.

0

По вопросам рекламы [email protected]