Sierpinski Triangles
in Bitwise Logic

posted by Darryl on 27 May 2015

Below you can see a Sierpinski Triangle drawn in a canvas. What makes this particular Sierpinski Triangle interesting is that it's generated by setting the color of each pixel to a thresholded bitwise & on the coordinates of the pixel. Check out the source code to see the precise details of how this is drawn, or read below for a deeper discussion.

Scaling:
  Animation:

Cycle height:
  Animation:

Phase:
  Animation:

Sample ratio:
  Animation:

Threshold:
  Animation:

Operation:
   false
   nor
   not implied by
   not left
   not implies
   not right
   xor
   nand
   and
   iff
   right
   implies
   left
   implied by
   or
   truth

Explanation

So what's going on here? How does this come about? You might want to open up another instance of this page so you can have the image and the text side by side. Additionally, it helps to know that the canvas is 512 pixels on each side.

So let's consider first the fact that if we take two arbitrary integers and perform a bitwise operation on them, we could get any number up to one less than the maximum provided by the integer type's representation. That's usually some number around 232-1 or 264-1 or whatever. The specifics don't really matter.

If we simply take the bitwise & of the coordinates, and then threshold the result, so that any number more than 0 is set to 255 (the maximum value for an RGB color), we get the above image. So a pixel is black if the bitwise conjunction is completely false, and white if it's at all true. Out pops the Sierpinski Triangle. I learned about this from Grim, Mar, and St Denis' book The Philosophical Computer (check out this and this for relevant excerpts). After exploring the idea further, I found other interesting patterns beyond just Sierpinski triangles.

Incidentally, Grim was a professor of mine while I was an undergraduate at Stony Brook University, and if you ever have the chance to take a class with him, or hear a talk by him, I suggest you do. He's a cool guy, and dresses like someone out of the Old West (which made for a good Halloween costume that semester).

Let's now set the threshold to 0. The way this is set up, a threshold of 0 simply turns off thresholding. What you get now is a full greyscale image. You'll notice that the bottom right has a big white block. This isn't because there's no data there, just because all of the data should be greater than 255, so it all gets pinned to 255. If you lower the scaling to 0.5, each pixel's brightness will be reduced to 0.5 of the maximum and the bottom right will show up. You can animate the scaling factor with a positive or negative change.

You'll notice also that there is a cycle height parameter. The value of each pixel is modded (%) by this value before setting the pixel. This bounds the pixel's color range to at most the cycle height, but because its modded, it cycles. So the brightness of a pixel right now if you haven't changed anything else is really (x&y)%512. If we set the cycle height to 256, so that every pixel has a brightness in range of RGB colors, the bottom right of the image suddenly shows up.

If we keep lowering it, we notice something interesting happens: the bottom right corners of the four quadrants start getting eaten away by the gaps in a Sierpinski Triangle. Keep going, and it becomes apparent that actually those pixels are just being pushed down to the bottom of the color space by the modular arithmetic. When the cycle height is 0, this gets drawn as there being no cycle at all, so no modular arithmetic is happening, and the only clipping that occurs is due to color ranges.

At this point, it would help to have a picture visualizing these three aspects, so here we have a poorly drawn picture:

The interplay of the scaling (which changes the slope of the lines), the cycle height, and the clipping due to the RGB range, lead to this truncated sawtooth wave. Thresholding appropriately serves to turn it into a square wave. Lastly, the phase parameter shifts the whole wave left and right (in the code, this is achieved by shifting the underlying line up and down for certain reasons).

We also have this sample ratio thing, which is a multiplier on the coordinates so that if we have a sample ration of 2, and we draw the point (3,4), we actually compute the value for the point (6,8). This acts to scale the whole image, but because there's no anti-aliasing, it ends up producing an effect analogous to sample artifacts in audio processing (hence the name).

Finally, we can pick any of the 16 binary logical operators. The names are chosen to be in line with their normal logic gate names, where possible, or their normal logical operator names, or barring either of those, something relatively clear. "Left" and "right" are just operators returning either their left or right arguments, respectively. The operators are listed in order of their truth table's output, if you care to reconstruct the operators.

Some Interesting Images

There are some interesting places in the parameter space for this. For instance, picking the operation to be "and", set scaling to 1000, cycle height to 495, and threshold to 0, we get a variety of overlapping Sierpinski triangles at different scales and colors. If we now animate the phase with speed 10, we get a Sierpinskian symphony. Zooming out with a sample ratio of 32, reveals more of the symphony, with more visible pulsations.

Another interesting place in the parameter space has scaling set to 20000, cycle height to 1300, with the sample ratio back at 1. If we animate the phase now, we get these very sudden changes in the overall content of the image. But with scaling just 1 higher, at 20001, we now get smaller changes to the overall image as the phase changes. The changes now are limited to certain substructures in the image, like lines or squares.

It's also interesting to go back to scaling = 20000, set sampling ratio to 32, and and look at changes that occur when you increment scaling up to 20003. Similarly, if you set sampling ratio to 33, you get interesting, but qualitatively different, patterns. You also notice that while the images look similar when the sampling ratio is 1, regardless of whether scaling is 20000, 20001, 20002, or 20003, when the sampling ratio is 33, you get weird artifacting that produces some very different images. I'm especially fond of scaling = 20003 and sampling = 33, which reminds me of certain Native American weaving patterns.

Generalizations?

In the above code, we get the results of a truncated sawtooth wave and a square wave with modular arithmetic, thresholding, and the clipping from the RGB color space. But we could perfectly well use other kinds of function. Whatever we pick should probably be most interesting within the bounds set by the color space tho, and probably would need some periodicity to keep it from getting boring.

We could also use some other kind of mapping into color instead of just picking a greyscale value, which would give us some more flexibility with how we map values to colors, as well as what function we use above, because we have a large space to play with.

Other generalizations could be made to 3 dimensional space with ternary logical operators, which are much more numerous than binary ones (222 = 24 = 16 vs 223 = 28 = 256). Visualizing these higher dimensional variants would be tricky, but there's probably some interesting stuff lurking in there.

What about other representations of numbers? Why not use ternary numbers or quaternary, instead of binary? Those would also increase the number of logical operations that exist, possibly producing other more interesting ones.

If you have comments or questions, get it touch. I'm @psygnisfive on Twitter, augur on freenode (in #languagengine and #haskell).