Today’s glance at reddit.com yielded a blog posting by a fellow who calls himself “Poromenos” and who recently wasted his day by designing a function made up of sines and cosines that encode the string “Hello world!”. “Hey”, I immediately thought, “I can do that too! I’m an expert at wasting my day, after all.” Only I decided to go a step further and write a program that generates this sort of function. I’m lazy, remember?

### The theory

The magic behind Poromenos’s function is the Fourier theorem: any “mostly” continuous and periodic function can be expressed as a sum of sines and cosines. I’m not going to bore you with the details; suffice to say that this also works for sampled functions, i.e. discrete series of values.

There’s an algorithm called DFT (Discrete Fourier Transform) that takes a series of *N* complex sample values and generates a corresponding Fourier series which encodes the various sine/cosine coefficients in *N* complex output values. In the special case of real input values (which is an extremely common case), you can effectively throw away half of these output values and take the remaining *N* real/imaginary components, do a bit of magic, and end up with coefficients for a function of the form:

\[
f(t) = x_0 + x_1 \cos t + x_2 \sin t + x_3 \cos 2t + x_4 \sin 2t + \ldots
\]

Now, \(f(\frac{2 \pi n}{N})\) returns exactly the \((n+1)\)th character of the original string.

### Magic?

Glad you ask. No, it’s not really magic. In fact, I used the trigonometric interpolation polynomial from Wikipedia’s article on the Discrete Fourier transform (remember: it’s science if you copied it from Wikipedia!):

\[ p(t) = \frac{1}{N} \left( X_0 + X_1 e^{it} + \ldots + X_{\frac{N}{2}} (\cos \frac{N}{2} t) + X_{\frac{N}{2}+1} e^{(-\frac{N}{2}+1)it} + \ldots + X_{N-1} e^{-it} \right) \]Here, \(X_i\) are the complex values of the Fourier series, and \(e^{\pm it}\) transforms to \(\cos t \pm i \sin t\) according to Euler’s formula. The lone \(\cos\) term in the middle doesn’t show up if \(N\) is odd.

Now, if the Discrete Fourier Transform is fed with real values, it holds that

\[ X_i = X_{N-i}^\star \]or, in other words, the right half of the series is equal to the complex conjugates (\((a + i b)^\star = a - i b\)) of the left half in reverse order. Due to that, \(p(t)\) gets a lot simpler after a bit of reduction:

\[ p(t) = \frac{1}{N} \left( X_0 + 2 \mathrm{Re}\{X_1\} \cos t - 2 \mathrm{Im}\{X_1\} \sin t + \ldots + \mathrm{Re}\{X_\frac{N}{2}\} (\cos \frac{N}{2} t) \right) \]Again, the last term disappears for odd \(N\).

There we are, all magic has now been reduced to more or less tangible math.

### The program

I’ve written a small C program that takes as its input an arbitrary string and outputs the above function, modified a bit so that you can use the character index directly, i.e. `f(4)`

gives you the fifth character of the original string.

The generated function will typically have an error of less than 0.1 at each position (which goes away by rounding the values as Poromenos does it in his code). In fact, for the string “Hello world!”, the mean square error is less than 0.0019.

Because this isn’t exactly a serious project, I didn’t spend any time adding stuff like UTF-8 support. You’ll have to resign yourself to using ASCII or any 8-bit-per-character encoding.

Compiling the code requires that you have fftw3 installed (including header files).

You can download the code or look at it in all its syntax-highlighted glory:

1 | #include <stdio.h> |

### The example

For the sake of completeness, here’s the function for “Hello world!” as generated by the above code:

f(t) = 93.083 - 10.549

cos(0.524t) - 0.195sin(0.524t) - 17.167cos(1.047t) + 22.805sin(1.047t) - 5.000cos(1.571t) - 1.833sin(1.571t) + 8.667cos(2.094t) + 19.630sin(2.094t) - 7.951cos(2.618t) - 1.638sin(2.618t) + 10.917cos(3.142t)

This is an anti-social blog. No interactive commenting is available. Please feel free to send me an e-mail to leave feedback. If you wish to "participate", anonymously or not, please let me know in your e-mail if I can publish your feedback.