[HN Gopher] Sierpinski Triangle? In My Bitwise and?
___________________________________________________________________
Sierpinski Triangle? In My Bitwise and?
Author : guiambros
Score : 208 points
Date : 2025-05-10 21:42 UTC (1 days ago)
(HTM) web link (lcamtuf.substack.com)
(TXT) w3m dump (lcamtuf.substack.com)
| jcul wrote:
| 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 wrote:
| Really interesting, and surprising article though!
| IceDane wrote:
| Same problem here. Firefox on Android.
| Jolter wrote:
| Same. Safari on iPhone.
| adrian_b wrote:
| 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.
| jrockway wrote:
| Substack is kind of a weird site, but this newsletter in
| particular is worth subscribing to and getting in your email.
| peterburkimsher wrote:
| Wolfram did a lot of research into cellular automata, and the
| Sierpinski Triangle kept showing up there too:
|
| https://www.wolframscience.com/nks/
| GuB-42 wrote:
| This one in particular: https://en.wikipedia.org/wiki/Rule_90
| jesuslop wrote:
| You get those also doing a Pascal triangle mod 2, so a xor. Is a
| zoom-out fractal as oposed to Mandelbrot set.
| anthk wrote:
| 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
| kragen wrote:
| 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 Michal
| 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
| anthk wrote:
| 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
| kragen wrote:
| 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.
| animal531 wrote:
| 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
| dvt wrote:
| Just a heads up, all (binary?) logical operators produce
| fractals. This is pretty well-known[1].
|
| [1] https://icefractal.com/articles/bitwise-fractals/
| wang_li wrote:
| The change rate in binary notation is fractal.
| Timwi wrote:
| Ask yourself why you added the "pretty well-known" phrase, and
| consider xkcd 1053.
| marginalia_nu wrote:
| It would be interesting to see how this generalizes to other
| bases.
|
| Base 3 has nearly 20,000 operators, of which 729 are
| commutative.
| dvt wrote:
| Yeah, I'm pretty sure as long as you have symmetry somewhere
| (e.g. a commutative operation), you'll get self-similar
| patterns.
| zX41ZdbW wrote:
| Sierpinski also sounds nice in music. Examples here:
| https://github.com/ClickHouse/NoiSQL
| gjm11 wrote:
| 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!
| coderatlarge wrote:
| i really love the result you quote about the carries. do you
| know where it has been applied by any chance?
| gjm11 wrote:
| I don't know of applications offhand, sorry. For me it's in
| the "appreciated for its own sake" category :-).
| coderatlarge wrote:
| 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.
| gjm11 wrote:
| 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.)
| ethan_smith wrote:
| 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.
| tomrod wrote:
| I prefer mine au naturale 3-adic.
|
| https://m.youtube.com/watch?v=tRaq4aYPzCc
|
| Just kidding. This was a fun read.
| kragen wrote:
| 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 wrote:
| 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 wrote:
| 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 wrote:
| I draw these with paper and pen when I am extremely bored in
| meetings.
| susam wrote:
| 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.
| kragen wrote:
| Gorgeous!
| msarnoff wrote:
| Munching squares!
| ttoinou wrote:
| Thank you for sharing. The third one has some kind of trippy 3d
| effect in the first seconds
| Recursing wrote:
| Shadertoy link: https://www.shadertoy.com/view/MllcW2
|
| And, xor, and or are red, green and blue
| anyfoo wrote:
| 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 wrote:
| 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?"
| `":" #");}
| Terr_ wrote:
| Instructions unclear, machine rooted. :p
| modeless wrote:
| 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
| MaxGripe wrote:
| Sierpinski pirated it from Razor 1911 :)
| lenerdenator wrote:
| It's more likely than you think.
| ChuckMcM wrote:
| 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 wrote:
| I first saw these sorts of bitwise logic patterns at
| https://twitter.com/aemkei/status/1378106731386040322 (2021)
| fiforpg wrote:
| > 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.
| pacaro wrote:
| 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
| linschn wrote:
| That's called a simplex :)
|
| The same as in the simplex algorithm to solve linear
| programming problems.
| CrazyStat wrote:
| 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".
| tikili wrote:
| Munching squares:
| https://tiki.li/show/#cod=VYxLCoAwDET3PcWsFWql4s7D1Fo/oBZqkf...
| immibis wrote:
| basically, whenever a shape contains 3 connected couples of
| itself, you get a deformed Sierpinski triangle.
| gitroom wrote:
| 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
| tpoacher wrote:
| 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.
___________________________________________________________________
(page generated 2025-05-11 23:01 UTC)