Discrete Fourier Transform

Posted3 months agoActive3 months ago

pykello

92 points

24 comments

nima101.github.ioTech/sciencestory

calmmixed

Debate

40/100

Discrete Fourier TransformFftSignal Processing

Key topics

Discrete Fourier Transform

Fft

Signal Processing

A blog post on the Discrete Fourier Transform (DFT) sparks a discussion on its implementation, applications, and related mathematical concepts, with commenters sharing their experiences and insights.

Snapshot generated from the HN discussion

Discussion Activity

Active discussion

First comment

Peak period

Day 5

Avg / period

Comment distribution24 data points

Loading chart...

Based on 24 loaded comments

Key moments

01Story posted
Sep 30, 2025 at 1:46 AM EDT
3 months ago
Step 01
02First comment
Oct 3, 2025 at 9:24 PM EDT
4d after posting
Step 02
03Peak activity
11 comments in Day 5
Hottest window of the conversation
Step 03
04Latest activity
Oct 12, 2025 at 5:46 AM EDT
3 months ago
Step 04

Generating AI Summary...

Analyzing up to 500 comments to identify key contributors and discussion patterns

Discussion (24 comments)

Showing 24 comments

tverbeure

3 months ago

1 reply

I almost always prefer text over video, but this video on the same subject is fantastic: https://www.youtube.com/watch?v=h7apO7q16V0. I watch it at least once every year.

Also, the title of the blog post (and by extension this HN post) is IMO not really correct: it's not about the DFT but specifically about the FFT.

majorchord

3 months ago

2 replies

Not going to lie, I have always been fascinated by the fourier transform, but I had to stop this video after less than 2 minutes in because it went way over my head... "a context you are all familiar with: polynomial multiplication"... um no, I have zero clue what that is, sorry. Also the speaker seems to have some sort of speech pathology that unfortunately bothers me.

tverbeure

3 months ago

Polynomial multiplication is something I learned in 8th grade?

lomase

3 months ago

I like this 3Blue1Brown video about what he calls the almost-fuerier transform:

www.youtube.com/watch?v=spUNpyF58BY

aeve890

3 months ago

1 reply

>I’ve worked on ads at Meta, Snap, and Nextdoor. I also consult companies on building ads. If you are building your ad stack, feel free to reach out — let’s chat!

Hmmm

IMTDb

3 months ago

3 replies

Not sure I get your point here

lispisok

3 months ago

1 reply

Do we really need yet another blog post about Fourier transforms that's really just self-promotion on HN?

tverbeure

3 months ago

What self-promotion? This was posted to HN by someone who had a long history of posting lots of links, with no obvious connection to the writer of the blog post.

As for yet another Fourier related post, shall we talk about AI instead?

aeve890

3 months ago

1 reply

Is this not the stereotypical big tech employee everyone love to bash here when the topic of advertising comes out? I've read thousand of comments about the morality of people working in that industry. Well, here's one.

I hope it helps.

dvfjsdhgfv

3 months ago

And actually, you can observe the values in action here:

https://nima101.github.io/adsopt

lomase

3 months ago

After careful consideration I think the point of aeve890 is that the advertisment industry sucks big time.

lomase

3 months ago

1 reply

Feels like an article wrote from somebody who knows a lot about the FFT for people who already knows a lot about the FFT.

dkjaudyeqooe

3 months ago

All mathematic exposition feels that way.

DecentShoes

3 months ago

1 reply

From what I've read about it all in the past, I feel like my intelligence level sits precisely between DCT and DFT. I seem to be able to mostly get Discrete Cosine Transform, but when confronted with Discrete Fourier Transform my brain simply shuts off and melts.

throw_away_8080

3 months ago

If you wanted to multiply two polynomials f and g of degree n, you could do distribution and the do n squared multiplications. Instead, evaluate the two separate polynomials at 2n special points, multiply the results pointwise, and then interpolate. The magical part is there are some specific points which speed up the evaluation and interpolation steps using a divide and conquer type algorithm.

dkjaudyeqooe

3 months ago

2 replies

Somewhat off topic rant, but am I the only one who find mathematical notation unnecessarily obtuse?

The bit that gets me is defining degree as n-1. For someone without a mathematical background, it takes a bit of pondering to figure out that you have to define n as one more than the actual degree, the opposite of what seems natrual. My mind at least just wants to think about n as the degree, and use n+1 as the last index. To me it seems aggressively unintuitive.

I guess you want to align the coefficient numbers but would it be a sin to define another index c = n-1 for that purpose?

But I'm a mathematical lightweight and maybe mathematical thinking is all about this. Perhaps some greater talent can correct my thinking.

defrost

3 months ago

Fence post and rail is "off by one", two fence posts are joined by one rail, N fence posts are joined by N-1 rails, and this polynomial order and defining coefficients discussion has that in common.

Two points define a line, a polynomial of degree 1. A polynomial with 2 coefficients, ax + b.

Three points give us a quadratic, a polynomial of degree 2 with three coefficients, ax^2 + bx + c.

N points gives us a polynomial of degree N-1 with N coefficients.

Indexing coefficients by their associated power of X seems natural to some.

A(N-1).X^(N-1) + ... A(1).X^1 + A(0).X^0 (where X^0 == 1)

are the N indexed coefficients of a generic polynomial of order N-1.

notrealyme123

3 months ago

By giving it a quick read I saw that the have n data points where a polynomial of n-1 degrees provides a useful fit in the sense of this blog post.

Every field has its own language to speak. And shouting into the field from "outside" that they should change is not polite.

E.g * if you redefine c = n-1 the connection between number of points and dimension is lost. * c ist very often used as a constant Skalar. E.g as the speed of light. Using it as a dimension of a problem is quite unintuitive.

raluk

3 months ago

1 reply

How much is fft used for AI? Seems that attention and convolution could benefit from this.

KISHNUVADAM

3 months ago

There are architectures, such as FNO, that utilize FFTs within them. These are particularly popular in deep learning weather prediction problems.

teo_zero

3 months ago

While I do understand that O(n²) complexitity is frowned upon, I wonder how big should n be before n² multiplications are worse than nlogn loops which include several complex multiplications, complex exp, and various array reshapes...

e-khadem

3 months ago

I first learned about FFT in highschool to solve competitive programming problems, and it was, let's say, useful for that. But then I started studying EE, and after learning more about the different types of Fourier transform, I started respecting the humble DFT matrix much more. I believe there is big gap of understanding between considering FFT as a cool algorithm for multiplying polynomials (or doing a circular convolution), and considering the transform as obtaining an eigenvalue representation of linear systems. The latter might not be as fruitful in the software engineering per se, but is the backbone of understanding the Fourier Transform for EE.

amirhirsch

3 months ago

If you are doing polynomial multiplication and want exact integer convolution then you can’t leave the precision of your FFT up to chance so the alternative to an FFT over complex roots of unity is to use something called a Number Theoretic Transform (NTT) that relies on nth roots of unity in finite integer rings

pixelpoet

3 months ago

TeX tip: it's \log, not log (ditto sin, cos, etc)

View full discussion on Hacker News

ID: 45422315Type: storyLast synced: 11/20/2025, 12:29:33 PM

Want the full context?

Jump to the original sources

Read the primary article or dive into the live Hacker News thread when you're ready.

Open link View on HN