mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

, the irrational base discrete weighted transform (IBDWT) is a variant of the

fast Fourier transform A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain (often time or space) to a representation in th ...

using an irrational base; it was developed by Richard Crandall ( Reed College), Barry Fagin ( Dartmouth College) and Joshua Doenias ( NeXT Software) in the early 1990s using

Mathematica Wolfram Mathematica is a software system with built-in libraries for several areas of technical computing that allow machine learning, statistics, symbolic computation, data manipulation, network analysis, time series analysis, NLP, optimizat ...

. The IBDWT is used in the Great Internet Mersenne Prime Search's client Prime95 to perform

FFT multiplication A multiplication algorithm is an algorithm (or method) to multiply two numbers. Depending on the size of the numbers, different algorithms are more efficient than others. Efficient multiplication algorithms have existed since the advent of the de ...

, as well as in other programs implementing Lucas-Lehmer test, such as CUDALucas and Glucas.

References

* Richard Crandall, Barry Fagin: ''Discrete weighted transforms and large-integer arithmetic'', Mathematics of Computation 62, 205, 305-324, January 1994
PDF file
* Richard Crandall: ''Topics in Advanced Scientific Computation'', TELOS/Springer-Verlag FFT algorithms Discrete transforms {{Mathanalysis-stub