-
Notifications
You must be signed in to change notification settings - Fork 34
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
2x is not a '99%' approximation for 1/(1-x) - 1/(1+x) around 0 #742
Comments
Hi @dmcooke, thanks for the bug report. You basically figured out yourself why this is happening: Herbie takes the range I'm thinking of fixing this by having a "minimum absolute value" field pop up whenever the input range crosses zero; that way it's at least clear to the user that this question is worth thinking about. We've tried mixing uniform and by-representation sampling in the past, and we've found that it's hard to avoid confusing behavior for, for example, wide ranges. Also thank you for the input and the |
One thing that might be reasonable would be to switch Herbie's semantics to be an equal weighting of uniform sampling of floats and uniform sampling of real numbers converted to their nearest float. I think this is a much more reasonable intuition for what users expect from a "good approximation" |
Yeah, I think using a uniform sampling, or a mix, would help in this case, but I've seen a number of cases where it would instead hurt (basically, if the range is large, like -1e3...1e3, it biases toward only large values). I think the current thinking is:
|
Right, that's why I was suggesting sampling according to the sum of union of a uniform and exponential distribution. Another potentially good option would be to always sample at the edges of the provided range. That would make sure that even in the absence of enough samples to explore the space well, it's not doing something too egregiously wrong. |
On the web interface, try the expression '1/(1-x) - 1/(1+x)' for a range [0, 0.5] (I'll call this
f(x)
). Herbie will find some alternatives, including '2*x', which it claims is '99%' accurate. While it's a good approximation near 0, it's worse over most of the range. The same problem occurs for a range bracketing 0, such as [-0.5, 0.5].E.g., f(0.5) = 1.3333, and 2*0.5=1, for a relative error of ~30%.
It appears that the very small floating-point numbers are drastically over-represented in the sample, making Herbie care much more about fitting to [1e-308, 1e-10], than to [1e-10, 0.5]. In that regime a low-order Taylor expansion is pretty much always going to win.
I can see how this may be ok for large ranges, eg. [2, 1e308]: a lot more fp values are in [1e10, 1e308] than [2, 1e10], but the range is also much wider. The reciprocal situation is rather different: [1e-308, 1e-10] is literally miniscule.
AFAICT, Herbie isn't attempting to divide the range up like it does for large ranges. E.g.
if x<1e-6 then 2*x else f(x)
would be a good approximation. (Herbie will divide if I restrict the interval to [1e-9, 0.5], for example.)Suggestions:
Since I spent some time on this, here's some miscellaneous results:
(approximately) '1.216286577e-2 + x*(1.570175987 + x*2.058023534)', with a maximum error of 2.23e-2.
This can be done with two calls to
fma
.The text was updated successfully, but these errors were encountered: