On Wed, Apr 18, 2007 at 11:10:08PM +0200, Albrecht Frenzel wrote:
> Daniel Lakeland wrote:
> > Perhaps you can store the value of the
> > function, and the gradient of the function at a set of regularly
> > spaced grid points (that would be 3 numbers for each grid point, one
> > for the function and two for the components of the gradient), and then
> > you evaluate the function by finding the closest grid point, and using
> > linear extrapolation with the gradient you refine the computation.
>
> This would be the mathematical solution for the problem, using
> real numbers.
>
> A fixedpoint solution itself will produce additional errors, that
> are missing in such an approximation model. To add them, leads to
> the same kind of problem, I'm currently investigating: error
> functions like beds of nail.
My point is that you can pre-calculate with maxima the fixed point
values for each grid location by first calculating using floating
point with maxima, and then rounding off the value. So in the first
place, there is no need to have a fixed point logarithm function, or
do any fixed point arithmetic to get an approximation at the grid
value. It is just a lookup, and you can compute the maximum roundoff
error at each gridpoint ahead of time as well.
Now your choice is, do you have a memory restriction? If not, use a
dense enough grid and nearest neighbor. Your maximum error is then
easily computable. If you have a memory restriction, use fixed-point
extrapolation.
Fixed point extrapolation is probably relatively easy to put an error
bound on though when compared with discrete logarithm approximations
and soforth. If you are clever I believe that you can come up with an
analytical expression which gives a bound on your error which
*includes* the fixed point error in it. If you can come up with the
analytical bound as a function of the spacing of the points, then you
can select a grid density which gives you an acceptable final result.
If it is important that you know exactly what the maximum error is,
rather than simply putting a bound on it, you will be stuck with the
numerical approach with spikey error functions.
--
Daniel Lakeland
dlakelan at street-artists.org
http://www.street-artists.org/~dlakelan