maybesomeone's blog

Formula for this ?
By maybesomeone, 3 years ago, In English

is there any formula to calculate this in O(1) ?

int N;
cin >> N;

int answer = 0;
while (N > 1) {
    N = sqrt(N);
    answer++;
}

cout << answer;
  • Vote: I like it
  • +12
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it 
#include<bits/stdc++.h>
using namespace std;

int main() {
  int n,ans = 0; cin >> n;
  n = abs(n);
  int f = 32 - __builtin_clz(n);
  while(f > 1) {
    f = (f+1) / 2;
    ans++;
  }
  cout << ans << endl;
}

This one works in O( log(log(n)) )

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

    can you explain this ?

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

      Imagine bit representation of n, let it be n = 16 (in bits 10000), sqrt of 16 is 4 (in bits 100), if n = 25 (11001 in bits) sqrt is 5 (in bits 101), size of bit representation after sqrt is always (bit representation size + 1)/2, we need to make size equal of 1 so number of operations is log(bit representation size of n) because after every sqrt it becomes half of initial size, it's little hard for me to explain, sorry.

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

    Instead of powerOfTwo(n) + 1 you can just write (31 — __builtin_clz(i)), result is the same I guess.

    → Reply
»
3 years ago, # |
← Rev. 3   Vote: I like it +6 Vote: I do not like it
Just output the result of your function for the first few values of n.
Can't you notice a pattern?
Solution
→ Reply