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. — PaulMcKenzie
– PaulMcKenzie, Commented Jul 24, 2016 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
– smac89, Commented Jul 24, 2016 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
– PaulMcKenzie, Commented Jul 24, 2016 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. — user6054931
– user6054931, Commented Jul 24, 2016 at 22:12

Cheers and hth. - Alf · Accepted Answer · 2016-07-25 01:12:55Z

5

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;
};

edited Jul 25, 2016 at 1:12

answered Jul 24, 2016 at 21:22

Cheers and hth. - Alf

146k15 gold badges218 silver badges342 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

PaulMcKenzie · Accepted Answer · 2016-07-24 23:45:31Z

0

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

answered Jul 24, 2016 at 23:45

PaulMcKenzie

35.6k4 gold badges26 silver badges49 bronze badges

2 Comments

Cheers and hth. - Alf Over a year ago

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?

PaulMcKenzie Over a year ago

This is an alternative solution that doesn't use pow, but a lookup table. Never claimed it was "better", just an alternative.

Collectives™ on Stack Overflow

Code producing different output on different compilers

2 Answers 2

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related