miniluigi's blog

Time Complexity of floor and log2
By miniluigi, history, 8 years ago, In English

When I was coding a solution for 633E, I noticed that using

int log(int x) {
    int ct = 0;
    int k = 1;
    while (k <= x) {
        k *= 2; ct++;
    }
    return ct-1;
}

over floor(log2(x)) allowed my program to run in time. Could someone please explain to me why one is faster than the other? Thanks!

See here for my code and use compare to see that nothing else is different:

log(x): http://mirror.codeforces.com/contest/633/submission/18990265

floor(log2(x)): http://mirror.codeforces.com/contest/633/submission/18990181

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

Comments Comments (9)
| Write comment?
»
8 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

i bet the main reason ur code is faster is because c++ function log2() works with doubles, and ur function log() works with integers only. I just replaced int by double in type that log() returns and in parameter that log() recieves and it caused TL 22.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Huh, OK I guess that makes sense. Thanks for your help!

    → Reply
»
8 years ago, # |
  Vote: I like it +32 Vote: I do not like it

You can make that function run even in O(1) if you use some bit hacks (works only in GCC, 8992243):

int log(int x) {
    return 32 - __builtin_clz(x) - 1;
}
→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Won't the TC be O(lg x) instead of O(1) since , TC of __builtin_clz(x) is lg(x) ?

    → Reply
    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      The implementation of __builtin_clz(x) is based on simple CPU instructions that exist for certain CPU architectures and is incredibly fast, in fact it seems like it is just two Assembly instructions. This makes it faster than even things like multiplication, i.e. it is O(1).

      → Reply
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Here is the implementation of log2 function, it's 200 lines of code. In contrast, your log function compiles into a 4 instruction loop, so it takes 128 instructions in the worst case.

→ Reply
»
8 years ago, # |
← Rev. 3   Vote: I like it -8 Vote: I do not like it

slight modification of BekzhanKassenov's code to cover long long as well

int log(long long x)
{
    return 64 - __builtin_clzll(x) - 1;
}
→ Reply
»
5 weeks ago, # |
  Vote: I like it -8 Vote: I do not like it

easy

→ Reply