Underscore Pi

This clever program written by Brian Westley calculates π by looking at its own area.  It is one of the winning entries of IOCCC in 1988.

#define _ -F<00||--F-OO--;
int F=00,OO=00;main(){F_OO();printf("%1.3f\n",4.*-F/OO/OO);}F_OO()
{
            _-_-_-_
       _-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
 _-_-_-_-_-_-_-_-_-_-_-_-_-_-_
  _-_-_-_-_-_-_-_-_-_-_-_-_-_
    _-_-_-_-_-_-_-_-_-_-_-_
        _-_-_-_-_-_-_-_
            _-_-_-_
}

Getting it to run

Because of an unusual use of the preprocessor, the program will not give correct results when compiled with modern gcc.

% gcc ./westley.c && ./a.out
(...warnings omitted)
0.250

One of the solutions is to use the -traditional-cpp parameter for gcc, as follows:

% gcc -traditional-cpp ./westley.c && ./a.out
(...warnings omitted)
3.141

Here we have it, a nice approximation of π.  But where do we get this value from?

How does it work?

We can ask gcc to perform only the pre-processing and not the actual compilation, by using the -E switch:

% gcc -traditional-cpp -E ./westley.c > expanded.c

This gives us a better view on the code, specifically the F_OO function.  The first line of the function shows us that the chains of minuses and underscores have been turned into something like this (newlines added for clarity):

-F<00||--F-OO--;
--F<00||--F-OO--;
--F<00||--F-OO--;
--F<00||--F-OO--;

We know that every _ is expanded by the preprocessor to -F<00||--F-OO--;.  The trick used here is that a minus before an underscore, -_, would change the expression to say --F<00||--F-OO--;, changing the negation into a pre-decrement.

The effect of the code above would be one decrement of OO and four decrements of F, as follows:

-F < 00 || --F-OO--; would first check if the negation of F is less than zero.  F has the value of zero at the beginning, so the condition is false.  Therefore, the second part is evaluated, decrementing both F and OO.  Now, both F and OO are equal -1 .

--F < 00 || --F-OO--; would first decrement F, and then check if it’s less than zero.  The condition is true now and the second part is not evaluated, so now F equals -2 and OO still equals -1.

Examining the code further, it is easy to notice that OO is decremented for every line and F for every occurrence of an underscore in the code.  It is easy to see now that F is the calculated area of the circle and OO is the diameter.

Now the code can compute the approximate value of π, from the calculated area and diameter of the circle:

printf("%1.3f\n",4.*-F/OO/OO);

A bit of math

The formula used here derived from the one for calculating a circle area from its diameter:

r = \frac{d}{2}

A = \pi r^{2} = \pi \big ( \frac{d}{2} \big) ^{2} = \pi \frac{d^2}{4}

Dividing both sides by \frac{d^{2}}{4}  , we get:

\pi = A \frac{4}{d^{2}}

An exercise for the reader

What would happen if you make the circle in the code bigger?

Advertisements

2 thoughts on “Underscore Pi

  1. Pingback: New top story on Hacker News: Underscore Pi – when M_PI from math.h is too mainstream; IOCCC winning entry – Tech + Hckr News

  2. Pingback: New top story on Hacker News: Underscore Pi – when M_PI from math.h is too mainstream; IOCCC winning entry – Technical Nair

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s