Talk:Fast folding algorithm

Computing Stub‑class

	This article is within the scope of WikiProject Computing, a collaborative effort to improve the coverage of computers, computing, and information technology on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.ComputingWikipedia:WikiProject ComputingTemplate:WikiProject ComputingComputing
Stub	This article has been rated as Stub-class on Wikipedia's content assessment scale.
???	This article has not yet received a rating on the project's importance scale.
	This article has been automatically rated by a bot or other tool as Stub-class because it uses a stub template. Please ensure the assessment is correct before removing the `\|auto=` parameter.

I can't find a good description of this algorithm on the net, so I've started my own. You'll notice it's got a big hole where all the technical detail should be! Contributions welcome ...

How it works

I implemented an FFA in python some time ago, so I can give a rough description of how it works.

During one pass of the FFA, all periods between n samples and n+1 samples are folded at once. The key idea is to divide the time series into m nonoverlapping blocks of n samples. Then the period-n profile is obtained by simply adding all the blocks. For a period between n and n+1, if one were simply folding the data, one would accumulate the profiles, but because the period is slightly longer than n, the phase would drift slightly. When the phase was wrong by one bin, you would begin cyclically shifting profiles to compensate for the drift. Thus to look at all possible periods, you should look at many different sequences of cyclic shifts. But the set of folds of m periods can be obtained from the set of folds of m/2 periods on the first and second halves by combining them both with and without shifting. So there's a divide-and-conquer algorithm.

In a way, this is very much like an FFT algorithm where the complex values have been replaced by profiles and the multiplication by "twiddle factors", roots of unity, has been replaced by cyclic shifts. —Preceding unsigned comment added by 65.95.19.27 (talk) 07:33, 21 March 2010 (UTC)[reply]