2

My code to compute square root of a number:

class Solution {
public:
    int mySqrt(int x) {
        int result;
        result = exp(log(x)/2);  # Square root of number = antilog(log(number)/2)
        return result;
    }
};

This code fails only when input is x = 2147395600, the expected output is 46340, but my code's output is 46339.

Why did this happen?

Error image: https://ibb.co/8Pg9Lpd (1016 / 1017 test cases passed, my code failed only for input x = 2147395600)

Problem description:

Implement int sqrt(int x).

Compute and return the square root of x, where x is guaranteed to be a non-negative integer.

Since the return type is an integer, the decimal digits are truncated and only the integer part of the result is returned.

Example 1:

Input: 4
Output: 2

Example 2:

Input: 8
Output: 2
Explanation: The square root of 8 is 2.82842..., and since 
             the decimal part is truncated, 2 is returned.
Puneeth G R
  • 111
  • 1
  • 8
  • You're asking too much of *floating point arithmetic* I'm afraid. One quick and dirty solution is to use `std::round` rather than the truncation to `int`. Note that `std::sqrt` is required by IEEE754 to return the best result possible. – Bathsheba Jun 16 '20 at 06:11
  • Double precision floating points carry about 16 significant (decimal) digits. With 16 significant digits `log(2147395600)` ≃ [21.48752159597273](https://www.wolframalpha.com/input/?i=ln%282147395600%29) and `exp(21.48752159597273 / 2)` ≃ [46339.999999999898](https://www.wolframalpha.com/input/?i=e%5E%2821.48752159597273+%2F+2%29) which truncates to `46339`. There is no error in the code, the only mistake is expecting exact results from a floating point calculation. – dxiv Jun 16 '20 at 06:24
  • @Bathsheba If the task is to find the integer part of the square root then rounding won't work. The safe way would be to check the squares of `ceil(result)` and `floor(result)` against `x` in integers and return the first one which is `<= x`. – dxiv Jun 16 '20 at 06:47
  • @dxiv: Yes, that's a good point. Facetiously, the safe way is to use `std::sqrt`, having asserted for IEEE754. – Bathsheba Jun 16 '20 at 06:49

0 Answers0