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

Автор rebel_roar, история, 3 года назад, По-английски

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?

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

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

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

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится -24 Проголосовать: не нравится

    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

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

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

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)....

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

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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).

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

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

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

    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.

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

      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://mirror.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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

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

        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

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

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

            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$$$.

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +12 Проголосовать: не нравится

Maybe you can try this:

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