nik1996's blog

By nik1996, history, 6 years ago, In English

Hi all,

Recently I was solving problem Sad Powers. In the editorial of the problem it is mentioned that sqrt() function of c++ has some precision issues. On using the function in my problem on some value gives me wrong answer. After looking others solution I observed that some have used additional checks. e.g. If square root of value x is required then many solutions have checked for both x and (x-1) /(x+1). I could not understand why that additional check is required.

Can anybody please tell why this additional check is required or what are the issues with sqrt() function?

Thanks!!

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

| Write comment?
»
6 years ago, # |
Rev. 3   Vote: I like it +2 Vote: I do not like it

Remember that sqrt() has 4 type of parameters two of them is sqrt(double x) and sqrt(long double x). If you feed the parameter with long long type, the function will call sqrt(double x). Which means you will losing precision if the long long number > +- 10^14 because of the precision of double type holds.
You want to use the one with long double type as it will hold the precision of long long number AND the floating point (as good as doubles are).
To use it, simply call it by typecast the number to long double such as sqrt(1.0L * x).

You can look at my submission for example (I just recently solved it too).

»
6 years ago, # |
Rev. 2   Vote: I like it +10 Vote: I do not like it

Floating points will always have precision errors — avoid them if you can.

E.g instead of ceil(n/k)

something like (n%k==0? n/k : n/k+1 )

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

    Assuming that n and k are integers, I think (n+k-1)/k is more common.

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

      It may lead to overflow when n and k are big integers.

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

    That is ceil not floor.

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

      this is what happens when you type things on the phone

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

    ceil(1.0*n / k), will give correct result.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

C++ has a builtin sqrtl that is much more precise than sqrt.

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Use sqrtl(),it is more precise.