A point in regard to a previous list query about trigonometric
evaluation
of some huge array...
Let us say we have a very large array of type float or double, with
general
element denoted x[n], and we want to replace the array with, for
example,
cos(x[n]) everywhere.
One way which is *wildly* faster than just applying cos() to each
element
is:
1) Create a fixed table of cos(2 PI j/N) for j = 0,...,N-1for some N
that provides adequate precision
in what follows (it is no hard to work out, for example, that N = 2^15
nails the problem
for single-precision).
2) Run through the array, multiplying each element by the constant r =
1/(2 PI) and then taking the fractional part,
i.e. replace the array {x[n]} with {r x[n] - floor(r x[n])}.
3) Run again through the now-normalized array, and use the obvious
interpolation from the
fixed table: Use j = floor(x N), and this j + 1 as endpoints, so to
resolve a cos(x[n]) value
in the obvious linear sense.
For N = 2^15 table size, say, it can be shown that
one has a maximum error of 1/2^25 from interpolation.
If one does not like the notion of a table, consider two viewpoints:
a) you can still vectorize a good deal of this method, doing
several interpolations at once,
b) no matter how you twist and turn, the lookups radically beat
old-fashioned cos() calls;
moreover ops such as fractional-part jamming must be done in
any classical cos() anway,
so such nonlinear ops can't hurt.
Similar ideas obtain, of course, for other elementary functions.
There should also be a way to go even faster, say by
using a relevant series for cos() via vectorization on the array; e.g.,
to get a cos() approximation
1 - x[n]^2/2! + x[n]^4/4!
for every array element is a trivial task for a vector processor.
R. E. Crandall
Advanced Computation Group
PS. I thank the eminent computationalist R. Brent for ideas along
these lines.
_______________________________________________
scitech mailing list | email@hidden
Help/Unsubscribe/Archives: http://www.lists.apple.com/mailman/listinfo/scitech
Do not post admin requests to the list. They will be ignored.
