gofft

package module
v0.0.0-...-d3572dd Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 16, 2025 License: MIT Imports: 6 Imported by: 0

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 log^2 n)$ 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 $2^{25}$ 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/NovikovRoman/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/NovikovRoman/gofft
cpu: AMD Ryzen 9 5900X 12-Core Processor
Algorithm Size Iterations Time Throughput Memory Allocs
Naive Tiny (4) 43044590 149.1 ns/op 429.29 MB/s 64 B/op 1 allocs/op
Naive Small (128) 31022 199949 ns/op 10.24 MB/s 2048 B/op 1 allocs/op
Naive Medium (4096) 31 190195290 ns/op 0.34 MB/s 65536 B/op 1 allocs/op
ktye Tiny (4) 334951483 16.13 ns/op 3968.29 MB/s 0 B/op 0 allocs/op
ktye Small (128) 5627564 1064 ns/op 1923.91 MB/s 0 B/op 0 allocs/op
ktye Medium (4096) 98692 62663 ns/op 1045.86 MB/s 0 B/op 0 allocs/op
ktye Large (131072) 1436 4210853 ns/op 498.03 MB/s 0 B/op 0 allocs/op
mjibson/go-dsp Tiny (4) 1864420 2882 ns/op 22.21 MB/s 499 B/op 13 allocs/op
mjibson/go-dsp Small (128) 701971 8934 ns/op 229.24 MB/s 5572 B/op 18 allocs/op
mjibson/go-dsp Medium (4096) 33637 149844 ns/op 437.36 MB/s 164358 B/op 23 allocs/op
mjibson/go-dsp Large (131072) 993 6568056 ns/op 319.30 MB/s 5243432 B/op 28 allocs/op
mjibson/go-dsp Huge (4194304) 13 463206769 ns/op 144.88 MB/s 167772795 B/op 33 allocs/op
mjibson/go-dsp Massive (16777216) 3 2478991133 ns/op 108.28 MB/s 671089306 B/op 35 allocs/op
gonum Tiny (4) 123918710 50.12 ns/op 1276.84 MB/s 0 B/op 0 allocs/op
gonum Small (128) 2041134 2904 ns/op 705.33 MB/s 0 B/op 0 allocs/op
gonum Medium (4096) 42642 138597 ns/op 472.85 MB/s 0 B/op 0 allocs/op
gonum Large (131072) 870 6913295 ns/op 303.35 MB/s 0 B/op 0 allocs/op
gonum Huge (4194304) 15 359428827 ns/op 186.71 MB/s 0 B/op 0 allocs/op
gonum Massive (16777216) 4 1407001550 ns/op 190.79 MB/s 0 B/op 0 allocs/op
scientificgo Tiny (4) 66733696 77.52 ns/op 825.58 MB/s 128 B/op 2 allocs/op
scientificgo Small (128) 3675384 1653 ns/op 1238.64 MB/s 4096 B/op 2 allocs/op
scientificgo Medium (4096) 88891 60442 ns/op 1084.28 MB/s 131072 B/op 2 allocs/op
scientificgo Large (131072) 2526 2886025 ns/op 726.66 MB/s 4194304 B/op 2 allocs/op
scientificgo Huge (4194304) 26 228963535 ns/op 293.10 MB/s 134217728 B/op 2 allocs/op
scientificgo Massive (16777216) 4 1312125600 ns/op 204.58 MB/s 536870914 B/op 2 allocs/op
gofft Tiny (4) 1000000000 5.687 ns/op 11253.23 MB/s 0 B/op 0 allocs/op
gofft Small (128) 6283482 1037 ns/op 1974.64 MB/s 0 B/op 0 allocs/op
gofft Medium (4096) 120750 51886 ns/op 1263.07 MB/s 0 B/op 0 allocs/op
gofft Large (131072) 2596 2387875 ns/op 878.25 MB/s 0 B/op 0 allocs/op
gofft Huge (4194304) 27 265444115 ns/op 252.82 MB/s 0 B/op 0 allocs/op
gofft Massive (16777216) 5 1069123500 ns/op 251.08 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

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 

func IsPow2(N int) bool

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 NextPow2 

func NextPow2(N int) int

NextPow2 returns the smallest power of 2 >= N.

func Prepare deprecated 

func Prepare(N int) error

Prepare precomputes values used for FFT on a vector of length N. N must be a perfect power of 2, otherwise this will return an error.

Deprecated: This no longer has any functionality

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 

type InputSizeError struct {
	Context     string
	Requirement string
	Size        int
}

InputSizeError represents an error when an input vector's size is not a power of 2.

func (*InputSizeError) Error 

func (e *InputSizeError) Error() string

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.