Hacker News

Sierpiński Triangle? In My Bitwise and?

217 points by guiambros 10 months ago

66 Comments
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.

By susam 10 months ago
[deleted]

By 10 months ago
Munching squares!

By msarnoff 10 months ago
Shadertoy link: https://www.shadertoy.com/view/MllcW2
And, xor, and or are red, green and blue

By Recursing 10 months ago
Thank you for sharing. The third one has some kind of trippy 3d effect in the first seconds

By ttoinou 10 months ago
Gorgeous!

By kragen 10 months ago
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!

By gjm11 10 months ago
This elegantly explains why (x & y) == 0 produces Sierpinski triangles: it's equivalent to checking whether (x+y choose x) mod 2 equals 1, directly connecting bitwise operations to binomial coefficients.

By ethan_smith 10 months ago
i really love the result you quote about the carries. do you know where it has been applied by any chance?

By coderatlarge 10 months ago
I don't know of applications offhand, sorry. For me it's in the "appreciated for its own sake" category :-).

By gjm11 10 months ago
i can see that for sure. do you have a reference by any chance? chatgpt hallucinates various references given the result. knuth’s “concrete mathematics” might have it.

By coderatlarge 10 months ago
I don't know whether it's in Concrete Mathematics, but perhaps https://en.wikipedia.org/wiki/Kummer%27s_theorem will do?
(That page has a link to another beautiful theorem with a similar feel, Lucas's theorem: if p is prime, then (n choose r) mod p is the product of the (n_i choose r_i) where n_i and r_i are corresponding digits of n and r when written in base p.)

By gjm11 10 months ago
I checked: the result is in Concrete Mathematics, as exercise 5.36, but there is no attribution to Kummer there.
Incidentally, I found the name of the theorem (and the Wikipedia page about it) using a new kind of tool called a "search engine". It's a bit like asking ChatGPT except that it hardly ever hallucinates. You should try it! :-)

By gjm11 10 months ago
thank you! what an excellent and delightful related result as well :)

By coderatlarge 10 months ago
[deleted]

By 10 months ago
[deleted]

By 10 months ago
[dead]

By jujuh 10 months ago
Just a heads up, all (binary?) logical operators produce fractals. This is pretty well-known[1].
[1] https://icefractal.com/articles/bitwise-fractals/

By dvt 10 months ago
The change rate in binary notation is fractal.

By wang_li 10 months ago
It would be interesting to see how this generalizes to other bases.
Base 3 has nearly 20,000 operators, of which 729 are commutative.

By marginalia_nu 10 months ago
Yeah, I'm pretty sure as long as you have symmetry somewhere (e.g. a commutative operation), you'll get self-similar patterns.

By dvt 10 months ago
That's more or less, because binary numbers are already fractal.

By eru 10 months ago
Ask yourself why you added the “pretty well-known” phrase, and consider xkcd 1053.

By Timwi 10 months ago
Try this one liner pasted into a Unix shell:
```
  cc -w -xc -std=c89 -<<<'main(c){int r;for(r=32;r;)printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}'&&./a.*
```
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:
```
  main(c,r){for(r=32;r;)printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}
```
By modeless 10 months ago
Instructions unclear, machine rooted. :p

By Terr_ 10 months ago
Hey, at least it's not doing `curl | bash` like some people's installers do. It's only 109 characters, you can review that right? :-P

By modeless 10 months ago
For all I know, the whole thing might just be a very convoluted call to curl?

By eru 10 months ago
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.

By jcul 10 months ago
This might be a Firefox problem.
I have never seen it before, but today I have seen it in 3 or 4 sites linked from HN.
What has worked for me is to click "Accept all", then, after the pop-up reappears, click "Only necessary", which makes the pop-up disappear.
Clicking "Only necessary" without clicking before that "Accept all" has not worked. Likewise, clicking multiple times one of those options has not worked.

By adrian_b 10 months ago
Substack is kind of a weird site, but this newsletter in particular is worth subscribing to and getting in your email.

By jrockway 10 months ago
Same problem here. Firefox on Android.

By IceDane 10 months ago
Really interesting, and surprising article though!

By jcul 10 months ago
Same. Safari on iPhone.

By Jolter 10 months 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!
Rendering proof: https://lambda-screen.marvinborner.de/?term=ERoc0CrbYIA%3D

By marvinborner 10 months 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.

By kragen 10 months 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.

By userbinator 10 months ago
I reached a similar result when researching all possible "binary subpixel" configurations that would give a pixel its fuzzy value. Arranging the configurations in ascending order row-wise for one pixel and column-wise for the other, performing an intersection between the two pixels, and plotting against their resulting fuzzy value results in a sierpinski triangle.
(if interested, see fig 4.3, page 126 of my thesis, here: https://ora.ox.ac.uk/objects/uuid:dc352697-c804-4257-8aec-08...)
Cool stuff. Especially the bottom right panel, you might not have expected that kind of symmetry in the intersection when looking at the individual components.

By tpoacher 10 months ago
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.

By anyfoo 10 months ago
> 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.

By fiforpg 10 months ago
There are so many ways to produce sierpinski gaskets.
It you specify n points and the pick a new point at random, then iteratively randomly select (uniformly) one of the original n points and move the next point to the mid point of the current point and the selected point. Coloring those points generates a sierpinski triangle or tetrahedron or whatever the n-1 dimensional triangle is called

By pacaro 10 months ago
That's called a simplex :)
The same as in the simplex algorithm to solve linear programming problems.

By linschn 10 months ago
I programmed this on my TI-83 back in the day and spent many hours watching it generate triangles during boring classes.
You can generate many other fractals (e.g. fern shapes) in a similar way, though the transformations are more complicated than “move halfway to selected point”.

By CrazyStat 10 months ago
yes, those are called iterated function systems (IFS) fractals

By deadfoxygrandpa 10 months ago
I draw these with paper and pen when I am extremely bored in meetings.

By zabzonk 10 months ago
I first saw these sorts of bitwise logic patterns at https://twitter.com/aemkei/status/1378106731386040322 (2021)

By msephton 10 months ago
Wolfram did a lot of research into cellular automata, and the Sierpinski Triangle kept showing up there too:
https://www.wolframscience.com/nks/

By peterburkimsher 10 months ago
This one in particular: https://en.wikipedia.org/wiki/Rule_90

By GuB-42 10 months ago
Sierpinski also sounds nice in music. Examples here: https://github.com/ClickHouse/NoiSQL

By zX41ZdbW 10 months ago
Munching squares: https://tiki.li/show/#cod=VYxLCoAwDET3PcWsFWql4s7D1Fo/oBZqkf...

By tikili 10 months ago
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.

By ChuckMcM 10 months ago
It's more likely than you think.

By lenerdenator 10 months ago
I prefer mine au naturale 3-adic.
https://m.youtube.com/watch?v=tRaq4aYPzCc
Just kidding. This was a fun read.

By tomrod 10 months ago
You get those also doing a Pascal triangle mod 2, so a xor. Is a zoom-out fractal as oposed to Mandelbrot set.

By jesuslop 10 months ago

True. pas.f in Forth

    : .r u.r ;
    : position  ( row -- )  cr  33 swap 2 *  - spaces  ;
    : pas ( 0 ... 0 -- 0 ... 0 )    0 >r begin
    over + >r  dup 0= until
    begin  r> dup while  dup 4 .r  repeat  ;
    : pass  ( -- )    0 1 0    18 0 ?do  dup position  >r  pas  r>  1+  loop      drop  ;
    : pax  ( 0 ... 0 -- )  drop begin 0= until ;
    : pascal  ( -- )  pass pax ;

    pascal
    cr

The same mod2:

    : .r u.r ;
    : position  ( row -- )  cr  33 swap 2 *  - spaces  ;
    : pas ( 0 ... 0 -- 0 ... 0 )    0 >r begin
     over + >r  dup 0= until
     begin  r> dup while  dup 2 mod 4 .r  repeat  ;
    : pass  ( -- )    0 1 0    18 0 ?do  dup position  >r  pas  r>  1+  loop     drop  ;
    : pax  ( 0 ... 0 -- )  drop begin 0= until ;
    : pascal  ( -- )  pass pax ;

    pascal
    cr

A Forth for people in a hurry:

     git clone https://github.com/howerj/subleq
     cd subleq
     sed -i 's,0 constant opt.control,1 constant opt.control,g' subleq.fth
     gmake subleq
     ./subleq subleq.dec < subleq.fth > new.dec
     ./subleq new.dec < pas.f

By anthk 10 months ago

Output from `cr pascal` in GForth:

                                    1
                                  1   1
                                1   0   1
                              1   1   1   1
                            1   0   0   0   1
                          1   1   0   0   1   1
                        1   0   1   0   1   0   1
                      1   1   1   1   1   1   1   1
                    1   0   0   0   0   0   0   0   1
                  1   1   0   0   0   0   0   0   1   1
                1   0   1   0   0   0   0   0   1   0   1
              1   1   1   1   0   0   0   0   1   1   1   1
            1   0   0   0   1   0   0   0   1   0   0   0   1
          1   1   0   0   1   1   0   0   1   1   0   0   1   1
        1   0   1   0   1   0   1   0   1   0   1   0   1   0   1
      1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
    1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1
   1   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1 ok

By changing `4 .r` to `bl + dup dup dup emit emit emit emit` I get this:

                                      !!!!
                                    !!!!!!!!
                                  !!!!    !!!!
                                !!!!!!!!!!!!!!!!
                              !!!!            !!!!
                            !!!!!!!!        !!!!!!!!
                          !!!!    !!!!    !!!!    !!!!
                        !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                      !!!!                            !!!!
                    !!!!!!!!                        !!!!!!!!
                  !!!!    !!!!                    !!!!    !!!!
                !!!!!!!!!!!!!!!!                !!!!!!!!!!!!!!!!
              !!!!            !!!!            !!!!            !!!!
            !!!!!!!!        !!!!!!!!        !!!!!!!!        !!!!!!!!
          !!!!    !!!!    !!!!    !!!!    !!!!    !!!!    !!!!    !!!!
        !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
      !!!!                                                            !!!!
    !!!!!!!!                                                        !!!!!!!! ok

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 ;

Running `pasand` then yields this:

    ################################################################
    ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  ##  
    ####    ####    ####    ####    ####    ####    ####    ####    
    ##      ##      ##      ##      ##      ##      ##      ##      
    ########        ########        ########        ########        
    ##  ##          ##  ##          ##  ##          ##  ##          
    ####            ####            ####            ####            
    ##              ##              ##              ##              
    ################                ################                
    ##  ##  ##  ##                  ##  ##  ##  ##                  
    ####    ####                    ####    ####                    
    ##      ##                      ##      ##                      
    ########                        ########                        
    ##  ##                          ##  ##                          
    ####                            ####                            
    ##                              ##                              
    ################################                                
    ##  ##  ##  ##  ##  ##  ##  ##                                  
    ####    ####    ####    ####                                    
    ##      ##      ##      ##                                      
    ########        ########                                        
    ##  ##          ##  ##                                          
    ####            ####                                            
    ##              ##                                              
    ################                                                
    ##  ##  ##  ##                                                  
    ####    ####                                                    
    ##      ##                                                      
    ########                                                        
    ##  ##                                                          
    ####                                                            
    ##                                                               ok

By kragen 10 months ago

Straight from the blog, too, from C to Forth:

   : sier cr 32 0 do 32 0 do i j and if ."   " else ." * " then loop cr loop ;
   sier

Output from eforth/subleq (with do...loop set in the config):

    * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 
    *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   *   
    * *     * *     * *     * *     * *     * *     * *     * *     
    *       *       *       *       *       *       *       *       
    * * * *         * * * *         * * * *         * * * *         
    *   *           *   *           *   *           *   *           
    * *             * *             * *             * *             
    *               *               *               *               
    * * * * * * * *                 * * * * * * * *                 
    *   *   *   *                   *   *   *   *                   
    * *     * *                     * *     * *                     
    *       *                       *       *                       
    * * * *                         * * * *                         
    *   *                           *   *                           
    * *                             * *                             
    *                               *                               
    * * * * * * * * * * * * * * * *                                 
    *   *   *   *   *   *   *   *                                   
    * *     * *     * *     * *                                     
    *       *       *       *                                       
    * * * *         * * * *                                         
    *   *           *   *                                           
    * *             * *                                             
    *               *                                               
    * * * * * * * *                                                 
    *   *   *   *                                                   
    * *     * *                                                     
    *       *                                                       
    * * * *                                                         
    *   *                                                           
    * *                                                             
    *                                                               
     ok
     ok

By anthk 10 months ago

That looks nicer than my version. But you should put the `cr` before the inner loop, not after it. That way you can remove the `cr` before the outer loop.

By kragen 10 months ago

Nothing much to do with your great post, but I almost REALLY liked that first pyramid, but the last line being off threw me visually, so I had to straighten it out:

                                    1
                                  1   1
                                1   0   1
                              1   1   1   1
                            1   0   0   0   1
                          1   1   0   0   1   1
                        1   0   1   0   1   0   1
                      1   1   1   1   1   1   1   1
                    1   0   0   0   0   0   0   0   1
                  1   1   0   0   0   0   0   0   1   1
                1   0   1   0   0   0   0   0   1   0   1
              1   1   1   1   0   0   0   0   1   1   1   1
            1   0   0   0   1   0   0   0   1   0   0   0   1
          1   1   0   0   1   1   0   0   1   1   0   0   1   1
        1   0   1   0   1   0   1   0   1   0   1   0   1   0   1
      1   1   1   1   1   1   1   1   1   1   1   1   1   1   1   1
    1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1
  1   1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1

By animal531 10 months ago

Sierpinski pirated it from Razor 1911 :)

By _7acn 10 months ago
basically, whenever a shape contains 3 connected couples of itself, you get a deformed Sierpinski triangle.

By immibis 10 months ago
[deleted]

By 10 months ago
been down the bitwise fractal rabbit hole more times than i can count and honestly, i never get tired of these patterns - you think people start seeing shapes like this everywhere after a while or is that just me

By gitroom 10 months ago
[dead]

By jujuh 10 months ago