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.
jcul · 2h ago
Really interesting, and surprising article though!
IceDane · 1h ago
Same problem here. Firefox on Android.
kragen · 1h ago
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.
userbinator · 5m ago
Sierpinski triangles are definitely a common sight in demoscene productions, to the point that they're acceptable in the smaller sizes, but others will think you're not good enough if that's all you do for a 64k or above entry.
marvinborner · 1h ago
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!
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.
But this is not using bitwise AND, just the Pascal's triangle approach. (Interestingly, you can reformulate that as a neighborhood-2 2-state 1-dimensional cellular automaton pretty easily; it occurs in a couple of different guises in Wolfram's catalog.)
Here's an ASCII-art version that uses AND as Michał describes:
32 value size : line cr size 0 do dup i and if bl else [char] # then dup emit emit loop drop ;
: pasand size 0 do i line loop ;
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.
You can pause the animation anytime by clicking the ‘■’ button and then step through the T coordinate using the buttons on either side of it.
[1] https://icefractal.com/articles/bitwise-fractals/
Apologies for a comment not related to the content, but it makes it difficult to read the article on mobile.
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.
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
"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!
https://m.youtube.com/watch?v=tRaq4aYPzCc
Just kidding. This was a fun read.
Here's an ASCII-art version that uses AND as Michał describes:
Running `pasand` then yields this:https://www.wolframscience.com/nks/