4 ms·

I realized that I missed the part that he's talking about log2(x) rather than log(x+1), which changes the interval. Since MiniMaxApproximation gets quirky when

by tagrun 11y ago

I realized that I missed the part that he's talking about log2(x) rather than log(x+1), which changes the interval. Since MiniMaxApproximation gets quirky when the function is 0 in the given interval (it minimizes the relative error, so a division by 0 occurs, unless you cancel it), I'm rather using the interval [0.25, 0.5] with t=1/4: -3.64631 + 7.93796 x - 5.30406 x^2 This gives a maximum relative error of 0.00334047, which is still an order better than his. As for the (2,2) approximant: (-5.83261 - 16.7012 x + 22.394 x^2)/(1 + 11.2638 x + 7.81124 x^2) max rel error: 1.69763 10^-6 I checked several other values of t, and the max rel error for (2,0) approximant is roughly the same. This leads me to believe that the reason he is getting 10 times larger error is because he is imposing that errors should vanish at certain points. Not only this increases the max rel error, but it also distorts the smoothness of the function in a bad way (the kinks in the plots are a bad sign in general).

gjm11 11y ago
Your polynomial, since it doesn't get it exactly right at 1/4 & 1/2, will have an enormous relative error when you use it for computing logs of numbers very close to 1. Goldberg's initial function b ignores this issue, and a glance at the graph of its absolute errors will confirm that it's the minimax poly for absolute error or very close to it. His next candidate t half-fixes this, and again looking at the graph of the relative error makes it clear that it's right. (Note that avoiding intervals containing zero will indeed allow you to get better max relative errors -- keeping the relative error finite where the function is zero effectively reduces your polynomial degree by 1.) Then finally he fully fixes it with the polynomial g, solving the more interesting problem of minimizing the max relative error for the log function everywhere, and chooses a better functional form by shifting the interval he reduces to with the polynomial s. (The fact that his earlier polynomials do the wrong thing is clearly not a mistake but a paedagogical strategy: start with something simple and incrementally improve it.) My apologies for spelling all this out, but it really appears that you're accusing him of making elementary mistakes without actually understanding what he's doing. "Imposing that errors should vanish at certain points" is not a mistake, it's a necessity if you're implementing log by argument reduction plus local approximation and you care about relative error in the resulting approx_log function, and you are getting better numbers than Goldberg by solving the wrong problem. Your (2,2) rational approximant will be much more expensive to compute than the polynomial and won't yield the speed gains Goldberg is looking for. And, again, it will give you a log function with infinite relative error at 1. [EDITED to fix a typo and clarify something.]
- tagrun 11y ago
  And sorry for spelling this out for you, but maybe it is you who is "accusing of making elementary mistakes without actually understanding what he's doing." Here is why: 1) > Your polynomial, since it doesn't get it exactly right at 1/4 & 1/2, will have an enormous relative error when you use it for computing logs of numbers very close to 1. In case you missed, Mathematica's (not mine) polynomial gives a maximum 0.00334047 relative error. And the points with 0.00334047 error are actually edge points (which does not include 1). The important point is, it is not enormous. In fact, his polynomial gives 10 times larger error at certain points, so it is he who has an enormous error. And Mathematica's polynomial is continuous, so even when you slightly get outside of the intended range, you're still getting an error of the order 10^-3. 2) > Your (2,2) rational approximant will be much more expensive to compute than the polynomial and won't yield the speed gains Goldberg is looking for. Again, since you apparently missed it, the (2,2) approximant I gave is for [0.25,0.5] interval with t=1/4, so yes, bad things can and will happen if you use that polynomial outside of that range (same things happens with his polynomials too, obviously). Instead, what one should do is to move that 1/4 part into the exponent and stick to [0.25,0.5]. (About the speed vs accuracy trade-off, I already pointed that out in my original post by saying "if the division isn't too expensive"; I'm not sure why you are emphasizing it again here.) Going back to your statement, when compute logs very close to 1, you subtract 2 from the exponent and instead compute between [0.25,0.5] using that polynomial. 3. > "Imposing that errors should vanish at certain points" is not a mistake, it's a necessity if you're implementing log by argument reduction plus local approximation and you care about relative error in the resulting approx_log function, and you are getting better numbers than Goldberg by solving the wrong problem. "argument reduction plus local approximation" means range reduction to [t,2t) for log function and this has nothing to do with the behavior of approximation polynomial at the edges; you may very well have non-zero errors at t and 2t and there is nothing wrong or alarming about it (see Handbook of Floating Point Arithmetic, Chapter 11, for example). The point is, the max rel error should be kept small, which Mathematica does, 10 times better. Such an artificial condition is necessary only when the relative error function becomes discontinuous and starts making sudden jumps (see Figs 6-7 from the top in the write up.) He is trying to remedy a problem which appeared due to his choice of t, at the cost of losing degrees of freedom in the polynomial (see also the comments here http://reference.wolfram.com/language/FunctionApproximations/tutorial/FunctionApproximations.html http://reference.wolfram.com/language/FunctionApproximations... about when the function becomes zero in the interval, in which case you need to deal with these points by making them special --note from the example that this doesn't have to mean you lose 2 degrees of freedom to avoid a single point). So, in short, I am solving the right problem. 4. Which brings me to the other unspelled problem in some of his polynomials; the derivative is very bumpy and discontinuous, which spells out disaster in general math applications. (Clearly, the derivative of his function will have enormous minimax (L^\infty) and RMS (L^2) errors, unlike Mathematica's polynomial.) Summary: 1) Mathematica's polynomial gives ~10 times smaller maximum error than the write up within the range 2) Mathematica's polynomial gives 10x smaller RMS error within the range 3) Mathematica's polynomial is smooth. (I hope by now, you are clear that Mathematica's polynomial nowhere gives any enormous error and quite the oppoisite, the error is much lower) 4) If you use approximant polynomials only within their intended range and move the remaining factors into the exponent, everything works out. 5) My pointing out a bad mathematical practice wasn't personal, so please don't steer the discussion into that direction. I understand that you respect him which may motivate this, my credentials in maths aren't shabby at all (I have more peer-reviewed research papers than him, and in higher impact journals etc etc) (and if Mathematica says one thing and a human says another, in most cases Mathematica is correct) but credentials don't matter in front of solid results. In fact, accepting a scientific result (partly-)based on credentials is considered to be toxic in science. Which brings me back to my original point. I stand by what I said earlier: I don't recommend using the polynomials in the write up.

by tagrun 11y ago

gjm11 11y ago

Your polynomial, since it doesn't get it exactly right at 1/4 & 1/2, will have an enormous relative error when you use it for computing logs of numbers very close to 1. Goldberg's initial function b ignores this issue, and a glance at the graph of its absolute errors will confirm that it's the minimax poly for absolute error or very close to it. His next candidate t half-fixes this, and again looking at the graph of the relative error makes it clear that it's right. (Note that avoiding intervals containing zero will indeed allow you to get better max relative errors -- keeping the relative error finite where the function is zero effectively reduces your polynomial degree by 1.) Then finally he fully fixes it with the polynomial g, solving the more interesting problem of minimizing the max relative error for the log function everywhere, and chooses a better functional form by shifting the interval he reduces to with the polynomial s. (The fact that his earlier polynomials do the wrong thing is clearly not a mistake but a paedagogical strategy: start with something simple and incrementally improve it.) My apologies for spelling all this out, but it really appears that you're accusing him of making elementary mistakes without actually understanding what he's doing. "Imposing that errors should vanish at certain points" is not a mistake, it's a necessity if you're implementing log by argument reduction plus local approximation and you care about relative error in the resulting approx_log function, and you are getting better numbers than Goldberg by solving the wrong problem. Your (2,2) rational approximant will be much more expensive to compute than the polynomial and won't yield the speed gains Goldberg is looking for. And, again, it will give you a log function with infinite relative error at 1. [EDITED to fix a typo and clarify something.]

tagrun 11y ago
And sorry for spelling this out for you, but maybe it is you who is "accusing of making elementary mistakes without actually understanding what he's doing." Here is why: 1) > Your polynomial, since it doesn't get it exactly right at 1/4 & 1/2, will have an enormous relative error when you use it for computing logs of numbers very close to 1. In case you missed, Mathematica's (not mine) polynomial gives a maximum 0.00334047 relative error. And the points with 0.00334047 error are actually edge points (which does not include 1). The important point is, it is not enormous. In fact, his polynomial gives 10 times larger error at certain points, so it is he who has an enormous error. And Mathematica's polynomial is continuous, so even when you slightly get outside of the intended range, you're still getting an error of the order 10^-3. 2) > Your (2,2) rational approximant will be much more expensive to compute than the polynomial and won't yield the speed gains Goldberg is looking for. Again, since you apparently missed it, the (2,2) approximant I gave is for [0.25,0.5] interval with t=1/4, so yes, bad things can and will happen if you use that polynomial outside of that range (same things happens with his polynomials too, obviously). Instead, what one should do is to move that 1/4 part into the exponent and stick to [0.25,0.5]. (About the speed vs accuracy trade-off, I already pointed that out in my original post by saying "if the division isn't too expensive"; I'm not sure why you are emphasizing it again here.) Going back to your statement, when compute logs very close to 1, you subtract 2 from the exponent and instead compute between [0.25,0.5] using that polynomial. 3. > "Imposing that errors should vanish at certain points" is not a mistake, it's a necessity if you're implementing log by argument reduction plus local approximation and you care about relative error in the resulting approx_log function, and you are getting better numbers than Goldberg by solving the wrong problem. "argument reduction plus local approximation" means range reduction to [t,2t) for log function and this has nothing to do with the behavior of approximation polynomial at the edges; you may very well have non-zero errors at t and 2t and there is nothing wrong or alarming about it (see Handbook of Floating Point Arithmetic, Chapter 11, for example). The point is, the max rel error should be kept small, which Mathematica does, 10 times better. Such an artificial condition is necessary only when the relative error function becomes discontinuous and starts making sudden jumps (see Figs 6-7 from the top in the write up.) He is trying to remedy a problem which appeared due to his choice of t, at the cost of losing degrees of freedom in the polynomial (see also the comments here http://reference.wolfram.com/language/FunctionApproximations/tutorial/FunctionApproximations.html http://reference.wolfram.com/language/FunctionApproximations... about when the function becomes zero in the interval, in which case you need to deal with these points by making them special --note from the example that this doesn't have to mean you lose 2 degrees of freedom to avoid a single point). So, in short, I am solving the right problem. 4. Which brings me to the other unspelled problem in some of his polynomials; the derivative is very bumpy and discontinuous, which spells out disaster in general math applications. (Clearly, the derivative of his function will have enormous minimax (L^\infty) and RMS (L^2) errors, unlike Mathematica's polynomial.) Summary: 1) Mathematica's polynomial gives ~10 times smaller maximum error than the write up within the range 2) Mathematica's polynomial gives 10x smaller RMS error within the range 3) Mathematica's polynomial is smooth. (I hope by now, you are clear that Mathematica's polynomial nowhere gives any enormous error and quite the oppoisite, the error is much lower) 4) If you use approximant polynomials only within their intended range and move the remaining factors into the exponent, everything works out. 5) My pointing out a bad mathematical practice wasn't personal, so please don't steer the discussion into that direction. I understand that you respect him which may motivate this, my credentials in maths aren't shabby at all (I have more peer-reviewed research papers than him, and in higher impact journals etc etc) (and if Mathematica says one thing and a human says another, in most cases Mathematica is correct) but credentials don't matter in front of solid results. In fact, accepting a scientific result (partly-)based on credentials is considered to be toxic in science. Which brings me back to my original point. I stand by what I said earlier: I don't recommend using the polynomials in the write up.