tag:blogger.com,1999:blog-1953325079793449971.post6531120122753136076..comments2024-09-20T21:17:15.980+02:00Comments on Algorithms Weekly by Petr Mitrichev: Binary search and eps in comparisonsPetr Mitrichevhttp://www.blogger.com/profile/00138130656174416711noreply@blogger.comBlogger8125tag:blogger.com,1999:blog-1953325079793449971.post-70197606232015604142013-05-10T11:37:36.625+02:002013-05-10T11:37:36.625+02:00Because of the way floating point works there will...Because of the way floating point works there will be no information loss. That page is referring to integer overflow, which works differently to exponential overflow.Robin Leenoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-4936468058426000252013-05-10T11:37:32.630+02:002013-05-10T11:37:32.630+02:00one more concern is about error that might happen ...one more concern is about error that might happen while executing "double middle = (left + right) / 2;" . plz refer this <br /> http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.htmlBandishankarnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-27747880411681412382013-05-10T11:37:21.643+02:002013-05-10T11:37:21.643+02:00I completely agree that the invariant approach is ...I completely agree that the invariant approach is the only way to approach binary search logically. However, I believe I did use exactly this approach - and still failed. In the problem in question, my invariant was "left is bad, right is good". When checking whether middle is good, I've tried to be precise: I've checked that every subset of k cities covers at least k/n fraction of the perimeter, without any eps - exactly so that the comparison is as precise as possible. I've thought that "if for some value of middle the total length is exactly k/n, then for slightly larger value it will be more than k/n, and thus the comparison without eps will produce exact results". And this last statement contained a tiny mistake - it doesn't work for k=n (and only for that case).<br /><br />If you could explain how you expected me to apply the approach to this problem more cleanly, that would be great!Petrhttp://petr-mitrichev.blogspot.com/noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-43496735782208085682013-05-10T11:37:19.602+02:002013-05-10T11:37:19.602+02:00Well, blindly adding epsilons will also fail in ot...Well, blindly adding epsilons will also fail in other situations. The thing that is actually important is keeping a clear invariant: always state a condition such that everything to the left of the place you seek is "good" and everything to the right is "bad", and then maintain the invariant "left is good, right is bad". Then, what you are testing inside the bsearch is the question "is middle good or bad"? And you need to make this test as precise as you can.misofhttp://misof.myopenid.com/noreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-23682581200563807382013-05-10T11:37:13.574+02:002013-05-10T11:37:13.574+02:00Thanks for (yet another) nice lesson. I guess when...Thanks for (yet another) nice lesson. I guess when you are pressured to perform at a very high speed (in order to grab the 1st place), you are bound to make one or two mistakes occasionally. I'm still expecting the day you will beat that "magic" 4000 mark =)Pedro Osórionoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-82377503280045473342013-05-10T11:37:12.602+02:002013-05-10T11:37:12.602+02:001) It is not precise comparison vs. approximate co...1) It is not precise comparison vs. approximate comparison; it is fixed number of comparisons or comparison until the error is is small enough.<br /><br />2) It is f(x) <= eps. You cannot generally solve f(x) = C exactly with a computer.Testhttp://peteriserins.comnoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-2162942325290004862013-05-10T11:37:11.750+02:002013-05-10T11:37:11.750+02:00How precise comparison is worse than approximate o...How precise comparison is worse than approximate one in a presence of plateau?<br /><br />Isn't second snipped just solving equation f(x) = eps instead of f(x) = 0?Vlad Shcherbinanoreply@blogger.comtag:blogger.com,1999:blog-1953325079793449971.post-52779158809061825422013-05-10T11:35:33.350+02:002013-05-10T11:35:33.350+02:00Well, technically you're right, but practicall...Well, technically you're right, but practically what happens is that the first snippet solves f(x) = 0 by finding _any_ such x, while in reality we usually need _largest_ such x (in other words, the boundary between f(x) <= 0 and f(x) > 0). If f(x) = 0 between -infinity and some point x0, and f(x) > 0 when x > x0 (this is what happened in the SRM), then this method may return any value between -infinity and x0 instead of x0 (in the SRM it was -infinity :)). Solving f(x) = eps provides a good approximation to largest x such that f(x) = 0.Petrhttp://petr-mitrichev.blogspot.com/noreply@blogger.com