我正在尝试实现用于乘法的 Karatsuba 算法。我有点遵循这个 wiki 中的伪代码 page .但我总是收到这个错误:
terminated by signal SIGSEGV (Address boundary error)
当我用其他东西替换导致递归发生的行时:
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;
}
最佳答案
我找到了问题的原因。 这是因为这些行:
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
一样。因为它导致递归是无限的。
关于c++ - 递归函数中由信号 SIGSEGV(地址边界错误)终止,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/39088472/