Skip to content(if available)orjump to list(if available)

Implementing complex numbers and FFT with just datatypes (2023)

Implementing complex numbers and FFT with just datatypes (2023)

3 comments

·May 25, 2025
Visit

peter_d_sherman

Designing a custom datatype (which turns out to be based on balanced ternary trees!) to implement optimized FFT evaluation -- absolutely brilliant, IMHO!

Related:

https://news.ycombinator.com/item?id=38969053

LegionMammal978

Balanced ternary is an odd choice for signed integers, when it seems like two's-complement integers would work just as well here. (That is, start with primitives 0 = ...00000 and -1 = ...11111, and construct 2x and 2x+1 from those.)

aleph_minus_one

Or simply use binary (in the sense of digits 0,1) numbers with respect to base -2.