Блог пользователя njha1999

Loop runs for 10^18 and still executes : Strange Behaviour or am too dumb to understand this?
Автор njha1999, история, 5 лет назад, По-английски

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!

  • Проголосовать: нравится
  • +5
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +35 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +9 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    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?

    → Ответить
    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +4 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +1 Проголосовать: не нравится

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

        → Ответить