Patterns

July 27, 2021 4:26 PM

Bit-field patterns created from applying simple formulas (small subset of work available in unrolled thread)
posted by They sucked his brains out! (43 comments total)

Okay, someone please help me out because this does not seem to be "x to the power of y divided by 9", but I do not understand what it actually is, other than pretty.
posted by saturday_morning at 4:41 PM on July 27, 2021

Ah Tuesdays with moiré
posted by condour75 at 4:44 PM on July 27, 2021 [32 favorites]

Yesssss. These are so neat, and it's such an elegant little form of formula to produce such interesting results. I got excited about that same thread myself a while back and went on a whole coding and plotter-drawing spree trying to explore it a little myself.

For anybody who is, other than enjoying the patterns, feeling kind of "what?" about what's going on (I was when I first saw it), this is using a combination of bitwise operators and modulus arithmetic to decide whether each pixel in a (x,y) plane should be a black or white (that is, a 1 or a 0).

So the canonical example in Martin Klepe's first tweet there is

(x ^ y) % 9

Which translates as "for every (x,y) coordinate on a plane, do a bitwise XOR of the base 2 value of x compared to y, and see if the result modulo 9 is a 0 or not". (Big note: ^ is more commonly used as an exponent value in online math shorthand, but this is *not* x to the y power, it's x XOR y. Threw me originally too.)

Which if you're not into it is still useless jargon probably, but the actual thing happening isn't too complicated. x and y are both integers, you've got a big 2D grid where x gets bigger on one axis and y gets bigger on the other, starting from 0. You take those two integers, write them out in binary as strings of 1 and 0, take those two strings and perform an Exclusive Or operation where your new binary number has a 1 wherever the original strings disagree (EITHER the top digit OR the bottom digit is a 1), and has a 0 wherever they agree.

Take THAT number, divide it by 9. Does it divide evenly, with remainder zero? Then it's a white pixel. Otherwise, it's a black pixel. Repeat for as many pixels as you care to see. It's straightforward but also very tedious, so great to make a computer do even though you could work it out on graph paper if you wanted.
posted by cortex at 4:44 PM on July 27, 2021 [15 favorites]

You can see throughout that thread variations on the formula; changing out various logical operators in those tiny one liners makes a big difference in the overall kind of pattern you get, where replacing the XOR with OR or AND, or the % modulo sign with various bitwise operators, fundamentally changes the kind of pictures drawn, whereas just changing the numeric coefficient so that you've got e.g. (x ^ y) % 5 gives you a pattern that has the same general feel but is different in the details.

(In fact there's a nice little math puzzle there, to put in concrete terms why if you keep making that coefficient larger, the drawings get more and more sparse. Also, why are all the interesting patterns for (x ^ y) % n apparently using odd n? And what happens when n is 2, or 1? And what happens if instead of (x ^ y) % n you do ((x ^ y) + 1) % n? And so on. All of the things that happen with these end up making sense if you work through what's going on, but the sheer concision of the basic formula still feels magical, like some little Game Genie For Math discovery.)
posted by cortex at 4:53 PM on July 27, 2021 [1 favorite]

BRB, gonna write a Twitter Mastodon bot that generates these at random.

(Semi-serious here; it may be a fun little afternoon multi-week hacking project.)
posted by suetanvil at 5:04 PM on July 27, 2021

Animating them is fun, too. Copy this into a file, save it as .html, and open it in a browser. You can change the formula inside the "test" function to give different effects based on x, y, and time (t).

https://pastebin.com/5uj34j3s
posted by wanderingmind at 5:06 PM on July 27, 2021 [4 favorites]

See also ByteBeat, which is this simple kind of math formula but for music generation.

Has someone made a good web UI for making these 2x pixel arrays? It's simple Javascript but maybe someone's hosted it nicely.
posted by Nelson at 5:31 PM on July 27, 2021 [3 favorites]

These are awesome. I started trying random functions. Then quickly found one that kept me captivated for 20 minutes.

(x + x*y) % [some number Z]

Gives a rather mundane grid, if Z is prime. But when Z is not prime it adds more patterns into the squares. The complexity of the pattern seems related to the number of factors. Compare 53 (prime, gives squares) to 51 (= 3 x 17, gives squares with smaller squares inside) to 60 (= 2 x 2 x 3 x 5, gives apparent circles inside the squares well.)

I *think* it's overlaying patterns in a square shape determined by the various prime factors.
posted by mark k at 5:40 PM on July 27, 2021

Neat!

Here's a fun challenge problem: can you find two such formulas such that you can get from one to the other by treating it as a game board for Conway's Game of Life for some finite number of steps?

In formal terms, find expressions for f(x,y) and g(x,y) : Z^2 -> {0,1}, such that if C is an operator representing the application of the rules of Conway's Game of Life for one step, g = (C^k) f.

Bonus points if f = g.
posted by biogeo at 5:41 PM on July 27, 2021

Also, bonus points if k=1. More bonus points if g = (C^k) f and f = (C^m) g for some integers k and m, and maximum bonus points if k=m=1.
posted by biogeo at 5:48 PM on July 27, 2021

Ah Tuesdays with moiré

𝔹𝕒 𝔻𝕦𝕞 𝕋𝕤𝕤
posted by lalochezia at 5:55 PM on July 27, 2021 [6 favorites]

biogeo, that's crazy talk. Clearly, there should be bonus points for making k as large as possible. And more bonus points for finding a subclass of formulas that can be transformed into each other through C.
posted by kleinsteradikaleminderheit at 6:01 PM on July 27, 2021

Well, somehow my mind immediately thought of those Earthbound backgrounds, and now I'm envisioning a combination of the two -- procedurally animated procedurally generated trippy graphics.
posted by pwnguin at 6:41 PM on July 27, 2021 [1 favorite]

Integers themselves are pretty weird.
The Moessner Miracle. Why wasn't this discovered for over 2000 years?

Stuff like this is why I was not terribly impressed by the graphics of the C64 disk-drive demo. You can make a whole bunch of pretty things with a simple(-ish) function.
posted by zengargoyle at 6:50 PM on July 27, 2021 [3 favorites]

Man, wait until you can see what you can do with just a stick of lead and some paper.
posted by Nelson at 7:02 PM on July 27, 2021 [1 favorite]

Man, wait until you can see what you can do with just a stick of lead and some paper.

I really don't think it's wise for anyone to smoke that.
posted by loquacious at 7:32 PM on July 27, 2021 [4 favorites]

*HRNNNNNGGG*
posted by loquacious at 7:34 PM on July 27, 2021 [4 favorites]

Those challenges leave a lot of bonus points on the table for some very simple cases:
oh no, mefi does not like nonmatching angle brackets at all

f(x,y)=g(x,y)=0, k=m=1
f(x,y)=g(x,y)=x%2
f(x,y)=g(x,y)=y%2
f(x,y)=g(x,y)=(0<x<3)&&(0<y<3)
f(x,y)=g(x,y)=(x%4<2)&&(y%4<2)

f(x,y)=g(x,y)=(x%5<3)&&(y%5==1), k=m=2
f(x,y)=g(x,y)=(x%5==1)&&(y%5<3)

f(x,y)=(x%5<3)&&(y%5==1), g(x,y)=(x%5==1)&&(y%5<3), k=m=1
f(x,y)=x%4<2, g(x,y)=x%4>1
f(x,y)=y%4<2, g(x,y)=y%4>1
posted by polytope subirb enby-of-piano-dice at 8:21 PM on July 27, 2021 [2 favorites]

Reminded me of this train station with walls designed using cellular automata "Rule 30". I think it was on metafilter before? A whole set of those patterns are described in A New Kind of Science

What if you used one of those 2d patterns to prime a new one, and then stacked them to generate 3d shapes? Ummm...
posted by haemanu at 8:31 PM on July 27, 2021

also, being half-asleep on mefi produces some fun microdreams, like reading a reply on this thread saying that supermarket shopping trolleys have ocr and will print these patterns if you feed them formulae in the right way, then rushing out with a scrap of paper to give it a try
posted by polytope subirb enby-of-piano-dice at 8:32 PM on July 27, 2021 [1 favorite]

Reminds me of the XOR texture.
posted by genpfault at 8:41 PM on July 27, 2021 [1 favorite]

Okay, f(x,y)=g(x,y)=0 definitely doesn't count as the trivial case, but otherwise pse-o-p-d, claim your numerous bonus points! More bonus points on offer for a solution that doesn't use comparison operators as indicator functions.
posted by biogeo at 8:43 PM on July 27, 2021

Speaking of microdreams...
Another xor "automaton"
posted by haemanu at 8:56 PM on July 27, 2021 [3 favorites]

The XOR texture mentioned by genpfault uses

x ^ y

to set pixel values on a black-white spectrum. The formula is very similar to the posted link's

(x ^ y) % 9
posted by torii hugger at 9:24 PM on July 27, 2021 [1 favorite]

Couldn't find a previously, but more on youtube about the train station haemanu mentioned: https://www.youtube.com/watch?v=aeyhnrZvQBE
posted by polytope subirb enby-of-piano-dice at 9:32 PM on July 27, 2021

Oh man, I had a whole arrangement of these, animated on a frame variable, in VGA Mode X -- I wonder if I can dig the code out of an old disk image inside another old disk image or such. Trying to remember the formula structure from how it looked... it was not based on the classic (x*x + y*y)%k though I had started with that. There was clearly some harmonic-series aliasing I'm recalling in the animation. I bet it was subsampling high-frequency sawtooths by large increments mod color range.
posted by away for regrooving at 10:00 PM on July 27, 2021 [1 favorite]

more on youtube about the train station haemanu mentioned

These are beautiful. More of these, please!
posted by They sucked his brains out! at 10:02 PM on July 27, 2021

These are awesomesauce They sucked his brains out!, I was going to put a q up about other natural (and non-natural) patterns. Love the noise iterations!

Am currently working on a very large Voronoi that will be formed partly with a Cat. D10, these are more grist for that mill.
posted by unearthed at 11:30 PM on July 27, 2021

(x % y) ^ (256 % (x|y)) makes a satisfyingly weird pattern of flying distorted Sierpinski triangles.
posted by wanderingmind at 12:12 AM on July 28, 2021

There is something about the way these patterns fall out of mathematics that is probably the closest I will ever feel to understanding the Divine. It feels like we're glimpsing some kind of impossible cosmic beauty through a tiny pin-hole
posted by Merus at 1:38 AM on July 28, 2021 [4 favorites]

Oh no. I had things to do! And now I have other things to do!

Seriously though, I love stuff like this. Thanks for posting, They sucked his brains out!

Some apparently boring patterns get a whole lot more interesting if you add colour into the mix.
posted by Mister_Sleight_of_Hand at 3:10 AM on July 28, 2021 [1 favorite]

that doesn't use comparison operators as indicator functions.

There are lots of workarounds (e.g., (x>y) => Math.max(0, Math.min(1, x-y))).

Note that it's possible to encode a function that's 0 (or 1) for finitely many (Xi, Yi) points like:

((x ^ X0) | (y ^ Y0)) &&
((x ^ X1) | (y ^ Y1)) &&
((x ^ X2) | (y ^ Y2)) &&
...

(It's possible to do it with entirely binary ops (& instead of &&), but it requires a lot of bit shifting to compress each term into a single bit).

It's also possible to do it entirely with arithmetic (ignoring the problem of overflows), consider the related polynomial:

((x - X0) * (x - X0) + (y - Y0) * (y - Y0)) *
((x - X1) * (x - X1) + (y - Y1) * (y - Y1)) *
((x - X2) * (x - X2) + (y - Y2) * (y - Y2)) *
...

Which is the product of squared distances to each of the input (Xi,Yi) points: this function is zero only exactly at the input points and positive elsewhere.

Using constructions like this you can produce (comparison-free, branch-free) expressions for any finite Game of Life boards you want, including static patterns ("still lifes").
posted by Pyry at 7:25 AM on July 28, 2021 [1 favorite]

I made a little tool that lets you easily try out arbitrary formulas.
posted by jedicus at 8:34 AM on July 28, 2021 [4 favorites]

That's great jedicus! But it has a probably unintentional effect of degrading over time.. You only ever paint pixels black, never white, so iteration of formula results in less and less white until you're at Malevich Square.
posted by Nelson at 8:40 AM on July 28, 2021

Yep, I fixed that!
posted by jedicus at 8:43 AM on July 28, 2021

jsfiddle is a great idea though! Here's wanderingmind's animated version as a live demo. No nice formula UI like Jedicus made but you can just edit the test function in the source code easily enough. Don't use the t variable if you want static images.
posted by Nelson at 8:43 AM on July 28, 2021 [2 favorites]

Dave Fergemann's html explorations of arithemetic patterns goes beyond one-bit output to show some cool colored sequences: modquilt. (That work was done while we were talking about finite-field diffie-hellman modular arithmetic, which has a whole set of really useful applications, though it's largely been replaced by elliptic curve cryptography in practice these days)

These visualizations offer exciting glimpses into abstract patterns that exist in numbers themselves but are otherwise hard to think about without a lot of training. cool stuff!
posted by dkg at 10:04 AM on July 28, 2021

I modified jeddicus' JSFiddle to output a gradient, which is a bit more complex but lets you see "near misses." To get the same result as the boolean version, just tack == 0 onto the end of your formula, e.g. (x ^ y) % 9 == 0

Classic XOR pattern is (x ^ y) / 255

Math.abs((x % y) / y + (y % x) / x - 1) gives a neat gradient pattern

Raising a formula to a fairly high power tends to add a bit of depth without blowing out the original pattern: ((8 - (x ^ y) % 9) / 8) ** 6 is a version of the (x ^ y) % 9 == 0 pattern with some nice background depth.
posted by reventlov at 10:30 AM on July 28, 2021 [3 favorites]

Sometimes it’s humbling to be on Metafilter.
posted by Don.Kinsayder at 1:32 PM on July 28, 2021 [1 favorite]

Great post. Fun and games with 64-bit arithmetic. Diversion: assume we have a computer that can do ∞-trit arithmetic.

A cool expression to graph using our ∞-trit machine is

" x:0.5 > 0 "

where

":" is the tritwise-equality operator on infinite ternary sequences
x is a real number in the unit interval [0, 1]
0.5 and 0 are the usual real numbers
">" is the familiar ordering on real numbers

this evaluates to the Cantor set.

Our computer represents each real number in the unit interval as an infinite sequence of ternary digits. Examples:

0 is represented as the sequence (0, 0, 0, ...),
1 is represented as (2, 2, 2, ...),
1/2 is represented as (1, 1, 1...), and
1/4 is represented as (0, 2, 0, 2, 0, 2, ...)

Justification:

Think of "x" and "y" in all these pattern expressions as finite sequences of binary digits that give the "addresses" of points on the real number line. Then we can single out any real number z on the number line and ask "what is z's address as a sequence of binary digits?".

Let P_3 denote a ternary hierarchical decomposition of the unit interval [0, 1]. For the first level of the hierarchy we split the unit interval [0, 1] into a partition of three equally sized buckets: [0, 1] = [0, 1/3] union (1/3, 2/3) union [2/3, 1]. Label each bucket, from left-to-right, as "0", "1" and "2". There's a slight asymmetry here as the middle bucket labelled "1" excludes its left and right endpoints 1/3 and 2/3. Thanks Georg. We can repeat this process recursively to keep partitioning each level j bucket into three level j+1 buckets. Each level j bucket either has the form [a, b] or (a, b)

[a, b] gets split into [a, (a+b)/3] union ((a+b)/3, 2*(a+b)/3) union [2*(a+b)/3, b]
(a, b) gets split into (a, (a+b)/3] union ((a+b)/3, 2*(a+b)/3) union [2*(a+b)/3, b)

For any real number x in the unit interval, we can define its "address" with respect to to our hierarchy P_3. This is an infinite sequence of ternary digits ("trits") that says which bucket x sits in at each level of our hierarchy. The address of x with respect to P_3 is P_3(x) := (x_1, x_2, ..., x_j, ...) where each trit x_j in {0, 1, 2} indicates which of the three buckets x sits inside at layer j of the hierarchy.

If a and b are strings of bits, "a^b" denotes bitwise "exclusive or" for binary digits. For strings of bits we can compute bitwise equality by "~(a^b)" , where "~" is bitwise not operator. We want a tritwise equality operator for our sequences of trits. Let "a:b" define the infinite sequence of trits where (a:b)_j = 1 if a_j = b_j otherwise 0

Then P_3(x):P_3(0.5) > 0 defines the Cantor set. We can abuse notation a little bit and write this as "x:0.5 > 0", where we define ":" to act on real numbers x, y in [0, 1] by x:y = P_3(x):P_3(y) .

One technicality we've glossed over is that real numbers don't necessarily have unique ternary expansions. This isn't peculiar to ternary, same problem for infinite binary or infinite decimal precision. E.g. 1 = 0.99999.... in base 10, and 1 = 0.11111.... in base 2, and 2 = 0.2222... in base 3. This means that P_3 isn't well defined. We can probably repair that by defining P_3(x) to be the minimal infinite ternary sequence that addresses x, where we order the sequences lexicographically.
posted by are-coral-made at 2:28 PM on July 28, 2021 [2 favorites]

These are beautiful and nostalgic. Because of whatever quirks of its BASIC implementation and 256x192 resolution the old 8-bit ZX Spectrum could create these wonderful moire patterns just by DRAW-ing a line from the origin to the top of the screen, then another one pixel along and so forth. Similarly CIRCLEs with ever increasing radius. These images are much more varied though.

I'm also reminded of that C=64 maze effect program which popped up as a book a while back (which must have equivalents in other BASICs):

10 PRINT CHR$(205.5+RND(1)); : GOTO 10
posted by I'm always feeling, Blue at 7:48 PM on July 28, 2021 [1 favorite]

I mean, this is just a real reminder of how pretty maths actually is!
posted by I'm always feeling, Blue at 7:51 PM on July 28, 2021

I'm late to this, but I wrote a Python module to create these bit fields either as text in the terminal window or as image files.

More info here.
posted by AlSweigart at 12:11 PM on August 2, 2021 [2 favorites]