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

×

# Prerequisities for FFT?

 0 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 3★sandeep9 478●2●8●27 accept rate: 4%

 1 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. answered 18 Aug '15, 09:37 61●1●1●5 accept rate: 14%
 1 The pre-requisites for learning FFT are: $N^{th}$ Principal root of unity Groups and Fields Polynomials answered 25 Jan '17, 19:00 3.4k●19●43●77 accept rate: 16%
 1 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.) answered 26 Jan '17, 13:05 628●7 accept rate: 10%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• 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