Error in C track - Grains

Exercism Bugs & Feature Requests
1

Consider Thena's solution for Grains in C on Exercism and anguish's solution for Grains in C on Exercism
Analytically, the sum should be a odd number; because the 1st square have 1 grain, and every square after it have a even number of grains, the whole board should have a odd number of grains. But due to the test runner running it in uint64_t, the number cannot be accurately transcribed; thus leading to the result that both passes.

#include <stdio.h>
#include <stdint.h>
#include <math.h>

int main(){

    uint64_t overlimit = pow(2, 64);
    uint64_t underlimit = pow(2, 64) - 1;
    uint64_t requirement = 18446744073709551615ull;
    printf("overlimit: %llu\n", overlimit);
    printf("underlimit: %llu\n", underlimit);
    printf("requirement: %llu\n", requirement);
    printf("Press any key to continue...\n");
    
    char userInput;
    scanf("%c", &userInput);
    
    return 0;
}

overlimit: 18446744073709551615
underlimit: 18446744073709551615
requirement: 18446744073709551615
Press any key to continue...

#include <stdio.h>
#include <stdint.h>
#include <math.h>

int main(){

    uint64_t overlimit = pow(2, 64);
    uint64_t underlimit = pow(2, 64) - 1;
    uint64_t requirement = 18446744073709551615ull;
    
    if(overlimit == requirement){
        printf("Overlimit is equal to requirement\n");
    }
    else{
        printf("Overlimit is not equal to requirement\n");
    }
    if(underlimit == requirement){
        printf("Underlimit is equal to requirement\n");
    }
    else{
        printf("Underlimit is not equal to requirement\n");
    }

    printf("Press any key to continue...\n");
    
    char userInput;
    scanf("%c", &userInput);
    
    return 0;
}

Overlimit is equal to requirement
Underlimit is equal to requirement
Press any key to continue...

the bug stems from the grains amount being pow (2, 64) -1, and as it is the limit of uint64_t the test runner cannot distinguish between the two

TEST_ASSERT_EQUAL_UINT64(18446744073709551615ull, total());
1 Like
2

I think there is certainly room for critique for the solution which takes advantage of the architectural limitation of a uint_64, but I don’t think this is a bug (meaning it either returns a wrong answer which is accepted as correct, or a correct answer which is rejected as wrong).

This is defined in the c standard as well: c++ - Is (uint64_t)-1 guaranteed to yield 0xffffffffffffffff? - Stack Overflow

Your test is also subject to precision loss/overflow since pow as defined in math.h return a double float, not an integer.

1 Like
3

I’m pretty sure the observed behaviour is due to the fact that pow operates on double-precision floating point numbers (its signature is double pow(double x, double y);). A double can only represent consecutive integers up/down to \pm2^{53} (see types - Biggest integer that can be stored in a double - Stack Overflow), so some rounding occurs that results in pow(2, 64) and pow(2, 64) - 1 having identical representations in memory. When these identical doubles are cast to uint64_ts, the results are also identical.

4

@kruschk is correct, the values of the expressions pow(2, 64) and pow(2, 64) - 1 are identical (at least on all modern platforms that implement double as IEEE-754 binary64.

For a demonstration you can visit this simulator by Edmund Weitz and see what happens when you subtract 1.0 from 18446744073709551616.0.

There is one more guest to the party, undefined behavior (UB).

The conversion from a floating point type to an integer type invokes undefined behavior if the integer type cannot represent the value after the truncation of the fractional part (see cppreference).

The mathematically correct value of pow(2, 64) is 0x1 0000 0000 0000 0000, a 65-bit value that uint64_t cannot represent, so the assignment to overlimit invokes undefined behavior. With UB anything can happen (e.g. the often quoted “nasal demons” or “pregnant cats”).

That leads to the curious situation that these two functions can return different values:

uint64_t func1(void) {
    return (uint64_t)pow(2, 64);
}
uint64_t func2(void) {
    double result = pow(2, 64);
    return (uint64_t)result;
}

When compiled with Clang I get 9223372036854775808 from both functions, with GCC I get 18446744073709551615 from func1() and 0 from func2() (see the compiler explorer).

5

There is one more guest to the party, undefined behavior (UB).

That’s an excellent point; thanks for bringing it up! I wrote code very similar to your func1 and func2 and noticed the same behaviour that you described (GCC), but I couldn’t figure out what was going on and gave up. The fact that the cast invokes UB explains it! :slight_smile: