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:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <complex.h>
#include <math.h>
#include <fftw3.h>
 
/*
 * fourierfit.c:
 * Fits a series of sines/cosines onto a series of character values from a
 * string.
 *
 * Copyright (c) 2008, Jan Krueger <jast@heapsort.de>
 *
 * This program is free software: you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation, either version 3 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */
 
/*
 * Compile like this:
 * cc -o fourierfit -lm -lfftw3 fourierfit.c
 */
 
/*
 * Precision of output function (in digits after decimal point).
 * Yes, it's a string. printf much?
 */
#define PRECISION "3"
/* Names of cos/sin functions to use in output */
#define COSNAME "cos"
#define SINNAME "sin"
/* Name of function variable */
#define FNAME "t"
 
/* Don't change below here etc. */
 
#define PREC_FORMAT "%."PRECISION"f"
const char *cos_format = " %c "PREC_FORMAT"*"COSNAME"("PREC_FORMAT"*"FNAME
	")";
const char *sin_format = " %c "PREC_FORMAT"*"SINNAME"("PREC_FORMAT"*"FNAME
	")";
 
void format_term(const char *f, double d, int p, int N)
{
	printf(f, (d >= 0 ? '+' : '-'),
		fabs(d), /* scale of function */
		(double)p * M_PI * 2.0 / (double)N /* scale of parameter */
	);
}
 
int main(int argc, char **argv)
{
	int N;
	int odd;
	int i;
	double *in;
	fftw_complex *out;
	fftw_plan p;
	if (argc != 2) {
		puts("Syntax: fourierfit <string>");
		exit(1);
	}
	N = strlen(argv[1]);
	odd = N % 2;
 
	in = fftw_malloc(sizeof (double) * N);
	out = fftw_malloc(sizeof (fftw_complex) * N);
 
	p = fftw_plan_dft_r2c_1d(N, in, out,
		FFTW_ESTIMATE | FFTW_DESTROY_INPUT);
 
	/* Fill in array */
	for (i = 0; i < N; i++) {
		in[i] = (double) argv[1][i];
	}
 
	fftw_execute(p);
	fftw_destroy_plan(p);
	fftw_free(in);
 
	/* "DC" */
	printf(PREC_FORMAT, creal(out[0])/N);
 
	for (i = 1; i <= (N-1)/2; i++) {
		format_term(cos_format, 2.0*creal(out[i])/N, i, N);
		format_term(sin_format, -2.0*cimag(out[i])/N, i, N);
	}
	/* Nyquist component */
	if (!odd) {
		format_term(cos_format, creal(out[N/2])/N, N/2, N);
	}
	printf("\n");
	fftw_free(out);
	exit(0);
}

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.524*t) – 0.195*sin(0.524*t) – 17.167*cos(1.047*t) + 22.805*sin(1.047*t) – 5.000*cos(1.571*t) – 1.833*sin(1.571*t) + 8.667*cos(2.094*t) + 19.630*sin(2.094*t) – 7.951*cos(2.618*t) – 1.638*sin(2.618*t) + 10.917*cos(3.142*t)

16 responses to this post

  1. […] HOWTO: encode a string into a complicated-looking trigonometric function entra en más detalles teóricos y escribe un programa en C que emplea análisis de Fourier para encodificar el texto. […]

  2. DK says:

    HOWTO: encode information with a tad more information on the output thant on the input. Whoa. Incredible.
    Why not take directly the ascii codes of the letters? I can do it too. Check it out:
    f(x)=89*x^1+111*x^2+17^*x^3… and so on…

  3. Jan says:

    Are you sure that works? As I see it, in that case, f(0) = 0, f(1) = (large number), f(2) = (even larger number) etc. The whole point of the output function generated by my code is that f(i) = (ASCII code of (i+1)th letter).

    As for the reason I use sines and cosines rather than a polynomial (using classic interpolation methods), the resulting function would very likely have a lot less smooth behaviour between the data points. This is a well-known problem with polynomial interpolation and the reason why things like splines are often used instead. The above function, anyway, is a lot easier to work with than, for example, splines (since a spline is actually a couple of partial functions, it’s a bit difficult to calculations on), and notice how I never said there was much of a point to the whole exercise. ;)

  4. Richard Kiss says:

    It works!

    $ python

    >>> def f(t): return 93.083 – 10.549*cos(0.524*t) – 0.195*sin(0.524*t) – 17.167*cos(1.047*t) + 22.805*sin(1.047*t) – 5.000*cos(1.571*t) – 1.833*sin(1.571*t) + 8.667*cos(2.094*t) + 19.630*sin(2.094*t) – 7.951*cos(2.618*t) – 1.638*sin(2.618*t) + 10.917*cos(3.142*t)

    >>> ”.join((chr(f(x)+.5) for x in range(12)))
    ‘Hello world!’

  5. […] HOWTO: encode a string into a complicated-looking trigonometric function […]

  6. […] HOWTO: encode a string into a complicated-looking trigonometric function […]

  7. Michael Pederson says:

    no way, pix pls

  8. Michael Pederson says:

    Just kidding. Here are some:

    http://img406.imageshack.us/img406/1606/helloworldls5.jpg
    http://img515.imageshack.us/img515/8141/helloworldoverflownk9.jpg

    Um, I know it’s not necessary these days, but I noticed your strings aren’t null-terminated.

  9. Jan says:

    That’s the joy of C string constants which, in this form, automatically get null-terminated. It’s almost like a high-level language! As far as I know (which, admittedly, isn’t very far), this has always been so.

    Oh, and thanks for adding pretty pictures to this page.

  10. […] HOWTO: encode a string into a complicated-looking trigonometric function This was written by Wayne. Posted on Tuesday, April 15, 2008, at 1:32 pm. Filed under Uncategorized. Bookmark the permalink. Follow comments here with the RSS feed. Post a comment or leave a trackback. […]

  11. Dynelle says:

    do you have a demo online for this? thanks! i would be glad if u visit my Artikelverzeichnis. but u need understood german :)

  12. Dueces says:

    I tried running the program but the compiler made some error. Do you have already compiled .exe file demo?

  13. C. Laeuse says:

    Back in university, we used it for dealing with AC analysis!

  14. Sunil Ram says:

    Can’t understand all this:( May be not my field

  15. Jan says:

    Dueces, sorry, no. I don’t even have a decent compiler for Windows. I’m one of those insane Linux users. ;)

  16. Ryan says:

    It’s not working for me too:(