c - <math.h> pow() giving wrong result

Question

This is from google's code jam, practice problem "All your base".

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
long long pow_longlong(int digit, int raiseto)
{
    if (raiseto == 0) return 1;
    else return digit * pow_longlong(digit, raiseto - 1);
}
long long base10_with_map(int base, char* instr, char* digits)
{
    if (base < 2) base = 2;
    long long result = 0;
    int len = strlen(instr);
    int i = 0;
    while (len--)
        result += digits[instr[len]] * pow_longlong(base, i++);
    return result;
}
long long test(char* in)
{
    char appear[256];
    int i;
    int len = strlen(in);
    int hold = 0;
    for (i = 0; i < 256; i++) appear[i] = 'xFF';
    for (i = 0; i < len; i++)
        if (appear[in[i]] == 'xFF')
        {
            if (hold == 0) { appear[in[i]] = 1; hold++; }
            else if (hold == 1) { appear[in[i]] = 0; hold++; }
            else appear[in[i]] = hold++;
        }
    return base10_with_map(hold, in, appear);
}
int main(int argc, char* argv[])
{
    if (argc < 2)
    {
        printf("Usage: %s <input-file> 
", argv[0]); return 1;
    }
    char buf[100];
    int a, i;
    FILE* f = fopen(argv[1], "r");
    fscanf(f, "%d", &a);
    long long result;
    for (i = 1; i <= a; i++)
    {
        fscanf(f, "%s", buf);
        result = test(buf);
        printf("Case #%d: %lld
", i, result);
    }
    return 0;
}

This works as intended and produces correct result to the problem. But if I replace my own pow_longlong() with pow() from math.h some calculations differ.

What is the reason to this? Just curious.

Edits: - No overflow, plain long is enough to store the values, long long is just overkill - Of course I include math.h - In example: test("wontyouplaywithme") with pow_longlong returns 674293938766347782 (right) and with math.h 674293938766347904 (wrong)

Answer 1

Sorry that I won't go through your example and your intermediary function; the issue you're having occurs due to double being insufficient, not the long long. It is just that the number grows too large, causing it to require more and more precision towards the end, more than double can safely represent.

Here, try this really simple programme out, or just trust in the output I append to it to see what I mean:

#include <stdio.h>

int main( ){

    double a;
    long long b;

    a = 674293938766347782.0;
    b = a;

    printf( "%f
", a );
    printf( "%lld", b );

    getchar( );
    return 0;
}

/*
    Output:
    674293938766347780.000000
    674293938766347776
*/

You see, the double may have 8 bytes, just as much as the long long has, but it is designed so that it would also be able to hold non-integral values, which makes it less precise than long long can get in some cases like this one.

I don't know the exact specifics, but here, in MSDN it is said that its representation range is from -1.7e308 to +1.7e308 with (probably just on average) 15 digit precision.

So, if you are going to work with positive integers only, stick with your function. If you want to have an optimized version, check this one out: https://stackoverflow.com/a/101613/2736228

It makes use of the fact that, for example, while calculating x to the power 8, you can get away with 3 operations:

...
    result = x * x;             // x^2
    result = result * result;   // (x^2)^2 = x^4
    result = result * result;   // (x^4)^2 = x^8
...

Instead of dealing with 7 operations, multiplying them one by one.