A Reasonable Approximation

Latest posts

pi.py

There's a fairly well-known (as these things go) IOCCC entry ("westly.c") to calculate pi. It looks like this:

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

This prints 3.141, but you could get more digits by increasing the size of the circle (and changing the printf call).

I recently decided to port this to python. Here's the result:

class F:pass
s=F();_=F();
a=[];3;d=[];
A=(lambda:a.
append(1) or
s);D=(lambda
:d.append(1)
or s);l=len;
_.__neg__=(#
(lambda: _))
_.__sub__=(#
lambda x: (D
() and A()))
s. __sub__=\
lambda x:A()

-_
_-_-_-_
_-_-_-_-_-_
-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_-_-_-_
_-_-_-_-_-_-_-_-_
-_-_-_-_-_-_-_
_-_-_-_-_-_
_-_-_-_
-_

print"%.3f"%(8.*l(a+d)/l(d)**2)

The rest of this post is spoilers, so stop reading if you'd like to figure out what's going on for yourself.

How it works

The original C version works by counting the area of the circle in variable F, and its diameter in variable OO. Then it calculates $ π = {4A \over d^2} $, and prints this to 3 decimal places.

In more detail, _ is #defined to the statement F-->00 || F-OO--;. Since F is never positive in this program, by default this decrements both F and OO. But _ mostly appears in the context of -_, which becomes -F-->00 || F-OO--;, which will only decrement F (since F is negative whenever this statement occurs).

So the diameter of the ascii circle is counted as the number of lines, and its area is counted as the total number of _s it contains.

The python version uses a similar algorithm, but implemented differently. There's no preprocessor, so instead I use operator overloading. _ is a variable. Strings like _-_-_ count the total number of _s minus one into variable a, and count one into variable d. Then we use $ π = {8(a+d) \over d^2} $. 8 because it's only a semicircle, and $(a+d)$ because a is missing one _ per line.

How it does that is easy enough. _ has a __sub__ method which increments both a and d, and returns a new variable, s. s has a __sub__ method which just increments a and returns s. So a line like _-_-_-_ becomes s-_-_ becomes s-_ becomes s, and on the way it counts 1 into d and 3 into a.

We can also start a line with a -. -_ is defined to just return _, so it doesn't change anything. The top and bottom lines, -_, are just there for aesthetic reasons, they don't do anything at all.

As an implementation detail, a and d are actually lists. You can't call a += 1 in a python lambda, because python's lambdas are crippled (limited to a single expression, whereas a+=1 is a statement). So I have functions

A = lambda: a.append(1) or s
D = lambda: d.append(1) or s

which are slightly shorter, easier to lay out, and I think more in the spirit of the thing, than writing def A(): global a; a+=1; return s. (There's also some historical motivation. I originally used I = lambda x:x.append(1) or s and called I(a) and I(d). But I had difficulty fitting it into the square block, and in the course of experimentation ended up with what I have now. I could have gone with a and d as one-element arrays and def I(x): x[0]+=1; return s. But, whatever.)

Then in the final line, l(a+d) is just len(a+d), and summing arrays concatenates them so that's the same as len(a)+len(d). And l(d) is just len(d).

Here's an unobfuscated version of the header:

class F:pass
s = F()
_ = F()
a = []
d = []
A = lambda: a.append(1) or s
D = lambda: d.append(1) or s
l=len
_.__neg__ = lambda: _
_.__sub__ = lambda x: D() and A()
s.__sub__ = lambda x: A()

Incidentally, I only have one code block, class F:pass. When I decided to lay the header out in a rectangle, because yay geometric shapes, that line forced the width because I can't put anything before or after it. I wanted to go with F = type('', (), {}). But for some reason, that makes subtraction throw a TypeError:

>>> class F: pass
... 
>>> x = F()
>>> x.__sub__ = lambda x: 3
>>> x-x
3
>>> G=type('',(),{})
>>> y = G()
>>> y.__sub__ = lambda x: 3
>>> y - y
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: unsupported operand type(s) for -: '' and ''

I don't know why that happens.

You might be wondering, if I'm using the same algorithm as the C version, why is my semicircle so much larger than the original circle? That's an annoying quirk of mathematics.

With a circle, we have $ π = { 4a \over d^2 } $. For fixed $d$, we need an area $ a = { πd^2 \over 4 } $. But our area is an integer. So for fixed $d$, we can get an upper and lower bound on $π$, and we choose to display one of these. As we increase $d$, the bounds get tighter, but the lower bound doesn't move monotonically up, and the upper bound doesn't move monotonically down. $ d=16 $ is the first time that either bound gives us three decimal places, with an area of 201.

I had to go with a semicircle, because of significant whitespace, so I instead need an area $ a = { πd^2 \over 8 } $. With a diameter of 16, I could choose between an area of 100 or 101. These give π as 3.125 or 3.15625, which aren't even correct to two decimal places. If I wanted three decimal places, I needed a diameter of 32 and an area of 402. (My semicircle is actually 34 lines tall, but as noted above, the first and last lines don't do anything.)

Pedants will note that π rounded to three decimal places should actually be 3.142. I could have acheived that with a diameter of 34 and an area of 454. With a full circle, we could go for diameter 17 and area 227.

Posted on 18 January 2014

comments powered by Disqus