somewhere to talk about random ideas and projects like everyone else



Cooley-Tukey FFT + DCT + IDCT in under 1K of Javascript 30 May 2015

Technically this is a Hough transform and isn't at all related to the FFT*, but it looks a lot cooler than any of the actual FFT/DCT pictures I have, so I might as well stick it here

Almost a year ago, I wrote a simple script for computing perceptual hashes in Javascript (it’s going to be part of a forthcoming Naptha feature which allows it recognize source images for memes and do perfect inpainting). One step of the process is computing the 2D Discrete Cosine Transform of a shrunken version of the image.

The problem is that step was kind of ridiculously slow, and it’s not really hard to see why: there’s a series of four nested for loops— because that’s the obvious naive way for computing the DCT.

In practice, it’s actually not all that bad because you only have to do it once per image, and the dimensions of the source image are a fixed 32x32. But it still felt pretty bad, so when I was looking over the code again earlier this week, I tried doing some research to figure out a faster way to do the DCT.

Surely you’d imagine that there have to be extraordinarily efficient implements of the DCT out there, given that it’s the very foundation of JPEG out there. And you’d be right, but they’ve generally unrolled the butterfly into a series of bit-shifts which are quite unlikely to generalize beyond the 8x8 block size.

I’m reasonably confident that FFTW3 has a fast DCT implementation which also is capable of generalization, but it seems buried within quite a lot of code.


This isn’t a super performant implementation, but it’s not horrendously slow and it doesn’t use recursion. It’s probably pretty trivial to make it quite a bit faster by precomputing sine and cosine tables. This uses the standard Cooley-Tukey radix-2 decimation-in-time algorithm, which means it only works for one dimensional arrays with a length which is a power of two.

It doesn’t check that the length is a power of two, it’ll just give you the wrong answer. You should definitely check that it’s true beforehand.

function miniFFT(re, im) {
    var N = re.length;
    for (var i = 0; i < N; i++) {
        for(var j = 0, h = i, k = N; k >>= 1; h >>= 1)
            j = (j << 1) | (h & 1);
        if (j > i) {
            re[j] = [re[i], re[i] = re[j]][0]
            im[j] = [im[i], im[i] = im[j]][0]
    for(var hN = 1; hN * 2 <= N; hN *= 2)
        for (var i = 0; i < N; i += hN * 2)
            for (var j = i; j < i + hN; j++) {
                var cos = Math.cos(Math.PI * (j - i) / hN),
                    sin = Math.sin(Math.PI * (j - i) / hN)
                var tre =  re[j+hN] * cos + im[j+hN] * sin,
                    tim = -re[j+hN] * sin + im[j+hN] * cos;
                re[j + hN] = re[j] - tre; im[j + hN] = im[j] - tim;
                re[j] += tre; im[j] += tim;

The transformation happens in place, so it’ll modify whatever arrays you pass in.

var re = [1, 2, 3, 4],
    im = [0, 0, 0, 0];
miniFFT(re, im);
console.log(re, im); // [ 10, -2, -2, -2 ] [ 0, 2, 0, -2 ]

Minified, it’s only 359 bytes. Unlike this other contender for the dubious prize of smallest javascript FFT implementation, it doesn’t require a special complex number library three times its size (though this doesn’t fit in a tweet— I’ll be really impressed if someone manages to do that).

I haven’t really golfed the code to the smallest size possible, but I think it’s at a reasonable balance of brevity while still being somewhat comprehensible.

It’s based on an in-place FFT from Princeton’s intro CS class Project Nayuki’s FFT.


Turns out that you can invert the FFT modulo a scaling factor just by swapping the real and imaginary arguments.

function miniIFFT(re, im){
    miniFFT(im, re);
    for(var i = 0, N = re.length; i < N; i++){
        im[i] /= N;
        re[i] /= N;


This is an implementation of a Type-II DCT using MiniFFT. For details about Makhoul’s algorithm for transforming a DCT into an FFT, see this post

function miniDCT(s){
    var N = s.length,
        K = -Math.PI / (2 * N),
        re = new Float64Array(N),
        im = new Float64Array(N);
    for(var i = 0, j = N; j > i; i++){
        re[i] = s[i * 2]
        re[--j] = s[i * 2 + 1]
    miniFFT(re, im)
    for(var i = 0; i < N; i++)
        s[i] = 2*re[i]*Math.cos(K*i)-2*im[i]*Math.sin(K*i);

Like MiniFFT, it operates in-place (well, not really, but it writes its output to the source array).

var arr = [3, 4, 1, 7];
console.log(arr); // [ 30, -5.09493566, 7.0710678118, -8.604744653 ]

It produces the same output as scipy’s fftpack, but Matlab’s DCT uses orthogonal normalization and produces a different result. However, it’s pretty simple to do it the Matlab way— just scale everything by 1/sqrt(2 * N) and divide the first element by sqrt(2).

function matlabDCT(arr){
    arr[0] /= Math.sqrt(2);   
    for(var i = 0, N = arr.length; i < N; i++) arr[i] /= Math.sqrt(2 * N);


I really considered renaming this series of functions into TinyFFT and friends because of the predicament of MiniIDCT— yeah, exactly— the horror— repeating I’s.

This is an implementation of a Type-III DCT, also known as the IDCT because it happens to be the inverse of a Type II DCT (frequently refered to as “The DCT”).

function miniIDCT(s){
    var N = s.length,
        K = Math.PI / (2 * N),
        im = new Float64Array(N),
        re = new Float64Array(N);
    re[0] = s[0] / N / 2;
    for(var i = 1; i < N; i++){
        var im2 = Math.sin(i*K), re2 = Math.cos(i*K);
        re[i] = (s[N - i] * im2 + s[i] * re2) / N / 2;
        im[i] = (im2 * s[i] - s[N - i] * re2) / N / 2;
    miniFFT(im, re)
    for(var i = 0; i < N / 2; i++){
        s[2 * i] = re[i]
        s[2 * i + 1] = re[N - i - 1]

This is based on Tom Grydeland’s IDL implementation of the IDCT.

Let’s start with a 8 element array of real numbers (DCT values).

[A, B, C, D, E, F, G, H]

From that it generates the corresponding complex values. Note that the real part is intact, and the complex part is the original array with its head chopped off and the rest of it flipped around and attached to a water balloon.

[A, B, C, D, E, F, G, H] - j[0, H, G, F, E, D, C, B]

Then the complex values are rotated by exp(i * pi / (2 * N)) to get spectral components. After an IFFT that gets transformed into:

[a, h, c, f, e, d, g, b]

It took me a while to see what was going on there, but the even indices are map to the first half of the results, and the odd ones map to the second half in reverse

Scrambled      a h c f e d g b
Even Indexed   a   c   e   g
Odd Indexed      h   f   d   b
Odd Reversed     b   d   f   h
Unscrabmled    a b c d e f g h

Muting a Casio W-201 Watch 25 September 2013


For the past four years, I’ve been using a Casio W-201 watch. It’s plastic and cheap and light, and there isn’t really much more I would ask for. I presume Douglas Adams would be rather disappointed by my fondness of digital watches, but I’m frankly just not smart enough to read an analog dial. I haven’t migrated to those fancy-schmancy smartwatches, and I don’t currently have any intention to part with my precious ticky thingy.

What’s ironic is that the one thing that annoys me about this watch is that sometimes it does, in fact, “tick”. It beeps, with the shrill piezoelectric sound that plagues anything with a four cent PCB. Whenever I switch its mode from military time to regular, or from clockface to stopwatch, I’m greeted by that hundred millisecond reminder that I have ears. And out of some odd sense of courtesy, or deep desire to be unnoticed, this really bothers me.

I may have been a tad disingenuous in saying that I’ve used the same watch for the past four years. Some time in the beginning of the span, I managed to lose my watch, and bought an exact replica. Well, it wasn’t quite the exact replica. The watch had the same model number, but the band that bore the Casio emblem seemed a different hue. Most irritatingly though, this replica made noises when the old one didn’t. At first I thought this was an edgy new feature that made things feel more responsive and tactile, but eventually I realized it was actually pretty annoying.

I distinctly recall the birth of a conspiracy- my subconscious irritation was percolating through neural pathways, assembling a notorious scheme to administer open-heart surgery on this diminutive timepiece to euthanize the noise, once and for all, under the noxious smother of a lead-tin alloy. But these fugitive fermentation of my mind took a backseat when I found my formerly missing watch limply lying on the edge of a basement table.

About a month ago, I had found myself in similar shoes. I had come onto campus with the sudden realization that my precious chronometer had vanished. I scoured the depths of the two pockets in my rather minimal backpack (I decided to pack light for senior year after lugging a monstrosity of a backpack for all of 11th grade), yet no plastic timekeeper was to be found.

Reluctantly, I located my contingency clock, and uneasily slid it onto my left wrist. But soon enough I had felt comfortable in the metaphorical transition of life which the watch represented. It’d be a new phase of my life, running at a different pace, in a new setting- I shouldn’t be encumbered by the gadgets of old.

They say all relationships suffer from a kind of honeymoon phase, where everything in the universe seems kept in perfect harmony. I celebrated my watch’s inaugural re-synchronization, meticulously ensuring that the deviation from NIST’s official US time was no more than a quarter-second. But as all quartz oscillators perceptively drift over time, my relationship with my lightless-sundial began to sour.


This edgy beeping noise began to perceptively evolve from neat to nuisance, and the long-lost scheme of silence started to surface. The final straw came when I had acquired a nifty petite set of mini-screwdrivers, ostensibly for eye-glass repair, courtesy of State Farm at the Career Fair. A particularly intractable case of post-midnight procrastination inevitably struck, leaving a desk strewn with digital watch-guts in its wake.

As I fumbled with how to trigger the precise reset code needed to get the watch to emerge from its disassembly-induced coma, I kept trying different permutations fitting some little spring in every nook and cranny I could find within the interior of the watch. As I haphazardly reassembled the watch, I noticed that the noise was gone, well, a rather significant caveat was that the screen would go black and the device would reset on every light flick of my wrist. From that, I realized that the spring must have been the connection between the ground and the piezoelectric buzzer- silencing the noise would be as simple as taking it out of the watch, rather than shoving it on top of the reset contact.

And as I began to appreciate the magnitude, or lack thereof, of insight gleaned from that epiphany, I came to realize the more protracted history of my first watch. When I had previously changed the battery on the original watch, I must have accidentally knocked out the most minuscule of springs, and simply overwritten the memories of the beep beforehand.

After all this time, the only thing that I had really wanted was to break something in the same way I had so many years prior. And I guess I might as well note as an epilogue that I found my original watch shortly thereafter while rifling through some cabinets. But I’ve embraced this new watch and all it symbolizes, perhaps ironically by physically handicapping it into the old one.