Sorry, I'm not accusing you of anything. By strided accesses I mean when you access elements of an array sequentially using some step size. Think loops with `i += stride` instead of `i++`. In the wikipedia pseudocode this is done implicitly using the 's' parameter. Notice that, in the version you implemented, you split the input into even and odd parts explicitly; you can achieve the same end by accessing the input array in a certain order as you are performing the mathematical operations. This is what the wikipedia pseudocode does. If you've seen other versions of the FFT with a bit reversal step, this is also where that comes in.
Check this out (javascript):
function permute1(x) {
if (x.length == 1) return x;
let even = [];
let odd = [];
for (let i = 0; i < x.length; i += 2) {
even[i / 2] = x[i];
odd[i / 2] = x[i + 1];
}
return [].concat(permute1(even), permute1(odd));
}
function permute2(x, offset, stride) {
if (!offset) offset = 0;
if (!stride) stride = 1;
if (stride >= x.length) return [x[offset]];
return [].concat(permute2(x, offset, stride * 2), permute2(x, offset + stride, stride * 2));
}
function permute3(x) {
let result = [];
for (let i = 0; i < x.length; i++) {
let k = i;
// pretend 32-bit ints
k = ((k >> 1) & 0x55555555) | ((k & 0x55555555) << 1);
k = ((k >> 2) & 0x33333333) | ((k & 0x33333333) << 2);
k = ((k >> 4) & 0x0F0F0F0F) | ((k & 0x0F0F0F0F) << 4);
k = ((k >> 8) & 0x00FF00FF) | ((k & 0x00FF00FF) << 8);
k = ( k >> 16 ) | ( k << 16);
k = k >> (64 - Math.log2(x.length));
if (k < 0) k += x.length; // fix up due to signed ints
result[i] = x[k];
}
return result;
}
For arrays with power of two sizes, these perform the same permutation (but fail differently for non power of two sizes). Note that, with permute1, we effectively iterate over the entire input log2(n) times, so this is an O(nlogn) algorithm!
edit: also, i think i may have misunderstood the relationship between your js version and your lambdatalk version. They seem to be the same to me?