A Simple Approximation Algorithm in Z[e^{2?i/8}]

TitleA Simple Approximation Algorithm in Z[e^{2?i/8}]
Publication TypeTechnical Report
Year of Publication1996
AuthorsM. Shokrollahi A, Stemann V
Other Numbers1042
Keywordscontinued fractions, cyclotomic fields, Fast Fourier transforms

We describe a very simple and efficient new algorithm for the approximation of complex numbers by algebraic integers in Z[e^{2?i/8}] whose coeffcients with respect to the usual basis are bounded in absolute value by a given integer M. Its main idea is the use of a novel signature technique. An important application is the reduction of dynamic range requirements for residue number system implementations of the discrete Fourier transform. The algorithm uses at most 10 log(M) arithmetic steps and 2.4log(M) additional memroy. It yields approximations within a distance of at most 3.42/M. Several examples are included which show that the algorithm is very fast in practice. For instance, 50000 complex approximations take less than 0.7 seconds on a SPARC-5.

Bibliographic Notes

ICSI Technical Report TR-96-032

Abbreviated Authors

M. A. Shokrollahi and V. Stemann

ICSI Publication Type

Technical Report