3 ms·

> If you take Mathematica's/your polynomial and do that with it, you get an infinitely large relative error at 1 because log(1)=0 but your approx_log(1) is not

by tagrun 11y ago

> If you take Mathematica's/your polynomial and do that with it, you get an infinitely large relative error at 1 because log(1)=0 but your approx_log(1) is not 0. So what? Instead of accepting that his polynomial is more erroneous, you are steering this whole discussion in a totally synthetic direction. Essentially your whole argument is global relative minimax error must be finite at every single point in the domain. I don't know where you got this idea/mantra but the point here is to have a rough and fast sketch with small overall error in applications, not mathematical rigor, which you can't have with a 2nd degree polynomial anyway. His polynomials give inifintely huge L^1 and L^2 errors near origin; the minimax is finite (1) but it doesn't make an infinitely big error OK. Which is why such simple minded mantras are wrong and bound to fail. While minimax is the only thing that gets mentioned there, the world is a bigger place. There are many error measures. The concept of minimax approximation breaks down at the points where the function is 0 (you can have any arbitrary small number and we're still doomed according to minimax) --this is not the end of the world, in many application, L^2 error (RMS) is more relevant, in which case Mathematica's approximant is again 10 times better. Do I want to make my errors 10 times larger over the whole domain and do I want a bumpy approximant just to make minimax happy at one, single point in the whole floating point range? No, thanks. If we're going to pick nits and be rigorous, his function fails big time at x=0 and x<0, and for x=\pm \infty as well as NaN. Now if this is a real concern, people just put a conditional there and live on happily. You can do that for x==1 case if this is a serious concern in your application ---even though it is very unlikely (this shouldn't bother you since you're OK with bumpy functions, and it's going to be a small bump in this case anyway and still beats his polynomial by an order globally). The whole point here is to have some rough sketch of log that works fast and yields small errors overall in the actual calculation. If I wanted rigor, I'd use libm log2 or http://www.netlib.org/fdlibm/e_log.c http://www.netlib.org/fdlibm/e_log.c which is also quite fast. Understand this, relative flavor of minimax is some measure which is rarely directly relevant, and is hardly suited for log function. It's not God's absolute commandement and the requirements of domain specific rough approximants depend on the actual usage: whether the errors are going to end up being additive, multiplicative, etc. Anyway, I'm not going to waste more time on this. Here are the unwavering facts since the beginning: 1) His polynonimal has 10x worse relative error, and worse RMS error in the whole domain 2) Your whole argument "but what about x==1" is wrongly placed since the approximant you have been fiercely defending here itself suffers from infinite pathological errors at x <= 0; if it bothers you so much nevertheless, just put an if(x==1) return 0, and there you go, I still have a 10x better function.

gjm11 11y ago
> So what? So "produce a fast approx log function with small relative error everywhere" is the problem Goldberg was trying to solve from the outset. (He wants to be able to give guarantees like "accurate to 7 bits".) The fact that he gets larger errors than you is completely explained by this. Of course no one else is obliged to be interested in solving that problem, but that's the problem he's trying to solve. (If you'd said "I think Goldberg is solving the wrong problem; no one cares about relative error rather than absolute error in an approximate logarithm function" I'd have been inclined to agree. But no, it was "haha, he computed a crappy polynomial; that's what happens when you let amateurs do work that should be left to the professionals" with no sign of any understanding of what constraints he was working with that led him to compute what he did.) > Instead of accepting that his polynomial is more erroneous, you are steering this whole discussion in a totally synthetic direction. As well as agreeing that his polynomial gives larger errors on the range to which it's applied directly (which I have, explicitly, agreed; go back and check if you don't believe me), I am pointing out that it does (infinitely) better than yours according to the criterion Goldberg was actually using, namely relative error over the whole domain in the log function it produces. > mantra Wow. (I got it from the start of Goldberg's article, where he explains what problem he's trying to solve.) > infinitely huge L^1 and L^2 errors near origin (I take it you mean in the derivative.) Yours does too; it is discontinuous at every integer power of 2. Obviously any piecewise-polynomial scheme like this one is going to have discontinuities in some derivative (and you can push up which derivative at the usual cost of either using higher-degree polynomials or getting worse errors). > There are many error measures. It appears that you think I am much more ignorant in this field than I actually am. (Or perhaps that you're pretending to for rhetorical effect, but I hope not.) > just to make minimax happy at one, single point If the relative error is infinite at x=1 then it is also very large when x is very close to 1. > fails big time at x=0 and x<0 You're complaining that he isn't generating NaNs and infinities when passed inputs that don't have a finite log? Fair enough, I guess, but in a post subtitled "Part I: the basics" it seems enough to me that he has the following warning sentence: "The code does not check that x>0, much less check for infinities or NaNs. This may be appropriate for a fast version of log." (Which he does.) > fiercely defending I think you may be mistaken about where the fierceness is coming from in this discussion. > just put an if (x==1) return 0 and there you go, I still have a 10x better function Nope. You've got rid of the actually infinite relative errors but you still have extremely large relative errors for x very close to 1 but not equal. Again: by all means argue that bounding the relative error in the return value of a log function is the Wrong Thing for almost all purposes. I will probably agree. But that isn't what you did.

by tagrun 11y ago

gjm11 11y ago

> So what? So "produce a fast approx log function with small relative error everywhere" is the problem Goldberg was trying to solve from the outset. (He wants to be able to give guarantees like "accurate to 7 bits".) The fact that he gets larger errors than you is completely explained by this. Of course no one else is obliged to be interested in solving that problem, but that's the problem he's trying to solve. (If you'd said "I think Goldberg is solving the wrong problem; no one cares about relative error rather than absolute error in an approximate logarithm function" I'd have been inclined to agree. But no, it was "haha, he computed a crappy polynomial; that's what happens when you let amateurs do work that should be left to the professionals" with no sign of any understanding of what constraints he was working with that led him to compute what he did.) > Instead of accepting that his polynomial is more erroneous, you are steering this whole discussion in a totally synthetic direction. As well as agreeing that his polynomial gives larger errors on the range to which it's applied directly (which I have, explicitly, agreed; go back and check if you don't believe me), I am pointing out that it does (infinitely) better than yours according to the criterion Goldberg was actually using, namely relative error over the whole domain in the log function it produces. > mantra Wow. (I got it from the start of Goldberg's article, where he explains what problem he's trying to solve.) > infinitely huge L^1 and L^2 errors near origin (I take it you mean in the derivative.) Yours does too; it is discontinuous at every integer power of 2. Obviously any piecewise-polynomial scheme like this one is going to have discontinuities in some derivative (and you can push up which derivative at the usual cost of either using higher-degree polynomials or getting worse errors). > There are many error measures. It appears that you think I am much more ignorant in this field than I actually am. (Or perhaps that you're pretending to for rhetorical effect, but I hope not.) > just to make minimax happy at one, single point If the relative error is infinite at x=1 then it is also very large when x is very close to 1. > fails big time at x=0 and x<0 You're complaining that he isn't generating NaNs and infinities when passed inputs that don't have a finite log? Fair enough, I guess, but in a post subtitled "Part I: the basics" it seems enough to me that he has the following warning sentence: "The code does not check that x>0, much less check for infinities or NaNs. This may be appropriate for a fast version of log." (Which he does.) > fiercely defending I think you may be mistaken about where the fierceness is coming from in this discussion. > just put an if (x==1) return 0 and there you go, I still have a 10x better function Nope. You've got rid of the actually infinite relative errors but you still have extremely large relative errors for x very close to 1 but not equal. Again: by all means argue that bounding the relative error in the return value of a log function is the Wrong Thing for almost all purposes. I will probably agree. But that isn't what you did.