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> \n", 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\n", 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)

How exactly do they differ? Try writing a small self-contained program that calls `pow` and `pow_longlong` and shows the results. If the results are small, it's probably a floating-point rounding error; `pow()` takes arguments of type `double` and returns a result of type `double`. — Keith Thompson, Apr 11 '14 at 15:21
If you use `pow` from `math.h`, do you use also include `math.h`, right? — ouah, Apr 11 '14 at 15:22
Please be specific: what input arguments, what discrepancy ? — , Apr 11 '14 at 15:24

Danvil · Answer 1 · 2014-04-12T00:59:42.927

0

pow (see reference) is not defined for integers, but only for floating point numbers. If you call pow with int as an argument the result will be a double.

You can in general not assume that the result of pow will be exactly the same as if you would use pure integer math as in the function pow_longlong.

Citation from wikipedia about double precision floating point numbers:

Between 2^52=4,503,599,627,370,496 and 2^53=9,007,199,254,740,992 the representable numbers are exactly the integers. For the next range, from 2^53 to 2^54, everything is multiplied by 2, so the representable numbers are the even ones, etc.

So you get inaccurate results with pow if the result would be bigger than 2^53.

edited Apr 12 '14 at 00:59

answered Apr 11 '14 at 15:25

Danvil

22,240
19
65
88

Question has the tag C. – Utkan Gezer Apr 11 '14 at 15:30
@ThoAppelsin: Ok, fixed the link. Same argument though. – Danvil Apr 11 '14 at 15:31
Still, unless you get beyond the limits that a `double` can safely represent, you can safely and automatically assume that `pow` and `pow_longlong` will yield the same output for the same input. In this case, however, there are just too many digits to be represented properly with a `double`. I'm speaking for C, don't know about C++ – Utkan Gezer Apr 11 '14 at 15:37
Yes, the point really exactly is the "unless...", which doesn't take place in the answer, making it look like **a** and **b** in `int a = pow( x, y ); int b = pow_longlong( x, y );` could be different from each other for any integer **x** and **y**. That's not correct, as long as **x** and **y** are low enough, and positive. As I said on my previous comment, the "unless..." part plays the key role in this case, which still is just being barely pointed out with this answer, even after the edit. – Utkan Gezer Apr 11 '14 at 21:39

score 0 · Accepted Answer · edited May 23 '17 at 12:15

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\n", 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.

pow() giving wrong result

2 Answers2

Linked