I’m an ethusiastic promoter of the C language. One of the outmoded cultural phenomena associated with C are bit-twiddling hacks: a collection of brain-teasers that implement improbably complex algorithms using bitwise arithmetic. They are often developed under the guise of code optimization, but they mostly serve to impress your friends and confuse enemies.
I have also previously written about fractals; they’re pieces of mathematical curiosa that enjoyed a near-mythical status in 1980s, but are no longer talked about in polite company. One of the better-known fractals is the Sierpiński triangle. It is constructed by taking an ordinary triangle and then successively removing the middle one-fourth from what’s left:
The fractal has some interesting properties; most notably, the surface area decreases by 25% in each iteration while the perimeter increases by 50%, so the respective limits are 0 and ∞. This is despite the figure retaining the same overall footprint as the starting triangle.
Anyway — there is this astonishingly simple bit-twiddling hack that somehow produces the Sierpiński triangle (demo):
#include#include #define LEN (1
19 Comments
jcul
I can't dismiss the cookie popup on this page. After rejecting or accepting cookies it reloads and reappears.
Apologies for a comment not related to the content, but it makes it difficult to read the article on mobile.
peterburkimsher
Wolfram did a lot of research into cellular automata, and the Sierpinski Triangle kept showing up there too:
https://www.wolframscience.com/nks/
jesuslop
You get those also doing a Pascal triangle mod 2, so a xor. Is a zoom-out fractal as oposed to Mandelbrot set.
dvt
Just a heads up, all (binary?) logical operators produce fractals. This is pretty well-known[1].
[1] https://icefractal.com/articles/bitwise-fractals/
zX41ZdbW
Sierpinski also sounds nice in music. Examples here: https://github.com/ClickHouse/NoiSQL
gjm11
Here's a possibly-too-highbrow explanation to complement the nice simple one in the OP.
"As everyone knows", you get a Sierpinski triangle by taking the entries in Pascal's triangle mod 2. That is, taking binomial coefficients mod 2.
Now, here's a cute theorem about binomial coefficients and prime numbers: for any prime p, the number of powers of p dividing (n choose r) equals the number of carries when you write r and n-r in base p and add them up.
For instance, (16 choose 8) is a multiple of 9 but not of 27. 8 in base 3 is 22; when you add 22+22 in base 3, you have carries out of the units and threes digits.
OK. So, now, suppose you look at (x+y choose x) mod 2. This will be 1 exactly when no 2s divide it; i.e., when no carries occur when adding x and y in binary; i.e., when x and y never have 1-bits in the same place; i.e., when x AND y (bitwise) is zero.
And that's exactly what OP found!
tomrod
I prefer mine au naturale 3-adic.
https://m.youtube.com/watch?v=tRaq4aYPzCc
Just kidding. This was a fun read.
kragen
The 31-byte demo "Klappquadrat" by T$ is based on this phenomenon; I wrote a page about how it works a few years ago, including a working Python2 reimplementation with Numpy: http://canonical.org/~kragen/demo/klappquadrat.html
I should probably update that page to explain how to use objdump correctly to disassemble MS-DOG .COM files.
If you like making fractal patterns with bitwise arithmetic, you'll probably love http://canonical.org/~kragen/sw/dev3/trama. Especially if you like stack machines too. The page is entirely in Spanish (except for an epilepsy safety warning) but I suspect that's unlikely to be a problem in practice.
marvinborner
Very cool! This basically encodes a quad-tree of bits where every except one quadrant of each subquadrant recurses on the parent quad-tree.
The corresponding equivalent of functional programming would be Church bits in a functional quad-tree encoding s.(s TL TR BL BR). Then, the Sierpinski triangle can be written as (Y fs.(s f f f #f)), where #f is the Church bit tf.f!
Rendering proof: https://lambda-screen.marvinborner.de/?term=ERoc0CrbYIA%3D
zabzonk
I draw these with paper and pen when I am extremely bored in meetings.
susam
I’d like to share some little demos here.
Bitwise XOR modulo T: https://susam.net/fxyt.html#XYxTN1srN255pTN1sqD
Bitwise AND modulo T: https://susam.net/fxyt.html#XYaTN1srN255pTN1sqN0
Bitwise OR modulo T: https://susam.net/fxyt.html#XYoTN1srN255pTN1sqDN0S
Where T is the time coordinate. Origin for X, Y coordinates is at the bottom left corner of the canvas.
You can pause the animation anytime by clicking the ‘■’ button and then step through the T coordinate using the ‘«’ and ‘»’ buttons.
anyfoo
Ah. Is that why LFSRs (linear feedback shift registers) and specifically PRBS generators (pseudo-random binary sequences) produce Sierpinski triangles as well?
PRBS sequences are well-known, well-used "pseudo-random" sequences that are, for example, used to (non-cryptographically!) scramble data links, or to just test them (Bit Error Rate).
I made my own PRBS generator, and was surprised that visualizing its output, it was full of Sierpinski triangles of various sizes.
Even fully knowing and honoring that they have no cryptographic properties, it didn't feel very "pseudo-random" to me.
modeless
Try this one liner pasted into a Unix shell:
It used to be cooler back when compilers supported weird K&R style C by default. I got it under 100 characters back then, and the C part was just 73 characters. This version is a bit longer but works with modern clang. The 73-character K&R C version that you can still compile today with GCC is:
MaxGripe
Sierpinski pirated it from Razor 1911 :)
lenerdenator
It's more likely than you think.
ChuckMcM
Y'all would really like https://www.gathering4gardner.org/ :-)
I tend to like lcamtuf's Electronics entries a bit better (I'm an EE after all) but I find he has a great way of explaining things.
msephton
I first saw these sorts of bitwise logic patterns at https://twitter.com/aemkei/status/1378106731386040322 (2021)
fiforpg
> the magic is the positional numeral system
— of course. In the same way the (standard) Cantor set consists of precisely those numbers from the interval [0,1] that can be represented using only 0 and 2 in their ternary expansion (repeated 2 is allowed, as in 1 = 0.2222…). If self-similar fractals can be conveniently represented in positional number systems, it is because the latter are self-similar.
jujuh
[dead]