Tuesday 17 December 2013

Infinite Snowflake

So it's close to the Christmas Holiday season, so I thought I would spend some time writing something seasonal.   My son, who is rather mathematically minded, was asking me about finding reoccurring digits in reciprocals of primes, for example 1/7, 1/11, 1/13 etc., and somehow this got me looking at the binary digits of Pi, and after a little more browsing around wikipedia onto the Thue-Morse binary sequence.

The Thue-Morse binary sequence starts with zero and one successively appends to the existing sequence the boolean compliment of the sequence so far.   One interesting feature is that a turtle graphics program can be written to control the turtle by feeding it the successive digits from the sequence so that:
  • A zero moves the cursor forward by a step
  • A one turns the cursor anti-clockwise by 60 degress (or pi/3 radians)
 ..and a Koch snowflake is drawn.  So, I've implemented this in C and obfuscated it a little just for fun:

#include<stdio.h>
#include <math.h>
#define  Q (1<<9)
#define M /**/for
#define E(b,a) {\
J q=1^(X+b)[3+Q*\
a];printf("%c%c%\
c",q,q,q);/*//*/}
int /*/*/ typedef
#define  W double
#define  z (Q<<5)

       J;J X[3+(Q              *Q)]
     ,t[z       ] ;J          main(
    ){ W         o= Q        >>1,V=
   o/5,           a=0;      M (1 [X
   ]=1;           X[1]         <z;X
  [1 ]             *=2)        for(
  X[2]             =0;X        [2]<
  X[1]             ;X[2        ]++,
  t[X[             2]+X        [1]]
  =1^t             [X[2        ]]);
  for(             0[X]        =0;X
  [0]<             3;0[        X]++
   )for           (X[2]        =0;X
   [2]<           z;X[         2]++
    )if(         t[X[          2]])
     a-=(       M_PI           /3.0
       );else{o+=          cos(a ); V+=

sin(a);X[3+( int)o+Q*(int)V]|=1;}printf(
"P6 %d %d 1 ",Q,Q);M(1[X] =0;X[1]<Q;X[1]
++)M(2[X]=0;X[ 2]<Q;X[2]++)E(2[X],X[1]);
return 0;} /* Colin Ian King 2013    */

To build and run:
gcc koch-binary.c -lm -o koch-binary 
./koch-binary | ppmtojpeg > koch-binary.jpg
And the result is a koch-snowflake:


The original source code can be found here. It contains a 512 x 512 turtle graphics plotter, a Thue-Morse binary sequence generator and a PPM output backend. Anyway, have fun figuring out how it works (it is only mildly obfuscated) and have a great Christmas!

No comments:

Post a Comment