# Is it true that convolving a 3x3 matrix and a Full HD image is slower with FFT?

Is it true that convolving a 3x3 matrix and a Full HD (1920×1080) image is slower with FFT, than with normal for-loops? Because you have to do zeropadding to get to a power of 2? (with the traditional Cooley-Tukey FFT for example)

Because when using the FFT, you have to zeropad the 3x3 kernel as well... log(1920*1080)/log(2) is roughly 21. That means I need 21 adds and 15.5 multiplies is 36.5 operations for each pixels. But I need to do 2 FFT and one IFFT. So, I need to multiply 36.5 by 3: 36.5*3=109.5 operations for each pixel?

When calculating the convolution directly using for-loops, you need 9 multiplications and 9 additions = 18 operations for each pixel.

I guess I made a mistake somewhere. One of those is '21 multiplies'... Please provide a better mathmatical proof.

• Please stop simultaneously crossposting on multiple forums! cs.stackexchange.com/questions/12217/…. Post on one forum or the other, and if your question doesn't get an adequate response after a couple of days request the moderator to move to the other forum. – Wandering Logic May 22 '13 at 17:29
• As @WanderingLogic says, please stop duplicate posting. It is against the spirit of the SE series of sites. Please choose one site, and ask there. If it's off-topic for the site, the moderators will move it. – Peter K. May 22 '13 at 17:41
• Re-opening after duplicate was removed from sister site. – Peter K. May 23 '13 at 11:40
• As well as not cross-posting, it might also be a good idea to stick to just the one user account. – Paul R May 23 '13 at 12:18