njha1999's blog

Loop runs for 10^18 and still executes : Strange Behaviour or am too dumb to understand this?
By njha1999, history, 5 years ago, In English

Either this is something strangely deep or i have to revisit time complexity analysis for a piece of code !!

#include <iostream>
int main()
{
    long long int t=1e18,a=0; 

    while(t--) a++;
    std::cout<<a;
    return 0;
}

This code executes in 15 ms codeforces / codechef ide! How is that even possible?

May be this question is too dumb but any help is appreciated. Thanks!

  • Vote: I like it
  • +5
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Codeforces will compile it with -O2, which means the code will be optimized. This code is so simple that even the compiler will figure out that all this really long while loop does is sets a to $$$10^{18}$$$ and t to 0.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +9 Vote: I do not like it

    Yep, here's the proof — https://godbolt.org/z/d8fo-p

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Thanks for your reply, need to look after these complier flags for now! Will the compiler be able to optimize it if i add branches here and there in the while block, like adding some if statements?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +4 Vote: I do not like it

      Probably not to something that runs in 15ms (or even $$$10^9$$$ seconds), unless these if-statements are very trivial (all clauses are always trivially true or trivially false, for example). It's really hard to automatically optimize programs to constant formulas like that.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Oh! Learnt something new today, though have seen these compiler flags in many snippets earlier but never knew what they actually did Thanks!

        → Reply