go-fft docs

A pure-Go (no cgo) FFT library — the numpy.fft / scipy.fft equivalent for Go. It computes the discrete Fourier transform of complex and real signals of any length, with no dependency on the native FFTW3 C library.

Ruby has no cgo-free FFT (every option wraps FFTW3); gonum/dsp/fourier is pure Go but its optimized assembly is amd64-only. go-fft is a portable Go core that runs on Go’s six 64-bit targets, with AVX2 and AVX-512 kernels on amd64 and NEON kernels on arm64, generated by go-asmgen and bit-identical to the Go code. It is grown test-first with 100% coverage and differentially checked against numpy.fft.

import "github.com/go-fft/fft"

x := []complex128{1, 2, 3, 4}
X := fft.FFT(x)          // forward transform
y := fft.IFFT(X)         // round-trips back to x

Try it in your browser: the playground runs go-fft compiled to WebAssembly, with nothing to install — pick a signal and a transform (FFT, RFFT, DCT/DST, any length, float64 or float32), see the spectrum, and copy the equivalent Go and numpy code.

Use v0.26.3 or later. v0.25.0 to v0.26.2 return wrong N-D results, silently, on Intel CPUs with AVX-512 when an axis other than the last has a length 9·p (v0.26.3 release notes).

API surface

Normalization (Norm: NormBackward, the default, NormOrtho, NormForward), bin layout and frequency conventions follow numpy.fft; the DCT and DST follow scipy.fft.

Opt-in fused multiply-add (Options.FMA)

By default every amd64 kernel is bit-identical to the package’s Go code, so a result does not depend on the CPU that computed it. Options{FMA: true} gives that up for speed on amd64 CPUs with FMA3: twiddle products and butterfly constants are fused, and on AVX-512 Intel CPUs (Cascade Lake) 1,024 and 2,048 points take radix-32 passes. Results differ from the default’s in the last bits and are as accurate (0.76–1.08× the default’s error against long-double scipy, over 90 transforms). Elsewhere (arm64, other architectures, no FMA3) the option gives the default transform, bit for bit; the float32 transforms ignore it.

X := fft.FFTWith(x, fft.Options{FMA: true})
p := fft.NewPlanWith(1024, fft.Options{FMA: true})

Use it when bit-for-bit reproducibility across machines does not matter. Measured gains against the default plan: Cascade Lake complex 1,024 1.22× (0.94× FFTW’s time, against 1.19× by default), 2,048 1.11×, RFFT 4,096 1.09×, 256 and 512 1.07–1.08×; Zen 3 1–6% (complex 1,024 stays 1.10× FFTW’s time). Where fusing measured slower (Cascade Lake 4,096 to 16,384 points) the plan keeps the default kernels, so no measured row is slower than the default. See Performance.

Reusable plans

A plan computes the twiddle tables once and reuses them, so a transform does no sin/cos. The convenience functions above keep an internal per-length plan cache and get this for free. A plan is what you reach for when you control the loop: it writes into your slice, so a repeated transform allocates nothing.

p := fft.NewPlan(n)            // complex transform of length n
p.FFT(dst, src)                // []complex128 of length n; dst and src may alias
p.IFFT(dst, src)               // normalized inverse

rp := fft.NewRealPlan(n)       // real-input transform
rp.RFFT(dst, src)              // src []float64 (n), dst []complex128 (n/2+1)
rp.IRFFT(out, spec)            // out []float64 (n), spec the half spectrum

pn := fft.NewPlanN(rows, cols) // any rank: NewPlanN(d0, d1, d2, ...)
pn.FFT(dst, src)               // row-major; matches FFTN
r2 := fft.NewRealPlan2(rows, cols)
r2.RFFT(spec, img)             // spec len r2.SpectrumLen() = rows*(cols/2+1)

FFTN, FFT2 and RFFT2 return a new slice on every call. On a many-core host, that allocation (and the garbage collector behind it) can cost more than the transform itself for a small repeated shape; PlanN and RealPlan2 avoid it.

How a length is transformed

• Lengths whose prime factors are all ≤ 13: an iterative mixed-radix Stockham engine, with radix-8/4/2/3/5/7 straight-line passes plus a general radix-p pass for 11 and 13.
• A prime whose N−1 is 7-smooth: Rader’s algorithm. Any other length: Bluestein’s chirp-z. Both convolve on the Stockham engine.
• Powers of two on loong64, s390x and amd64 without AVX2, and above 65536 on riscv64: an iterative, cache-blocked radix-4 kernel (SSE2 butterflies on amd64).
• Real transforms: a half-length complex transform plus one untangle pass.
• N-D transforms: separable, with the lines of a large axis spread across cores. On amd64 with AVX2, an axis other than the last runs as batched passes over strips of neighbouring lines, in place, instead of gathering each line.

SIMD and architectures

• amd64:
  • AVX2: the Stockham passes of radix 2/3/4/5/8 run as generated AVX2 kernels, with a final pass vectorized across blocks, and so does the real-FFT untangle.
  • AVX-512: powers of two of 256 points or more run four points per register, where the CPU and the operating system support it. From 65536 points on Intel, a blocked schedule keeps the last passes in L2 (v0.12.0).
  • Radix 16: on AVX2 without AVX-512, 128, 256 and 1024 points (2048 on Intel) take a radix-16 pass (v0.10.0).
  • Split layout (AMD, AVX2): powers of two keep real and imaginary parts apart between passes, removing every shuffle (v0.14.0).
  • Composites (Intel, AVX2): a radix-12 prime-factor pass and radix-16 tails up to 16384 points (v0.15.0); on AMD, radix-10/12/15/20 prime-factor passes (v0.18.0).
  • Split layout at 512 bits (Intel, AVX-512): powers of two from 256 points, eight points per register (v0.19.0).
  • Without AVX2: the radix-4 kernel runs SSE2 butterflies.
• arm64: the Stockham passes of radix 2/3/4/5/8, and the radix-2 to 5 final passes over an even number of blocks, run as generated NEON kernels (1.28× per transform on Neoverse-N1, 1.15× on Apple M4). gc fuses multiply-adds on arm64, so each kernel reproduces which product the Go code rounds and which it fuses. Powers of two keep their data split between passes, and the columns of N-D plans run as batched NEON passes (v0.11.0). The real-FFT untangle has a NEON kernel, and small N-D plans run each axis as one pass sequence over all lines (v0.17.0).
• Single precision: the float32 passes, the real-FFT untangle and the N-D column passes have their own AVX2 and NEON kernels (v0.13.0, v0.16.0).
• riscv64, loong64, ppc64le, s390x: the passes are Go code, which the gc compiler compiles to scalar instructions. It does not vectorize; it does fuse multiply-adds.
  • Complex multiply: kernels for riscv64 (RVV) and s390x exist and are validated bit-identical, but are not used, because the scalar loop measured as fast.

⛔ The kernels keep the Go code’s arithmetic exactly: on amd64 separately rounded multiplies and adds, no FMA, no reassociation; on arm64 the same fusions gc chose. Their results are therefore bit-identical to the Go passes (except the bits of a NaN produced from infinite inputs, which IEEE 754 leaves unspecified). The tests check it on generic, signed-zero and infinite inputs, comparing math.Float64bits. A faster transform that answers differently is not the same transform.

Where to go next

• Roadmap (phases) — the phased plan and what ships today.
• Performance — head-to-head with FFTW, numpy/scipy (pocketfft) and gonum, describing v0.27.0 on Zen 3, Neoverse-N1 and Cascade Lake.

Source: github.com/go-fft/fft · the transform is also exposed to Ruby through go-embedded-ruby’s FFT module.