Recently, I have encountered many situations in which I was asked the complexity of std::sqrt() in C++. Since my early cp days, I have known the time complexity of std::sqrt() to be O(sqrt(n)), the reason being this and a few other youtube channels. I was using C++17 at that point.
A friend of mine suggested it to be O(logn) in C++20 after he tested it by printing cout<<sqrtl(N), where N was set as 1e18. The code compiled in 10 ms, giving the correct ans.
Later on, I ran the same code in C++14 in ideone and the code still compiled in 10 ms. This made me really confused...
I would really appreciate if someone helps me with this. I looked it up in cpp-reference but couldn't find it.
Ah, you made the rookie mistake of believing that everything on GFG is correct. There's a ton of articles on problems on GFG that contain mistakes or the solutions are simply just wrong.
I don't know how the
std::sqrtis implemented, but as you saw, it runs very quickly. Implementing a square root function can easily be done with binary search — it wouldn't make any sense for the c++ library implementation to be slower.Yeah I always implement with binary search. Thanks for clarifying.
There are several methods for computing square roots, using convergence of series, iterative methods, etc. This is from Wiki. Using a fixed number of iterations, you can get a better performance than log N. Someone told me once that C++ uses a table with precomputed values that make it faster.
Okay but how big would that table be? I mean sqrtl supports values upto 1e18, so I'm not able to understand what we would precompute to construct the answer in O(1).
In these benchmarks, it looks like
std::sqrtis much faster than pretty much everything. In fact, if you look at the assembly, then in almost all cases (after doing some floating point checks),std::sqrtcalls the hardware instructionsqrtsd, and I would expect hardware instructions to be much faster than software implementations.Thanks nor gate ;) :P
Ahahahahaha, then function
pow(2, n)runs in $$$O(2^n)$$$ :Dcorrect me if im wrong, but its intended to be used with floats/doubles, no? there's no way for it to run in logn that way
Apart from some special cases, it is usually implemented as $$$\text{pow}(x, y) = \exp(y \log x)$$$.
C'mon bro, not funny :((..
Newton's method has a quadratic convergence rate which means that the number of accurate digits doubles with every iteration. This implies that for N-bit integers this method requires around log(N) iterations. Obviously std::sqrt might be even faster.