You are not logged in. Please login at www.codechef.com to post your questions!

×

Prerequisities for FFT?

Recently i have seen a lot of questions being asked on fast fourier transforms. I have tried to read and understand it from T. cormen's book(Introduction to algorithms) but i think it requires some other concepts of mathematics too and thus i was unable to proceed.Can anyone please tell me what are the prerequisities before learning fast fourier transforms?

asked 18 Aug '15, 07:36

sandeep9's gravatar image

3★sandeep9
4782827
accept rate: 4%


In Coreman, the explanation about the topic is sufficient enough to implement FFT, as it covers the required mathematics. Try reading it few times, you'll get clear understanding how the property of complex roots is utilized to yield 0(nlogn) time. If you still struggle then try reading about complex numbers and roots of unity (just basic required).

For implementation in C++ you can use Complex data type, also check out other people submissions and see how they have implemented.

You can read it more about it on link text, its in Russian, use google translate or Yandex Translator.

link

answered 18 Aug '15, 09:37

greendragons's gravatar image

3★greendragons
61115
accept rate: 14%

The pre-requisites for learning FFT are:

  • $N^{th}$ Principal root of unity
  • Groups and Fields
  • Polynomials
link

answered 25 Jan '17, 19:00

wittyceaser's gravatar image

2★wittyceaser
3.4k194377
accept rate: 16%

You just have to know polynomials and a bit of matrices.Got to youtube search for mit ocw 6.046 lectures and there is one lecture on FFT ( I think under divide and conquer).It is quite easy to understand(well, relatively atleast.)

link

answered 26 Jan '17, 13:05

rajarshi_basu's gravatar image

6★rajarshi_basu
6287
accept rate: 10%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×334

question asked: 18 Aug '15, 07:36

question was seen: 1,212 times

last updated: 26 Jan '17, 13:05