CODEWITHSUNDEEP
csegmentation-fault
rubik
rubik

Reputation: 9104

C segfault using long integers

I don't understand why this code compiles and then segfaults:

#include <stdio.h>
#include <stdlib.h>

unsigned long int gcd(unsigned long int, unsigned long int);
unsigned long int lcm(unsigned long int, unsigned long int);

int main(int argc, char *argv[]) {
    int i;
    unsigned long int n = 1L;
    for (i = 2; i < 21; i++) {
        n = lcm(n, i);
    }
    printf("%ld\n", n);
    return 0;
}

unsigned long int gcd(unsigned long int a, unsigned long int b) {
    if (a == b) return a;
    if (a > b) return gcd(a - b, b);
    return gcd(a, b - a);
}

unsigned long int lcm(unsigned long int a, unsigned long int b) {
    return abs(a * b) / gcd(a, b);
}

Are those unsigned longs even necessary? I also noted that if I change that 21 to a 18 it gives the correct result. The code is meant to find the LCM of all the numbers from 1 to 20.

Running it in gdb gives:

Program received signal SIGSEGV, Segmentation fault.
0x0000000000400643 in gcd (a=7536618, b=18) at p5.c:19
19    if (a > b) return gcd(a - b, b);

Upvotes: 1

Views: 417

Answers (2)

user1084944
user1084944

Reputation:

Due to how the stack and how they work, there's a limit on how deep function calls can be nested, depending on how much local state they keep.

For extremely imbalanced arguments, implementing gcd by repeated subtraction requires a lot of iterations, and so your recursion goes way to deep. You need to either change the implementation (e.g. make it iterative), or change the algorithm (e.g. compute remainders instead of differences).

You could increase the stack size, but that is wasteful of memory and the larger size will run eventually run out too with larger inputs.

Upvotes: 1

Blindy
Blindy

Reputation: 67417

You're overflowing the stack. Which is a shame, because that should be easily optimized as tail recursion, full recursion is extremely overkill for this. Using the proper optimization levels in any modern compiler (cl, gcc, icc) should get rid of the segfault.

Luckily writing this iteratively is trivial as hell:

unsigned long gcd(unsigned long a, unsigned long b) 
{ 
  while(a != b)
    if(a > b)
       a -= b;
    else 
       b -= a;

  return a;
}

Upvotes: 2

Related Questions