Floating point exception (signal SIGFPE) | Together C & C++ | Page 1

rapid sandal Aug 25, 2023, 4:52 AM

#

Why does my program returns an error when encountered with large value like n = 4100 and k = 3? Im assuming its because of integer overflow but the solution given (which uses int as well) works fine. How can I fix this issue?

Expected:

Enter n and k: 4100 3
4100 choose 3 = 11478429700

Actual result:

Floating point exception (core dumped)

My code:

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

void exit_if(int condition, char *err);
int n_choose_k(int n, int k);
int factorial(int x);

int
main(int argc, char *argv[]) {
    int n, k;
    
    // read the values
    printf("Enter n and k: ");
    exit_if(scanf("%d %d", &n, &k) != 2, "scanf failed to read values\n");
    
    // scaffolding for n_choose_k
    printf("%d choose %d = %d\n", n, k, n_choose_k(n, k));
    
    return EXIT_SUCCESS;
}

void
exit_if(int condition, char *err) {
    if (condition) {
        printf("%s", err);
        exit(EXIT_FAILURE);
    }
}

// to calculate the combination
int 
n_choose_k(int n, int k) {
    int numer, denom;
    
    numer = factorial(n);
    denom = factorial(n - k) * factorial (k);
    
    return numer / denom;
}

// to calculate the factorial (helper fn for combination)
int
factorial(int x) {
    exit_if(x < 0, "factorial of a negative integer is not defined\n");
    
    int ans = 1;
    for (int i = 2; i <= x; i++)
        ans *= i;
    return ans;
}

void bisonBOT Aug 25, 2023, 4:52 AM

#

When your question is answered use !solved to mark the question as resolved.

Remember to ask specific questions, provide necessary details, and reduce your question to its simplest form. For tips on how to ask a good question run !howto ask.

rapid sandal Aug 25, 2023, 4:52 AM

#

Solution:

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

/* function prototypes */

int n_choose_k(int n, int k);
int factorial(int n);
void exit_if(int condition, char *err);
int int_safe_multiply(int x, int y);

int
main(int argc, char *argv[]) {

    /* simple scaffolding */
    printf("Enter n and k: ");
    int n, k;
    exit_if(scanf("%d%d", &n, &k) != 2, "Error: Invalid input\n");

    /* now call the function */
    printf("%d choose %d = %d\n", n, k, n_choose_k(n, k));

    return 0;
}

/* a useful helper function, this helps the n_choose_k function in modularity.
 * note, factorial is a great simple function to practice recursion.
 */
int
factorial(int n) {
    /* This function assumes we are calculating a positive factorial. */
    exit_if(n < 0, "Error: Factorial must be positive");

    int fact = 1;
    for (int i = 2; i <= n; i++) {
        /* need to be careful, as it is easy to overflow int arithmetic here */
        fact = int_safe_multiply(fact, i);
    }
    return fact;
}

/* calculates and returns n choose k */
int
n_choose_k(int n, int k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

// Helper functions for error handling...

// exits if condition is true, printing message given by err (ex5-03)
void
exit_if(int condition, char *err) {
    if (condition) {
        printf("%s", err);
        exit(EXIT_FAILURE);
    }
}

// performs x * y if it is safe to do so, otherwise exits with error (ex5-03)
int
int_safe_multiply(int x, int y) {
    int result = x * y;
    // test overflow by checking that x * y = result via division.
    exit_if(y != 0 && x != result / y,
            "Error: Integer overflow when attempting multiplication\n");
    return result;
}

fathom mural Aug 25, 2023, 11:58 AM

#

rapid sandal Why does my program returns an error when encountered with large value like `n =...

Expected:
Enter n and k: 4100 3
4100 choose 3 = 11478429700
I doubt that was expected because that's literally bigger than the biggest possible integer value, even if you used unsigned int.

What I got from your solution code for the input 4100 3 was either Enter n and k: Error: Integer overflow when attempting multiplication with -O0 or Program terminated with signal: SIGFPE for optimization levels 1, 2 and 3.

Explanation of the SIGFPE signal:

Macro: int SIGFPE

The SIGFPE signal reports a fatal arithmetic error. Although the name is derived from “floating-point exception”, this signal actually covers all arithmetic errors, including division by zero and overflow. If a program stores integer data in a location which is then used in a floating-point operation, this often causes an “invalid operation” exception, because the processor cannot recognize the data as a floating-point number.

Actual floating-point exceptions are a complicated subject because there are many types of exceptions with subtly different meanings, and the SIGFPE signal doesn’t distinguish between them. The IEEE Standard for Binary Floating-Point Arithmetic (ANSI/IEEE Std 754-1985 and ANSI/IEEE Std 854-1987) defines various floating-point exceptions and requires conforming computer systems to report their occurrences. However, this standard does not specify how the exceptions are reported, or what kinds of handling and control the operating system can offer to the programmer.

The major and really only difference between the two codes is that you use the naive factorial approach, while the "solution" uses a safer way to multiply numbers. But yeah, neither program really works.

rapid sandal Aug 25, 2023, 4:23 PM

#

fathom mural > Expected: > Enter n and k: 4100 3 > 4100 choose 3 = 11478429700 I doubt that w...

Wait but the solution works tho

#

4100 and 3 is one of the test case

#

;compile C

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

/* function prototypes */

int n_choose_k(int n, int k);
int factorial(int n);
void exit_if(int condition, char *err);
int int_safe_multiply(int x, int y);

int
main(int argc, char *argv[]) {

    /* simple scaffolding */
    printf("Enter n and k: ");
    int n = 4100, k = 3;

    /* now call the function */
    printf("%d choose %d = %d\n", n, k, n_choose_k(n, k));

    return 0;
}

/* a useful helper function, this helps the n_choose_k function in modularity.
 * note, factorial is a great simple function to practice recursion.
 */
int
factorial(int n) {
    /* This function assumes we are calculating a positive factorial. */
    exit_if(n < 0, "Error: Factorial must be positive");

    int fact = 1;
    for (int i = 2; i <= n; i++) {
        /* need to be careful, as it is easy to overflow int arithmetic here */
        fact = int_safe_multiply(fact, i);
    }
    return fact;
}

/* calculates and returns n choose k */
int
n_choose_k(int n, int k) {
    return factorial(n) / (factorial(k) * factorial(n - k));
}

// Helper functions for error handling...

// exits if condition is true, printing message given by err (ex5-03)
void
exit_if(int condition, char *err) {
    if (condition) {
        printf("%s", err);
        exit(EXIT_FAILURE);
    }
}

// performs x * y if it is safe to do so, otherwise exits with error (ex5-03)
int
int_safe_multiply(int x, int y) {
    int result = x * y;
    // test overflow by checking that x * y = result via division.
    exit_if(y != 0 && x != result / y,
            "Error: Integer overflow when attempting multiplication\n");
    return result;
}

fast topazBOT Aug 25, 2023, 4:26 PM

#

Program Output

Enter n and k: Error: Integer overflow when attempting multiplication

rapid sandal Aug 25, 2023, 4:26 PM

#

Hmm what

#

It works on Unix

#

4100 choose 3 = 11478429700

#

Is the output

fathom mural Aug 25, 2023, 4:54 PM

#

rapid sandal 4100 choose 3 = 11478429700

What does sizeof(int) tell you on Linux?
If it tells you 8 then I'm down to believe you, but the maximum value a 4 byte signed integer can have is somewhere around 2.1 billion.
11,478,429,700 is too big by a factor of 5 or so.

fathom mural Aug 25, 2023, 4:55 PM

#

rapid sandal ;compile C ```c #include <limits.h> #include <stdio.h> #include <stdlib.h> /* ...

;compile -O1

fast topazBOT Aug 25, 2023, 4:55 PM

#

Compiler Output

Program terminated with signal: SIGFPE

rapid sandal Aug 25, 2023, 4:59 PM

#

fathom mural What does `sizeof(int)` tell you on Linux? If it tells you `8` then I'm down to ...

It’s on a website

#

they run the code on website

#

my solution doesn’t work but the actual solution work for some reason

#

it’s Unix based as well I believe

fathom mural Aug 25, 2023, 5:01 PM

#

rapid sandal my solution doesn’t work but the actual solution work for some reason

The actual solution doesn't work either.
Run it with -O1, -O2 or -O3 and it won't work in any scenario

rapid sandal Aug 25, 2023, 5:01 PM

#

I’ll take a ss tmr

fathom mural Aug 25, 2023, 5:01 PM

#

Compiler optimizations (besides maybe -O3) should not break the code

rapid sandal Aug 25, 2023, 5:01 PM

#

sorry I’m typing oh my phone

fathom mural Aug 25, 2023, 5:02 PM

#

rapid sandal I’ll take a ss tmr

You'll take ass tomorrow?

rapid sandal Aug 25, 2023, 5:02 PM

#

fathom mural You'll take ass tomorrow?

Screenshot

fathom mural Aug 25, 2023, 5:02 PM

#

aaah

rapid sandal Aug 26, 2023, 2:59 AM

#

#

oops my bad there were 2 solu

#

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

/* function prototypes */

double n_choose_k(int n, int k);

int
main(int argc, char *argv[]) {

    /* simple scaffolding */
    printf("Enter n and k: ");
    int n, k;
    if (scanf("%d%d", &n, &k) != 2) {
        printf("Error: Invalid input\n");
        exit(EXIT_FAILURE);
    }

    /* now call the function */
    printf("%d choose %d = %.0lf\n", n, k, n_choose_k(n, k));

    return 0;
}

/* calculates and returns n choose k
 * uses multiplicative formula to calculate, which works for n > 12
 * https://en.wikipedia.org/wiki/Binomial_coefficient#Multiplicative_formula */
double
n_choose_k(int n, int k) {
    double result = 1;
    for (int i = 1; i <= k; i++) {
        result *= (n + 1 - i) / (double) i;
    }
    return result;
}```

#

this works

rapid sandal Aug 26, 2023, 3:18 AM

#

waitt is it cuz they use double

fathom mural Aug 26, 2023, 1:27 PM

#

rapid sandal waitt is it cuz they use double

yes...
double can represent values with up to 300 zeros (max value is somewhere around 1.7*10³⁰⁸)

rapid sandal Aug 27, 2023, 7:45 AM

#

!solved

#Floating point exception (signal SIGFPE)