my face when I use binary search to find the roots of a quadratic equation
my face when I use binary search to find the roots of a quadratic equation
hi I know this is a year old, but I solved it and used a custom implementation of binary search to solve this.
interestingly enough, in python at least, it is almost as performant as the quadratic equation for solving this lol (43.7 microseconds vs 64.9 microseconds) but now that I realized it is a simple parabola, you can just get the maximum after getting the minimum time and practically matches the quadratic equation performance. lol
I know the math is faster as search space grows but I still think its interesting how performant this was.
TLDR: I'm so data structures and programming pilled that I forgot basic algebra.
Hehe. Nice observation!
Although, isn't this basically Newton's method of square roots? I don't recall how floating point implementations usually do it, but it's not too surprising that the performance is similar to the algebraic approach.
haha nice. So the CPython's
math.sqrtjust hands it off to the C/POSIX implementation of sqrt and even that could possibly be handing it off to the cpu for calculating the square root as fast as possible. my dumb binary search written in complete python is literally matching the speed of some of the most performant methods of doing square root.but you are right, my method of using a binary search isn't outlandish at all! wow https://stackoverflow.com/questions/3581528/how-is-the-square-root-function-implemented
infact it does seem similar to newton's method. I just bypassed the entire calculating square root to get the root value and just simply searched for the first single digit integer that will contain the root(ie first and last valid positions)
however as the comments to that solution alluded to, when it comes to precision, this method is not worth it. While for us, an approximation that is accurate enough to the single digits is really dam good and might be faster.(while it is not worth to implement for the general sqrt function, unless you know it is needed for extremely low precision tasks or as a challenge)
I sat here thinking I was being dumb for reinventing the wheel lmao