: .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
: .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
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 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
!!!!
!!!!!!!!
!!!! !!!!
!!!!!!!!!!!!!!!!
!!!! !!!!
!!!!!!!! !!!!!!!!
!!!! !!!! !!!! !!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!! !!!!
!!!!!!!! !!!!!!!!
!!!! !!!! !!!! !!!!
!!!!!!!!!!!!!!!! !!!!!!!!!!!!!!!!
!!!! !!!! !!!! !!!!
!!!!!!!! !!!!!!!! !!!!!!!! !!!!!!!!
!!!! !!!! !!!! !!!! !!!! !!!! !!!! !!!!
!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
!!!! !!!!
!!!!!!!! !!!!!!!! ok
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 ;
################################################################
## ## ## ## ## ## ## ## ## ## ## ## ## ## ## ##
#### #### #### #### #### #### #### ####
## ## ## ## ## ## ## ##
######## ######## ######## ########
## ## ## ## ## ## ## ##
#### #### #### ####
## ## ## ##
################ ################
## ## ## ## ## ## ## ##
#### #### #### ####
## ## ## ##
######## ########
## ## ## ##
#### ####
## ##
################################
## ## ## ## ## ## ## ##
#### #### #### ####
## ## ## ##
######## ########
## ## ## ##
#### ####
## ##
################
## ## ## ##
#### ####
## ##
########
## ##
####
## ok : sier cr 32 0 do 32 0 do i j and if ." " else ." * " then loop cr loop ;
sier
* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * *
* * * *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * *
* * * *
* *
* * * * * * * * * * * * * * * *
* * * * * * * *
* * * * * * * *
* * * *
* * * * * * * *
* * * *
* * * *
* *
* * * * * * * *
* * * *
* * * *
* *
* * * *
* *
* *
*
ok
ok 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 1Base 3 has nearly 20,000 operators, of which 729 are commutative.
"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!
(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.)
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! :-)
> E. E. Kummer, “Über die Ergänzungssätze zu den allgemeinen Reciprocitätsgesetzen,” Journal für die reine und angewandte Mathematik 44 (1852), 93–146. Reprinted in his Collected Papers, volume 1, 485–538.
Also, the answer to exercise 5.36 says “See [226] for extensions of this result to generalized binomial coefficients” and [226] (on page 620) is:
> Donald E. Knuth and Herbert S. Wilf, “The power of a prime that divides a generalized binomial coefficient,” Journal für die reine und angewandte Mathematik 396 (1989), 212–219
which of course begins (https://www2.math.upenn.edu/~wilf/website/dm36.pdf) by citing Kummer. (Looks like the authors published in the same journal as Kummer, 137 years later!)
I did notice that ex 5.36 references a paper of Knuth & Wilf, but references aren't transitive :-).
https://m.youtube.com/watch?v=tRaq4aYPzCc
Just kidding. This was a fun read.
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
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.
And, xor, and or are red, green and blue
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.
cc -w -xc -std=c89 -<<<'main(c){int r;for(r=32;r;)printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}'&&./a.*
main(c,r){for(r=32;r;)printf(++c>31?c=!r--,"\n":c<r?" ":~c&r?" `":" #");}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.
— 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.
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
The same as in the simplex algorithm to solve linear programming problems.
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”.
(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.
jcul•2mo ago
Apologies for a comment not related to the content, but it makes it difficult to read the article on mobile.
jcul•2mo ago
IceDane•2mo ago
Jolter•2mo ago
adrian_b•2mo ago
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•2mo ago