# Speed up Fourier for Booleans

I'm calculating a bit of the power spectrum of a two color cellular automaton using:

Abs[Fourier[#, FourierParameters -> {-1, -1}][[All, 1 ;; 100]] & /@
Transpose[CellularAutomaton[...]]]^2 // Total


Since I'm new to Mathematica, some trivial questions:

• Does it automatically optimize for the type of input data (just integers 0 and 1) or should I manually use Compile? Can I give it some hints about the input?

• Is Mathematica lazy enough to see that I only care about the first 100 frequencies and won't calculate the others? (the ones I care about are significantly less than the length of the input data, is there a better way to do this?)

This is to match a paper, everybody else seems to use this form which would be more efficient because it doesn't have to thread the Fourier over all columns:

CellularAutomaton[...] // Transpose // Total // Fourier // Abs

-
By sheer coincidence (or probably not) this Wolfram blog also deals with cellular automatons and power spectra (see the second app). – Sjoerd C. de Vries Apr 28 '12 at 14:00
Though Sjoerd's answer has already demonstrated this isn't done in practice, I think it's worth noting that there aren't really any general methods to compute partial FFTs that are significantly more efficient than just doing the whole FFT and then discarding the unwanted portion of the output. So even if Mathematica did realise you only wanted part of the output from the start, this isn't necessarily actionable information except for certain specific decimations. – Oleksandr R. Apr 30 '12 at 7:14

## 2 Answers

Most of your questions can be answered experimentally. You can find out a lot about Mathematica by just interactively playing and timing results. Let's see how it works out in this case:

does it automatically optimize for the type of input data (just integers 0 and 1)?

d1 = RandomReal[1, 10^7];

Fourier[d1]; // AbsoluteTiming // First

(*  ==> 1.0650609  *)

d2 = RandomInteger[1, 10^7];

Fourier[d2]; // AbsoluteTiming // First

(*   ==> 1.1050632 *)


So, no difference between integers and reals in this case. Note that Mathematica doesn't know no numerical Boolean values (0, 1), but only True and False and you can't perform a Fourier on that.

Is Mathematica lazy enough to see that I only care about the first 100 frequencies and won't calculate the others?

Mathematica has some clever optimizations going on under the hood, but this is not one of them. Compare the previous Fourier timing with this one:

Fourier[d1][[1 ;; 100]]; // AbsoluteTiming // First

(*  ==> 1.0740615  *)


The answer,therefore, is 'no'. The reason can be discovered easily, for instance, by using TracePrint

Fourier[{1, 2, 3, 4, 5}][[1 ;; 3]] // TracePrint

Fourier[{1,2,3,4,5}][[1;;3]]
Part
Fourier[{1,2,3,4,5}]
Fourier
{1,2,3,4,5}
{6.708203932 +0. I,-1.118033989-1.538841769 I,-1.118033989-0.363271264I
,-1.118033989+0.363271264 I,-1.118033989+1.538841769 I}
1;;3
Span
1
3
{6.708203932 +0. I,-1.118033989-1.538841769 I,-1.118033989-0.363271264 I
,-1.118033989+0.363271264 I,-1.118033989+1.538841769 I}[[1;;3]]

{6.708203932 +0. I,-1.118033989-1.538841769 I,-1.118033989-0.363271264 I}


As you can see, Part, the function lurking behind [[...]] is performed on the full output of Fourier, which itself, is fully unaware that pieces of its output will be picked away.

Can I give it some hints about the input?

Usually, no, you can't. Compile itself needs to know the types of its inputs, but most other Mathematica functions are just as happy with reals as with integers. Exceptions are, of course, functions that explicitly deal with integers like IntegerDigits.

Functions you write yourself can be typed. For instance,

f[x_Integer,y_Integer] := IntegerDigits[x][[y]]


only takes integers as arguments.

-

For Boolean/Binary data you may want to check into Hadamard/Walsh Transforms instead of Fourier, using Walsh functions (there is also a fast version of it). Also, there is more in the direction of Haar wavelets and the Mathematica Wavelet package.

Hope this helps.

-