gp7
Joined 12 years ago
Joined 12 years ago
I think cursive used to serve the same function, which I basically conjecture from the fact that older people tend to be significantly better at reading cursive than me.
"When mass produced, the cost of self-tuning options will be small compared to the price of a quality piano. You might think that this would put piano tuners out of work but that will not be the case because the number of pianos will increase (because of this book), ..."
That's confidence in the method, right there.
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?
As an aside, I also find the non-recursive, breadth-first, form easy to derive thru a process of code transformations of the depth-first form; explanations that start breadth-first are somewhat bewildering
[1] https://cnx.org/contents/ulXtQbN7@15/Implementing-FFTs-in-Pr...
As someone who has basically no formal training in mathematics outside what's required for undergraduate computer science this is a big one. The first time I saw it I was blown away. Everyone who knows of it seems to treat it as natural as breathing, and not worth the exposition
One thing though--one of the best books I've read, Trefethen's ATAP, was written as a collection of .m files, which when run would produce a pdf of each chapter. The .m files were filled with small formatting details that were simply omitted from the generated book. The slides suggest something equivalent is not possible with notebooks. That's unfortunate.