A Simple Approximation Algorithm in Z[e^{2?i/8}]
Title | A Simple Approximation Algorithm in Z[e^{2?i/8}] |
Publication Type | Technical Report |
Year of Publication | 1996 |
Authors | M. Shokrollahi, A., & Stemann V. |
Other Numbers | 1042 |
Keywords | continued fractions, cyclotomic fields, Fast Fourier transforms |
Abstract | 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. |
URL | http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1996/tr-96-032.pdf |
Bibliographic Notes | ICSI Technical Report TR-96-032 |
Abbreviated Authors | M. A. Shokrollahi and V. Stemann |
ICSI Publication Type | Technical Report |