Difference between revisions of "Irrational base discrete weighted transform"

Revision as of 11:15, 13 February 2019

The irrational base discrete weighted transform (IBDWT) is a variant of the Fast Fourier transform using an irrational base. It was proposed by Richard Crandall and Barry Fagin in 1994.

The IBDWT is used to perform FFT multiplication modulo Mersenne number in such programs as Prime95, CUDALucas, Glucas, gpuLucas.

In 2003, C. Percival proposed generalized IBDWT.

Crandall, R., Fagin, B. Discrete weighted transforms and large-integer arithmetic. Mathematics of Computation 62, 205, 305-324, January 1994.
Crandall, R. Topics in Advanced Scientific Computation. TELOS/Springer-Verlag, 1996.
Percival, C. Rapid multiplication modulo the sum and difference of highly composite numbers. Math. Comp. 72:387-395, 2003.
Crandall, R., Pomerance, C. Prime numbers: A Computational Perspective: 2nd edition. Springer, 2005.

@@ Line 1: / Line 1: @@
-The '''irrational base discrete weighted transform''' ('''IBDWT''') is a variant of the [[Fast Fourier transform]] using an irrational base. It was proposed by [[Richard Crandall]] and [[Barry Fagin]] in 1994.
+{{Shortcut|IBDWT|Irrational base discrete weighted transform: a variant of the [[Fast Fourier transform]] using an irrational base.}}
+The '''irrational base discrete weighted transform''' ('''IBDWT''') is a variant of the [[Fast Fourier transform]] using an [[Irrational number|irrational]] base. It was proposed by [[Richard Crandall]] and [[Barry Fagin]] in 1994.
 The IBDWT is used to perform FFT multiplication modulo [[Mersenne number]] in such programs as [[Prime95]], [[CUDALucas]], [[Glucas]], [[gpuLucas]].