1

I'm trying to implement Karatsuba algorithm for multiplication. I'm kinda follow the pseudocode in this wiki page. But I'm always getting this error:

terminated by signal SIGSEGV (Address boundary error)

When I replaced the lines that cause the recursion to happen with something else:

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

the error disappeared.

Here's my code:

#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;
}
Rafael Adel
  • 7,673
  • 25
  • 77
  • 118
  • What values did you enter for `x` and `y`? Also, it looks like you don't understand the `pow` function. It's not an integer function. – David Schwartz Aug 22 '16 at 20:50
  • @DavidSchwartz Anything larger than 9 causes the error. – Rafael Adel Aug 22 '16 at 20:51
  • Without having read the code I'll still venture a guess: infinite recursion, leading to stack overflow.. – Jesper Juhl Aug 22 '16 at 20:52
  • @JesperJuhl Yes !! I got it as you said, it's an infinite recursion. because of the line `a = x / pow(10, x_len);` and other like it. It should've been `a = x / pow(10, x_len / 2);` – Rafael Adel Aug 22 '16 at 20:56

2 Answers2

2

I found the problem cause. It was because of these lines:

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));

It should be x_len / 2 instead of x_len and the same with y_len. Since it causes the recursion to be infinite.

Rafael Adel
  • 7,673
  • 25
  • 77
  • 118
0

You are using the pow function to do integer powers. It is not an integer function. Code your own pow function that's suitable for your application. For example:

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

Make sure to put an int pow(int, int); at the top.

David Schwartz
  • 179,497
  • 17
  • 214
  • 278