(Even before computers, such convolutions could be done using the fact that diffraction of light effectively performs Fourier transforms.)

This quantity is -1 for all nonzero m for PN sequences (so that all but the first component in Abs[Fourier[(-1) list ]] 2 are equal), but has mean 0 for truly random sequences.

If Mod[p, 4]  1 JacobiSymbol sequences also satisfy Fourier[list]  list .

Power spectra [of random processes] Many random processes in nature show power spectra Abs[Fourier[data]] 2 with fairly simple forms.

An example is the algorithm of Anatolii Karatsuba from 1961 for finding products of n -digit numbers (with n = 2 s ) by operating on their digits in the nested pattern of page 608 (see also page 1093 ) according to First[f[IntegerDigits[x, 2, n], IntegerDigits[y, 2, n], n/2]] f[x_, y_, n_] := If[n < 1, x y, g[Partition[x, n], Partition[y, n], n]] g[{x1_, x0_}, {y1_, y0_}, n_] := With[{z1 = f[x1, y1, n/2], z0 = f[x0, y0, n/2]}, z1 2 2n + (f[x0 + x1, y0 + y1, n/2] - z1 - z0)2 n + z0] Other examples include the fast Fourier transform (page 1074 ) and related algorithms for ListConvolve , the quicksort algorithm for Sort , and many algorithms in fields such as computational geometry.

The Gibbs phenomenon in Fourier analysis was noticed in 1898 on a mechanical computer constructed by Albert Michelson .

However, the nested structure of m in natural order allows evaluation in only about n Log[n] steps using Nest[Flatten[Transpose[Partition[#, 2] . {{1, 1}, {1, -1}}]] &, data, Log[2, Length[data]]] This procedure is similar to the fast Fourier transform discussed below.

As mentioned on page 1082 , the frequency spectrum Abs[Fourier[list]] 2 for a 1D random walk goes like 1/ ω 2 .

But now if one sets up a superposition of all these configurations, one can compute Mod[a # , m]& , then essentially use Fourier to find periodicities—all with a polynomial number of quantum gates.