FFTRing

Next: fft Up: Univariate Polynomials and Series Previous: fractionalRoots,roots Contents Index

FFTRing

$\begin{usage} FFTRing: Category \end{usage}$

$\begin{descr} FFTRing~is the category of rings that export an algorithm for the FFT product of univariate polynomials over themselves. \end{descr}$

Exports

CommutativeRing

fft: (P:POL %) $\to$ (P, P) $\to$ Partial P FFT product

fft!: (P:POL %) $\to$ (P, P, P) $\to$ Boolean FFT product

fftCutoff: $\to$ MachineInteger Cutoff for FFT in

where
POL == UnivariatePolynomialCategory0

Subsections

fft
fft!
fftCutoff

Manuel Bronstein 2000-12-13

`CommutativeRing`
`fft`:	(P:POL %) $\to$ (P, P) $\to$ `Partial` P	FFT product
`fft!`:	(P:POL %) $\to$ (P, P, P) $\to$ `Boolean`	FFT product
`fftCutoff`:	$\to$ `MachineInteger`	Cutoff for FFT in