Publication Details
Title: A Simple Approximation Algorithm in Z[e^{2πi/8}]
Author: M. A. Shokrollahi and V. Stemann
Group: ICSI Technical Reports
Date: August 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-032.pdf
Overview:
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. Keywords: Fast Fourier transforms, cyclotomic fields, continued fractions
Bibliographic Information:
ICSI Technical Report TR-96-032
Bibliographic Reference:
M. A. Shokrollahi and V. Stemann. A Simple Approximation Algorithm in Z[e^{2πi/8}]. ICSI Technical Report TR-96-032, August 1996
Author: M. A. Shokrollahi and V. Stemann
Group: ICSI Technical Reports
Date: August 1996
PDF: ftp://ftp.icsi.berkeley.edu/pub/techreports/1996/tr-96-032.pdf
Overview:
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. Keywords: Fast Fourier transforms, cyclotomic fields, continued fractions
Bibliographic Information:
ICSI Technical Report TR-96-032
Bibliographic Reference:
M. A. Shokrollahi and V. Stemann. A Simple Approximation Algorithm in Z[e^{2πi/8}]. ICSI Technical Report TR-96-032, August 1996