On Monday 07 February 2005 20:52, Daniel Phillips wrote: > On Monday 07 February 2005 02:22, I wrote: > > I imagine (but did not prove) that the maximum error is quite similar > > over all the intervals between .5 and 1, because the curvature of 1/x > > doesn't change much in that interval... > > This turned out to be wrong. The result for the left end of the > > interval is: > >>> ((1/.501 + 2)/2 - 1/.5005) > > 1.9940139697194326e-06 > > or about one part in 500,000, i.e., 19 bits of accuracy. Just enough. > > It's kind of surprising that the maximum error varies by a factor of 8 > over the interval [.5, 1]. Could somebody please double check my > reasoning?
Do note that what you're using is not the best possible linear approximation. Thinking graphically, you're drawing a straight line between the first and last point of the interval, so that you're always a little high in the approximation. If you draw that line a little lower, then you'll still be high in the middle, but low at the ends, and the error is more balanced. The real maximum error is thus about half that, so you get one bit more precision. That's what my implementation does, but it has the additional hurdle that both the value (y-location of the approximating line) and the difference (steepness) are quite heavily quantised to fit in the 18 bits LUT entries. I've been playing with Gnuplot for a bit. gnuplot> a = -2 gnuplot> b = 3 gnuplot> plot [0.5:1] 1/x, a*x + b, 1/x - a*x - b gnuplot> a = ((1/0.501) - (1/0.500))/0.001 gnuplot> b = 2 - 0.5*a gnuplot> plot [0.500:0.501] 1/x, (a*x + b) gnuplot> plot [0.500:0.501] 1/x - (a*x + b) This last one looks like a quadratic curve (it isn't of course, but very close) with a minimum of ~ -2e-6 at 0.5005. gnuplot> a = ((1/1) - (1/0.999))/0.001 gnuplot> b = 1 - a gnuplot> plot [0.999:1] 1/x, (a*x + b) gnuplot> plot [0.999:1] 1/x - (a*x + b) Yields a similar curve with a minimum of -2.5e-7 at around 0.9995. So you didn't miss anything. The question is why does it differ. The standard linear approximation is the first-order Taylor polynomial. It's not exactly the same as what we were doing above (it is the line that touches the 1/x curve right in the middle of each LUT interval, rather than the one that intersects it at both ends), but it gives similar results in practice. The advantage is that we can now look at the quality of the approximation more easily. The error in the approximation is the sum of the higher-order Taylor terms, which is dominated by the second-order term. The Taylor polynomial of 1/x around a is 1/a - 1/(a**2) * (x - a)**1 + 1/(a**3) * (x - a)**2 - ... If our approximation consists of the first two terms, then the rest of the terms represent the error. As said, it is dominated by the second-order term, so let's forget about the rest. Then what we have left is 1/(a**3) * (x - a)**2 Our a is always just in the middle of an interval, ie. at 0.5005 or 0.9995 in the earlier examples, and between those values for the rest of the table. x then runs between 0.0005 less and 0.0005 more than that. That means that (x - a)**2 is never larger than 5e-4**2 = 2.5e-7, and no better at x = 1 than at x = 0.5. However, the 1/(a**3) term does vary between about 8 for a = 0.5005 (first interval) and about 1 for a = 0.9995. Thus, at the top end of the table, our maximum error is about 2.5e-7 * 1 = 2.5e-7, and at the bottom end the maximum error is about 2.5e-7 * 8 = 2e-6. Your numbers (yes, I'm somewhat surprised as well that it all works out so nicely :-)). Now I need to figure out a way to use this to improve the implementation... Cheers, Lourens _______________________________________________ Open-graphics mailing list [email protected] http://lists.duskglow.com/mailman/listinfo/open-graphics List service provided by Duskglow Consulting, LLC (www.duskglow.com)
