3
\$\begingroup\$

My friend and I are into competitive programming and we wrote two very similar programs for a problem. His got accepted with a runtime of 0.6 s while mine didn't get accepted even after 3 s.

I was hoping somebody could explain to me as to why the addition of one function slowed down my code so much.

Both programs produce the correct output. No issues on that front.

The Question: Given A, the initial value of a Collatz sequence, and some limit L, count the number of terms until either 1 is reached or L is exceeded. A and L are both smaller than 231.

His Code

#include<iostream>

using namespace std;

int main(){
    long long A,L;
    int cont,caso=1;

    while(1){
        cin>>A>>L;
        if(A<0 && L<0) break;

        cout<<"Case "<<caso<<": A = "<<A<<", limit = "<<L<<", number of terms = ";
        caso++;

        cont=0;

        while(A<=L && A!=1){
            if(A%2==0) A/=2;
            else A=3*A+1;

            cont++;
        }

        if(A==1) cont++;

        cout<<cont<<endl;
    }

    return 0;
}

My Code

#include<iostream>

using namespace std;

bool even(int a)
{
    if(a%2==0)
        return true;
    else
        return false;
}

int main()
{
    int n=0;
    while(1)
    {
        long long int a, limit;
        cin>>a>>limit;
        if((a==-1) && (limit==-1))
            break;
        cout<<"Case "<<n<<": A = "<<a<<", limit = "<<limit<<", number of terms = ";
        int val=a;
        int count=0;
        while((val<=limit) && (val!=1))
        {
            if(even(val))
                val/=2;
            else
                val=(val*3) + 1;
            count++;
        }
        if(a==1)
            count++;
        cout<<count<<endl;
    }
    return 0;
}
\$\endgroup\$
  • 1
    \$\begingroup\$ did you both compile with optimizations enabled? \$\endgroup\$ – ratchet freak Aug 21 '17 at 15:33
4
\$\begingroup\$

Overflow Bug

The reason your program is timing out is because your variable val is defined as an int instead of a long long. Because of this, val can become negative during the line val=(val*3) + 1, which leads to an infinite loop. You should change the type of val to long long. If you want to test the infinite loop yourself, try this test case and see what happens:

113383 2147483647

Output Bug

Your program has two output related errors:

  1. You should initialize n=1 instead of n=0.
  2. Your code is missing the line n++.

The above two problems mean that your program is outputting something like:

Case 0: A = 100, limit = 100000, number of terms = 25
Case 0: A = 101, limit = 100000, number of terms = 25

instead of the correct format of:

Case 1: A = 100, limit = 100000, number of terms = 25
Case 2: A = 101, limit = 100000, number of terms = 25
\$\endgroup\$
  • \$\begingroup\$ I had corrected the overflow bug before submitting, but still it showed a TLE error. I am guessing the reason is different. \$\endgroup\$ – Karan Singh Aug 23 '17 at 21:15
  • \$\begingroup\$ @KaranSingh I don't know what you submitted, so I can't tell you where the TLE is coming from. All I know is that in the code you posted, the overflow causes a TLE. Are you sure you fixed the overflow in the correct way? To check whether even() is the problem, you could inline it just like your friend's code and see if it makes any difference. \$\endgroup\$ – JS1 Aug 23 '17 at 23:14
0
\$\begingroup\$

This:

bool even(int a)
{
    if(a%2==0)
        return true;
    else
        return false;
}

If you are compiling without optimisation and with debugging could hurt a lot. depending on your input numbers. You've added a function call and a branch to every time round the loop as well as a narrowing cast (from long long to int).

You'd probably get better results with

inline bool even(long long a)
{
    return a % 2 == 0;
}

as comparison operators have boolean results so there's no need for the if ... return true else return false.

Another thing that could be affecting your speed is if you're compiling 32 bits and your friend is compiling for 64 bits.

Finally - a % 2 has to do a remainder operation if a is signed. If you want a bit of extra speed, make a unsigned then the compiler should just be able to test the lowest bit.

Oh, and never omit the braces after if or else. That way madness lies.

\$\endgroup\$
  • 2
    \$\begingroup\$ inline has no effect whatsoever about whether the compiler will inline a function. It's only a linker directive regarding the One Definition Rule. \$\endgroup\$ – ratchet freak Aug 21 '17 at 15:50
  • \$\begingroup\$ it is a recommendation to the compiler which the compiler might or might not ignore. not knowing which compiler he is using (and having come across those that do pay attention to this) I'd not be too sure. \$\endgroup\$ – Tom Tanner Aug 21 '17 at 16:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.