Live data from Hacker News

Using Fourier Transforms to Multiply Numbers

blog.robertelder.org

41–44 of 44 posts

Re: Using Fourier Transforms to Multiply Numbers

#41

Earlier quoted context omitted.

Yes that's true. But if you come at it looking at it as a sampled continuous signal and spectrum, you don't think of the FFT as fast polynomial multiplication. Neither viewpoint is wrong. Just different lenses for looking at different problems.

I think I still think of it that way. In EE you are convolving a filter with a signal in the time domain, which you can think of as a polynomial. Doing the fft, then a vector multiply +ifft accomplishes the same thing, but using the fft.

How can you think of a continuous time signal as a polynomial though? I don't know of a continuous time analogy. It seems like the polynomial only works for the discrete case. And FIR filter convolution is rarely computed by FFT in FPGAs (in stream applications).

Look at a system doing DSP for example. Let's say you have an input RF signal that goes into an analog band-pass filter, a mixer, an analog low-pass filter, a DAC, and a FPGA. The FPGA implements a FIR filter - lets say a Hilbert transform using a distributed arithmetic algorithm. You are getting envelope information out of the FPGA. There's no FFT anywhere in the FPGA to compute this filter output.

You are seeing some weird noise in your DSP output. You dig a little by looking at the output of the DAC and then look at the FFT magnitude log10. You see some suspicious spurs popping up, but at really strange discrete frequencies. You show the spectrum to an RF engineer, then you two go to the lab and put an analog spectrum analyzer on the input to the DAC. Sure enough, there are mixing products of your input carrier, mixer frequency, and sampling clock frequency. The weird spur frequencies make sense now - you are seeing folding of the mixing products from the sampling. You tweak the sampling clock to move the spur digital frequencies.

In that long but real world example, I don't see anywhere here where thinking of things in terms of polynomials would be helpful here. It's also going to lead to confusion of terminology with your RF engineer - they tend to think continuous.

Re: Using Fourier Transforms to Multiply Numbers

#42

Earlier quoted context omitted.

I think I still think of it that way. In EE you are convolving a filter with a signal in the time domain, which you can think of as a polynomial. Doing the fft, then a vector multiply +ifft accomplishes the same thing, but using the fft.

How can you think of a continuous time signal as a polynomial though? I don't know of a continuous time analogy. It seems like the polynomial only works for the discrete case. And FIR filter convolution is rarely computed by FFT in FPGAs (in stream applications). Look at a system doing DSP for example. Let's say you have an input RF signal that goes into an analog band-pass filter, a mixer, an analog low-pass filter,…

Sorry, I think I misspoke. I didn't mean that I think of it in those terms normally. working with RF everyday, I think of it as time and frequency domain in the sense that you were describing. But mathematically I could see how the polynomial makes sense. Also, I was only thinking about discreet time since we are talking about the fft.

Re: Using Fourier Transforms to Multiply Numbers

#43

Man, is there anything Fourier Transforms can't do? For a music project in college, I created a book of Hammond Organ presets by taking slices of samples from actual instruments and running FTs on them, then finding the best approximation in Hammond drawbar notation. The fact that it worked so well was such a satisfying experience that I managed to make 100+ combinations.

I sort of did the reverse for a song once, I used FFT to analyze a recording of a drawbar organ I wanted to mimic, then turned that into a ZynAddSubFX additive synthesis preset.

This is where I started, actually! I wondered how far back I could go though, and the Hammond B3 worked extremely well.

Re: Using Fourier Transforms to Multiply Numbers

#44

Earlier quoted context omitted.

> Anyway, do competitive programmers tend to program everything from scratch, or is there another reason they don't just use GMP? I think directly using algorithms and programs implemented by others would be considered cheating (and these libraries are not presented on the server which checks your answer anyway). In competitive programming, participants compete their own ability and knowledge to implement algorithms.

In C++ thanks to complex the implementation is short see https://ideone.com/tbHUN7

C99 has complex, too. I think most competitive programming contests are now using C99, finally.
Post reply on HN