rebel_roar's blog

Which is more efficient in for loop u*u<=n or u<=sqrt(n) ?
By rebel_roar, history, 3 years ago, In English

Can anyone help me, which is more efficient while using in the for loop?

for(u = 2; u <= sqrt(n); u++)

or

for(u = 2; u*u <= n; u++)

Here are my both submission

Using first method — 119098252

Using second method — 119098208

While using the first method i got TLE but the same code using with the second method got Accepted..

I am assuming that method one is calculating sqrt(n) again and again and other one is calculating u*u again and again then why one is got accepted other one is not.

Please tell me the reason behind this?

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

Comments Comments (15)
| Write comment?
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

sqrt may be $$$O(1)$$$ but it has a high constant factor. Computing it once and storing it in a variable lim passes.

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

    If variable ($$$n$$$) might be reduced during the for-loop then 1LL * u * u <= n is somewhat better

    Also for some rare occasions did precision error of sqrt(n) becomes hard to be detected/debugged

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

Indeed, the sqrt function is the culprit: it is a quite slow mathematical function and calculating it many times can easily lead to TLE.

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

Usually try not to use sqrt function unless your u*u is larger than LLONG_MAX(if you use long long int)/INT_MAX(if you use int)....

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

sqrt(n) will not get calcuated repeatedly as n is not changing unlike u changes. Don't know much detail about it, but just heard that if a code is executing repeatedly, the corresponding arthematic operations aren't done if the values aren't changed.

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

    The compiler is only allowed to remove repeated calls to functions with const or pure attribute. But sqrt(n) isn't really pure, because it has side effects (it may modify the global errno variable and/or raise FE_INVALID floating point exceptions).

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

Don't use sqrt(n), it can cause precision errors. (and yeah, it's slow too)

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

    Well, it can, but if we are talking about efficiency, then computing sqrt(n) once is obviously faster than computing u * u n times. GCC (since some version) guarantees to make an optimisation in the case for (int i = 0; i < f(n); i++), so that f(n) computes only once (obviously, only when it succeeds to prove that f(n) does not change during the loop). Clearly, it is not possible to make similar optimization in the case of u * u.

    Btw, u * u is also not fail-safe at all because you can simply overflow. Moreover, it overflows even earlier, than sqrt(n) causes precision errors. So, I think that the most safe and fast way is to handle the case of the perfect square and then use floor(sqrt(n)) (or with sqrtl instead of sqrt).

    But, honestly, I also prefer u * u because it is simply easier to debug when you don't use floats and the difference in speed is usually not important.

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

      GCC (since some version) guarantees to make an optimisation in the case for (int i = 0; i < f(n); i++), so that f(n) computes only once (obviously, only when it succeeds to prove that f(n) does not change during the loop).

      You can verify this yourself if you go to https://codeforces.com/problemset/customtest and try to experiment with the following code:

      #include <iostream>
#include <math.h>

int main()
{
  int n = -1;
  double sqrt_n = sqrt(n);

  errno = 0;
  std::cout << "sqrt_n=" << sqrt_n << "\n";
  std::cout << "sqrt(n)=" << sqrt(n) << "\n";
  std::cout << "errno=" << errno << "\n";
}

      The compiler is not allowed to get rid of the second call to "sqrt(n)" function and replace it by using the already pre-calculated value "sqrt_n". This optimization can't be safely applied, because it would change the user visible program behaviour and the printed errno value would be different.

      But there is a special -ffast-math compiler option (which doesn't seem to be used by the codeforces platform by default), and it may help: https://stackoverflow.com/a/22135559/4882445

      The code for (int i = 0; i < sqrt(n); i++) surely does call the sqrt function again and again on each loop iteration, unless the -ffast-math option is used. This all is very fragile and such code stinks.

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

    So if i calculate sqrt(n) previously and then check in the loop, Is it fine or not?

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

      It's fine for small numbers, but for bigger numbers you can run into precision errors. There are two solutions:

      1. Increment or decrement the answer a few times, because you're guaranteed to be close even if there are precision errors. Something like this:

        long long my_sqrt(long long x) {
    long long y = x;
    if (y*y < x) y++;
    if (y*y > x) y--;
    return y;
}

      2. Just use u*u <= x. This saves a bit of time to implement, and your sanity. But if you need to explicitly calculate the square root, then use the first way.

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

        It's worth to mention that it won't necessarily be fine for small numbers as it does not depend on the magnitude of them.

        "The crux of the problem is that numbers are represented in this format as a whole number times a power of two; rational numbers (such as 0.1, which is 1/10) whose denominator is not a power of two cannot be exactly represented." ref

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

          True, I forgot about that. So something like $$$\sqrt{81}$$$ might get something like $$$8.99999999999993435$$$. So you could probably add an epsilon value, like $$$10^{-9}$$$, but at that point, just do the incrementing thing.

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

            No, this can't happen. Everything will be perfectly fine and accurate as long as the numbers are all integers and smaller than $$$2^{53}$$$.

            But we may run into troubles if we are dealing with rational numbers. We have infinitely repeating digits after dot in a decimal representation for some of them, which makes fractions like $$$1/3 = 0.333...$$$ kinda inconvenient. And $$$1/5$$$ results in infinitely repeating digits after dot in a binary representation too. The floating point numbers are internally stored in a binary format. And a nicely looking floating point constant 0.2 in the source code actually isn't equal to exactly $$$1/5$$$ and won't give us exactly $$$1.0$$$ after multiplying by $$$5$$$.

            → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Maybe you can try this: 

for(u=2, U=sqrt(n); u<=U; u++)
→ Reply