README
¶
gofft 
A better radix-2 fast Fourier transform in Go.
Package gofft provides an efficient radix-2 fast discrete Fourier transformation algorithm in pure Go.
This code is much faster than existing FFT implementations and uses no additional memory.
The algorithm is non-recursive, works in-place overwriting the input array, and requires O(1) additional space.
What
I took an existing FFT implementation in Go, cleaned and improved the code API and performance, and replaced the permutation step with an algorithm that works with no temp array.
Performance was more than doubled over the original code, and is consistently the fastest Go FFT library (see benchmarks below) while remaining in pure Go.
Added convolution functions Convolve(x, y), FastConvolve(x, y), MultiConvolve(x...), FastMultiConvolve(X), which implement the discrete convolution and a new hierarchical convolution algorithm that has utility in a number of CS problems. This computes the convolution of many arrays in O(n*ln(n)2) run time, and in the case of FastMultiConvolve O(1) additional space.
Also included new utility functions: IsPow2, NextPow2, ZeroPad, ZeroPadToNextPow2, Float64ToComplex128Array, Complex128ToFloat64Array, and RoundFloat64Array
Why
Most existing FFT libraries in Go allocate temporary arrays with O(N) additional space. This is less-than-ideal when you have arrays of length of 225 or more, where you quickly end up allocating gigabytes of data and dragging down the FFT calculation to a halt.
Additionally, the new convolution functions have significant utility for projects I've written or am planning.
One downside is that the FFT is not multithreaded (like go-dsp is), so for large vector size FFTs on a multi-core machine it will be slower than it could be. FFTs can be run in parallel, however, so in the case of many FFT calls it will be faster.
How
package main
import (
"fmt"
"github.com/argusdusty/gofft"
)
func main() {
// Do an FFT and IFFT and get the same result
testArray := gofft.Float64ToComplex128Array([]float64{1, 2, 3, 4, 5, 6, 7, 8})
err := gofft.FFT(testArray)
if err != nil {
panic(err)
}
err = gofft.IFFT(testArray)
if err != nil {
panic(err)
}
result := gofft.Complex128ToFloat64Array(testArray)
gofft.RoundFloat64Array(result)
fmt.Println(result)
// Do a discrete convolution of the testArray with itself
testArray, err = gofft.Convolve(testArray, testArray)
if err != nil {
panic(err)
}
result = gofft.Complex128ToFloat64Array(testArray)
gofft.RoundFloat64Array(result)
fmt.Println(result)
}
Outputs:
[1 2 3 4 5 6 7 8]
[1 4 10 20 35 56 84 120 147 164 170 164 145 112 64]
Benchmarks
gofft>go test -bench=FFT$ -benchmem -cpu=1 -benchtime=5s
goos: windows
goarch: amd64
pkg: github.com/argusdusty/gofft
BenchmarkSlowFFT/Tiny_(4) 26778385 211 ns/op 302.94 MB/s 64 B/op 1 allocs/op
BenchmarkSlowFFT/Small_(128) 19299 307909 ns/op 6.65 MB/s 2048 B/op 1 allocs/op
BenchmarkSlowFFT/Medium_(4096) 20 289214125 ns/op 0.23 MB/s 65536 B/op 1 allocs/op
BenchmarkKtyeFFT/Tiny_(4) 93711196 62.2 ns/op 1028.68 MB/s 64 B/op 1 allocs/op
BenchmarkKtyeFFT/Small_(128) 2772037 2065 ns/op 991.94 MB/s 2048 B/op 1 allocs/op
BenchmarkKtyeFFT/Medium_(4096) 60714 99719 ns/op 657.20 MB/s 65536 B/op 1 allocs/op
BenchmarkKtyeFFT/Large_(131072) 615 9582652 ns/op 218.85 MB/s 2097152 B/op 1 allocs/op
BenchmarkGoDSPFFT/Tiny_(4) 1875174 3379 ns/op 18.94 MB/s 519 B/op 13 allocs/op
BenchmarkGoDSPFFT/Small_(128) 495807 12516 ns/op 163.63 MB/s 5591 B/op 18 allocs/op
BenchmarkGoDSPFFT/Medium_(4096) 36092 162981 ns/op 402.11 MB/s 164364 B/op 23 allocs/op
BenchmarkGoDSPFFT/Large_(131072) 802 7506683 ns/op 279.37 MB/s 5243448 B/op 28 allocs/op
BenchmarkGoDSPFFT/Huge_(4194304) 6 906703233 ns/op 74.01 MB/s 167772810 B/op 33 allocs/op
BenchmarkScientificFFT/Tiny_(4) 54239148 111 ns/op 576.40 MB/s 128 B/op 2 allocs/op
BenchmarkScientificFFT/Small_(128) 3121048 1938 ns/op 1056.98 MB/s 4096 B/op 2 allocs/op
BenchmarkScientificFFT/Medium_(4096) 77004 74428 ns/op 880.52 MB/s 131072 B/op 2 allocs/op
BenchmarkScientificFFT/Large_(131072) 1816 3206107 ns/op 654.11 MB/s 4194304 B/op 2 allocs/op
BenchmarkScientificFFT/Huge_(4194304) 24 247888846 ns/op 270.72 MB/s 134217728 B/op 2 allocs/op
BenchmarkFFT/Tiny_(4) 794523928 7.73 ns/op 8279.81 MB/s 0 B/op 0 allocs/op
BenchmarkFFT/Small_(128) 5375140 1132 ns/op 1809.57 MB/s 0 B/op 0 allocs/op
BenchmarkFFT/Medium_(4096) 97856 56821 ns/op 1153.38 MB/s 0 B/op 0 allocs/op
BenchmarkFFT/Large_(131072) 2142 2850784 ns/op 735.64 MB/s 0 B/op 0 allocs/op
BenchmarkFFT/Huge_(4194304) 26 223165362 ns/op 300.71 MB/s 0 B/op 0 allocs/op
Documentation
¶
Overview ¶
Package gofft provides a fast discrete Fourier transformation algorithm.
Implemented is the 1-dimensional DFT of complex input data for with input lengths which are powers of 2.
The algorithm is non-recursive, works in-place overwriting the input array, and requires O(1) additional space.
Index ¶
- func Complex128ToFloat64Array(x []complex128) []float64
- func Convolve(x, y []complex128) ([]complex128, error)
- func FFT(x []complex128) error
- func FastConvolve(x, y []complex128) error
- func FastMultiConvolve(X []complex128, n int, multithread bool) error
- func Float64ToComplex128Array(x []float64) []complex128
- func IFFT(x []complex128) error
- func IsPow2(N int) bool
- func MultiConvolve(X ...[]complex128) ([]complex128, error)
- func NextPow2(N int) int
- func Prepare(N int) errordeprecated
- func RoundFloat64Array(x []float64)
- func ZeroPad(x []complex128, N int) []complex128
- func ZeroPadToNextPow2(x []complex128) []complex128
- type InputSizeError
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func Complex128ToFloat64Array ¶
func Complex128ToFloat64Array(x []complex128) []float64
Complex128ToFloat64Array converts a complex128 array to the equivalent float64 array taking only the real part.
func Convolve ¶
func Convolve(x, y []complex128) ([]complex128, error)
Convolve computes the discrete convolution of x and y using FFT. Pads x and y to the next power of 2 from len(x)+len(y)-1
func FFT ¶
func FFT(x []complex128) error
FFT implements the fast Fourier transform. This is done in-place (modifying the input array). Requires O(1) additional memory. len(x) must be a perfect power of 2, otherwise this will return an error.
func FastConvolve ¶
func FastConvolve(x, y []complex128) error
FastConvolve computes the discrete convolution of x and y using FFT and stores the result in x, while erasing y (setting it to 0s). Since this does no allocations, x and y are assumed to already be 0-padded for at least half their length.
func FastMultiConvolve ¶
func FastMultiConvolve(X []complex128, n int, multithread bool) error
FastMultiConvolve computes the discrete convolution of many arrays using a hierarchical FFT algorithm, and stores the result in the first section of the input, writing 0s to the remainder of the input This does no allocations, so the arrays must first be 0-padded out to the next power of 2 from sum of the lengths of the longest two arrays. Additionally, the number of arrays must be a power of 2 X is the concatenated array of arrays, of length N (n*m) n is the length of the 0-padded arrays. multithread tells the algorithm to use goroutines, which can slow things down for small N. Takes O(N*log(N)^2) run time and O(1) additional space.
func Float64ToComplex128Array ¶
func Float64ToComplex128Array(x []float64) []complex128
Float64ToComplex128Array converts a float64 array to the equivalent complex128 array using an imaginary part of 0.
func IFFT ¶
func IFFT(x []complex128) error
IFFT implements the inverse fast Fourier transform. This is done in-place (modifying the input array). Requires O(1) additional memory. len(x) must be a perfect power of 2, otherwise this will return an error.
func IsPow2 ¶
IsPow2 returns true if N is a perfect power of 2 (1, 2, 4, 8, ...) and false otherwise. Algorithm from: https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2
func MultiConvolve ¶
func MultiConvolve(X ...[]complex128) ([]complex128, error)
MultiConvolve computes the discrete convolution of many arrays using a hierarchical FFT algorithm that successfully builds up larger convolutions. This requires allocating up to 4*N extra memory for appropriate 0-padding where N=sum(len(x) for x in X). Takes O(N*log(N)^2) run time and O(N) additional space.
This is much slower and takes many more allocations than FastMultiConvolve below, but has a smart planner that handles disproportionate array sizes very well. If all your arrays are the same length, FastMultiConvolve will be much faster.
func RoundFloat64Array ¶
func RoundFloat64Array(x []float64)
RoundFloat64Array calls math.Round on each entry in x, changing the array in-place
func ZeroPad ¶
func ZeroPad(x []complex128, N int) []complex128
ZeroPad pads x with 0s at the end into a new array of length N. This does not alter x, and creates an entirely new array. This should only be used as a convience function, and isn't meant for performance. You should call this as few times as possible since it does potentially large allocations.
func ZeroPadToNextPow2 ¶
func ZeroPadToNextPow2(x []complex128) []complex128
ZeroPadToNextPow2 pads x with 0s at the end into a new array of length 2^N >= len(x) This does not alter x, and creates an entirely new array. This should only be used as a convience function, and isn't meant for performance. You should call this as few times as possible since it does potentially large allocations.
Types ¶
type InputSizeError ¶ added in v1.2.1
InputSizeError represents an error when an input vector's size is not a power of 2.
func (*InputSizeError) Error ¶ added in v1.2.1
func (e *InputSizeError) Error() string
Source Files
Directories