4 ms·

> a maximum 0.0033407 relative error On the interval from 1/4 to 1/2. But the whole point of this exercise is to make an approximation for the log function ove

by gjm11 12y ago

> a maximum 0.0033407 relative error On the interval from 1/4 to 1/2. But the whole point of this exercise is to make an approximation for the log function over its whole domain. 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. (This is the central point I was trying to make in my comment, and the fact that you missed it suggests I wasn't clear enough. I'm sorry about that; in particular, clearly I should have made it more explicit that I understand how argument reduction works -- it hadn't occurred to me that that was in question, since it's a standard technique, described perfectly adequately in the article we're discussing.) > if you use the polynomial outside of that range I never for an instant suggested using the polynomial outside that range. I am assuming the obvious argument-reduction scheme where you say log2(2^a.b) = a + log2(b) and arrange for b to lie within some interval [t,2t). In other words, I am assuming the same thing that Goldberg described and the same thing that you are assuming (but apparently missing a key consequence of). So. Suppose you compute log2(1) using your polynomial. You argument-reduce: log2(1) = 2 + log2(0.25). Then you use your polynomial: log2(1) = 2 + (-3.64631 + 7.9376/4 - 5.30406/16) ~= 0.0066. The actual value you are looking for is log2(1) = 0. Your relative error is infinite. (You can use the other end of the interval instead. Then you get -0.0035; again, the relative error is infinite.) Goldberg avoids having this happen by forcing the absolute error to be zero at the endpoints (when he uses a polynomial on [1,2)) or at the relevant point in the middle (when he uses one on [0.75,1.5)). This extra constraint is what forces him to accept larger relative errors on his [t,2t) interval; that's the price he has to pay for finite relative error on the whole domain of the log2 function. > and this has nothing to do with the behaviour of approximation polynomial at the edges Indeed, the fact that the point where you run into trouble is at the end of the interval is irrelevant, and it would be an interior point that mattered if you did as Goldberg did and used an interval like [0.75,1.5). > So, in short, I am solving the right problem. No, really, you're not. Goldberg wants his relative error for the approx log2 function not to blow up when computing log2(1), which requires that it evaluate to exactly 0 when fed exactly 1. Your polynomial doesn't have that property. (Of course it's questionable whether relative error is what one ought to care about for an approximate logarithm function. Maybe it isn't. I don't know what applications Goldberg actually has in mind, and quite possibly he isn't at liberty to tell us. But the problem he's stated is to compute an approximation to log2 with reasonable relative error, and it's simply incorrect to say he's done that badly because you can get reasonable relative error on a smaller interval, if your relative error goes to infinity elsewhere. Which it does.) > the derivative is very bumpy and discontinuous Yeah, I dislike that too. Again, how much this matters depends on the applications you have in mind. > My pointing out a bad mathematical practice wasn't personal, so please don't steer the discussion into that direction. [...] accepting a scientific result (partly-)based on credentials is considered to be toxic in science. I never said anything even slightly personal; I have made no comment on either Goldberg's credentials or yours (or for that matter mine); only one person in this discussion has appealed to credentials, and it's you. Twice. (Once earlier: "Unless you are an expert in numerical methods ...". Once just now, comparing your credentials with Goldberg's.) Anyway: of course I strongly agree: credentials are less important than results. In this case, Goldberg made an approximation to log2 whose relative error is bounded on its entire domain of applicability, and you didn't. In particular, #4 from your summary is flatly incorrect.

tagrun 12y 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.

by gjm11 12y ago

tagrun 12y 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.