How to find the cost for implementing an fft

I wantto find the cost involved in implementing an fft that is the number of multiplications and additions as i have a task to compare it with normal DFT function to see the difference between the cost in implementing both the functions.

Answer 1

[David Young]

I guess you mean the cost involved in executing an fft. (The cost involved in implementing an fft would the amount you'd need to pay your team to write the code, I suppose.)

I guess by "normal DFT function" you mean the naive implementation, based on the DFT formula in textbooks. (Arguably, the FFT is the normal implementation, as some version of the FFT is always used in practice.)

Nit-picking aside, there are two things you could do:

1. Write a naive DFT function using the formula you'll find in any textbook, Wikipedia etc. Time it on some random data using cputime or tic and toc, and compare that time with the time taken using the fft function. If you do it properly (plenty of data, repeat the computation a number of times and take the fastest) then you will get a time roughly proportional to the number of multiplications and additions that have been executed. (Check your naive DFT function and fft give the same numerical results, to within a small tolerance.)
2. Analyse the two methods and work out how many multiplications and additions take place for each. You don't need to write any code for this - you just have to understand the algorithms. If you look up "computational complexity" you'll find textbooks and web pages that will help you greatly with this analysis. You'll find it easiest if you stick to the simplest kind of FFT which assumes that the data length is a power of 2.

[raj]

actually i want to know the number of multiplications and additions involved is it possible to calculate using the matlab function cputime or tic and tac??

Answer 2

[Walter Roberson]

You will have to analyze the code theoretically to say. It is not something that MATLAB can measure for you. cputime() and tic() and toc() and the profiler cannot give you this information. Neither can the High Precision Timer file exchange contribution.

Comparing to the native fft() call is not going to give you what you expect. You do not know how many multiplications and additions the native fft() uses, and you cannot find out.

All you are able to measure is execution time on the same inputs. That is not going to give you any way to compare fairly, as the native fft() is implemented through highly optimized C or C++ code (whereas your implementation will be in threaded interpreted MATLAB), and the native fft() will use multiple cores if available and if the problem is "large enough". You would be comparing implementation against implementation, rather than theory against theory.

[raj]

thanks a lot!!!