Speed up Fourier for Booleans

Question

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

Answer 1

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.

Answer 2

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.