Code producing different output on different compilers

Question

I was solving Quasi-Binary problem (doesn't matter) on Codeforces and this is my submission. This is the code I have produced :

#include <iostream>
#include <cmath>

using namespace std;

int quasi_binary(int num, int tens)
{
    int res,digit;

    if(num == 0)
    {
        return 0;
    }

    digit = num%10;
    num = num/10;

    res = quasi_binary(num, tens+1);

    if(digit)
    {
        cout << 1;
        return ((digit-1)*pow(10,tens)+res);
    }
    else
    {
        cout << 0;
        return res;
    }
}

int main()
{
    int n,k=-1,temp,digit;
    cin >> n;

    //this loop calculates the value of k,as it needs to be printed first
    temp=n;
    while(temp)
    {
        digit = temp%10;
        temp = temp/10;

        if(digit>k)
            k=digit;
    }
    cout << k << endl;

    //print those k quasi-numbers
    while(n)
    {
        n = quasi_binary(n,0);
        cout << " ";
    }
    return 0;
}

I don't see any statement that can produce undefined behaviour on different compilers. I used proper brackets at proper places, as well to avoid ambiguity. Still getting undefined behaviour. Can anyone please help to locate the statement/instruction which is generating the undefined behaviour.

Input

Output (online judge) - incorrect

5
111 101 101 11 11 11 11 11 11 11 11 11

Output (on my 64-bit PC with gcc) - correct

5
111 101 101 101 1

`pow(10,tens)` -- Do not use `pow` if you have integer exponents. There is [no guarantee that pow will give you the correct results](http://stackoverflow.com/questions/25678481/why-pown-2-return-24-when-n-5/25678721#25678721). — PaulMcKenzie, Jul 24 '16 at 21:20
I don't think it has to do with architecture or compilers. Use the complete conditional when testing if a number is greater than zero. I.e. use `if (num > 0)` rather than `if(num)`. Not sure if this is the problem — smac89, Jul 24 '16 at 21:22
*I don't see any statement that can produce undefined behaviour on different compilers* -- But you do have statements that produce floating point values (`pow()`), thus your program is not guaranteed to produce the same results. — PaulMcKenzie, Jul 24 '16 at 21:24
PaulMcKenzie is right. Make sure the parameters you use within `pow()` are `double`, because the parameters in `pow()` are both doubles. Try changing `tens` to `double`. — , Jul 24 '16 at 22:12

Cheers and hth. - Alf · Answer 1 · 2016-07-25T01:12:55.417

To avoid rounding down to 1 less than math result, replace pow(10, tens) with int( 0.5 + pow( 10, tens ) ).

Or, write your own integer power function.

E.g.

using Int_noneg = int;     // "Not negative"

auto int_pow( Int_noneg const x, Int_noneg const exponent )
    -> int
{
    Int_noneg   reverse_bits = 0;
    Int_noneg   n_exponent_bits = 0;
    for( Int_noneg i = exponent; i != 0; i /= 2 )
    {
        reverse_bits = 2*reverse_bits + i%2;
        ++n_exponent_bits;
    }

    Int_noneg   result = 1;
    for( Int_noneg i = 0; i < n_exponent_bits; ++i, reverse_bits /= 2 )
    {
        result *= result;
        if( reverse_bits % 2 != 0 ) { result *= x; }
    }
    return result;
};

score 0 · Answer 2 · answered Jul 24 '16 at 23:45

Before going into my solution, I took one for the team and went to the site you referenced in your post (didn't need to do this). I submitted your original code you posted, and yes, you get the error. Thus in the SO comment that I linked to in the main comment section, the pow function indeed causes issues due to floating point and the truncation issue.

To get around this, there are a few things you can do, mostly outlined in the other answer(s) given. But I will give my solution:

unsigned long powTable[] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 
                             10000000, 100000000, 1000000000 };

//...
return ((digit-1)*powTable[tens]+res);

Instead of calling the pow function, a simple lookup table with the powers of 10 is declared, and then the tens is used as an index into the table.

Live Example

Uhm, I don't see how that's an improvement over `int( 0.5 + pow( 10, tens ) )`, either for needed-only-once code or (especially) as more general reusable code? — Cheers and hth. - Alf, Jul 25 '16 at 00:06
This is an alternative solution that doesn't use `pow`, but a lookup table. Never claimed it was "better", just an alternative. — PaulMcKenzie, Jul 25 '16 at 00:15

Code producing different output on different compilers

2 Answers2