Schotter - Georg Nees - Part 2

Source: Victoria and Albert — link

In part 1, we found the original ALGOL-60 code for Schotter, and converted it to Python. Correctly matching the style was satisfying… but wouldn’t it be nice to exactly recreate the entire original plot?

Here’s the problem: we see references to random generators, but not their source. From Nees’ quote about the work:

From lines 9 and 10, it can be seen that the position of a single square is influenced by random generator J1, and the angle placement by J2.

Not so satisfying.

Step one: lots of searching, some asking

Schotter is an early, deservedly famous example of computer-generated art. There are a lot of references to it online, and a lot of recreations. They vary in their fidelity to the original, but it’s lovely to see how Nees’ work from the late 1960s continually inspires people to try generating art themselves.

An influential example

An influential recreation seems to be this well-written tutorial by Jim Plaxco.

It doesn’t match the actual implementation, but takes an interesting approach: the same random value is used both to rotate the squares, and (scaled by a factor of 0.45 named dampen) to shift them, down and to the right.

Looking for that dampening value is an easy way to identify descendants of this tutorial. Here’s a fun version by Stewart Russell, animating the drawing of the artwork on a simulated Tektronix 4010 vector display.

Jim Plaxco’s verion is the one I copied when I first tried an implementation (in Elm). In retrospect, I’m glad that it doesn’t look quite right—the randomness doesn’t creep in fast enough, and there’s no left-to-right increase in disorder—because that drove me to dive deeper.

There are also many exaxmples where people recreated the artwork by eyeballing it until it looked right, and many where people continue to implement fascinating variations. In this post by Bill Glover, you can see both.

Lots of information

There are also lots of articles about Georg Nees, many of which mention Schotter.

• 2021 Medium article by Druid
• 2020 post at the Kate Vass Galerie in Zurich
• Good old Wikipedia

Asking for help

I figured Jason Scott and Kay Savetz, heroes of the Internet Archive and frequent retrocomputing historians, might have ideas about how to track down original source code, so I asked on Mastodon. They didn’t know offhand, but did mention Paul Rickards, who has some absolutely amazing plotter art.

Following the breadcrumbs myself

Nees had an early exhibition in 1968 or so, and published a PhD thesis in 1969, Generative Computergraphik. Several of the histories mentioned his research into randomness and random number generation, so I figured he may have written about it in his thesis.

This twitter post had a tantalizing cover image, which could be found elsewhere with Google Image Search (example, example).

Jackpot: The thesis

I forget how I eventually found it, but the publisher Diaphenes in Zurich have a PDF of a 2006 reprint of the thesis. €30 later, I was off to the races.

Excitedly, I started copy-pasting screenshots into Google Translate. Eventually, that got tedious, and I tracked down OCRmyPDF, which can use Tesseract’s language packs to OCR in German. Translation is still necessary, but it’s easier to copy and paste longer sections.

The random number generators

Section 2.2.1. of Nees’ thesis is titled “Random generators”, and includes code!

2.2.1. Zufallsgeneratoren

Das Verfahren, das wir zur Erzeugung von Zufallszahlen benutzen werden, ist außerordentlich einfach. Ist JI die letzte aus einer Folge bereits erzeugter Zufallszahlen, so wird JI mit der Zahl 5 multipliziert und das Ergebnis wird durch sukzessive Subtraktion absteigender Zweierpotenzen unter eine bestimmte Zahlenschranke herabgedrückt. Die so gewonnene Zahl setzt als neue Zufallszahl die schon früher erzeugte Folge fort. Will man z. B. sanzzahlige Zufallszahlen erzeugen, die kleiner als 128 sind, so kann man 127 als erste Zufallszahl wählen — oder auch als letzte Zufallszahl einer kürzlich erzeugten Folge — und multipliziert nun 127 mit 5. Dieses ergibt 635. Nun zieht man die Zweierpotenzen 512, 256 und 128 solange schrittweise von 635 ab, bis das Ergebnis wieder kleiner als 128 ist. Man erhält also zunächst 635 — 512 ＝ 123, was aber bereits kleiner als 128 ist, so daß wir nichts weiter abzuziehen brauchen. Nun haben wir bereits zwei Zufallszahlen: 127 und 123. Beim nächsten Mal erhalten wir 123 * 5 ＝ 615. Davon 512 abgezogen, ergibt 103. Wiederum beim nächsten Mal ist 103 * 5 — 512 ＝ 3. Bis jetzt besitzen wir also die Zufallszahlen 127, 123, 103, 3. Von 3 x 5 ＝ 15 braucht man überhaupt nichts abzuziehen, denn 15 ist schon kleiner als 128, also ist 15 die nächste Zufallszahl. Auch 15 * 5 ＝ 75 ist kleiner als 128. Die Folge von Zufallszahlen ist also jetzt angewachsen auf 127, 123, 103, 3, 15, 75.

Setzt man das Verfahren fort, so ergeben sich noch einige neue Zufallszahlen, sehr bald jedoch wird die Folge von Zufallszahlen periodisch, wie wir später noch anschaulich machen werden. Die Periode besteht aus genau 32 Zahlen. Man bezeichnet die Algorithmen zur Erzeusung von Zufallszahlen als Zufallsgeneratoren. Zufallsseneratoren von so kurzer Periode, wie sie der vorgeführte Algorithmus besitzt, sind jedoch für unsere Untersuchungen fast immer ungeeignet. Wir benötigen Zufallssubstrate, die jedenfalls in dem Bereich, in dem wir sie benutzen, außer dem reinen Zufall selbst keine Qualitäten zu den ästhetischen Gebilden beisteuern, zu deren Genese sie herangezogen werden. Das bedeutet praktisch nichts anderes, als daß die Zufallsgeneratoren eine so große Periode aufweisen müssen, daß sie sich für uns nicht bemerkbar macht. Erfreulicherweise ist das Verfahren, mit dem wir vorhin experimentierten, dann durchaus brauchbar, wenn wir die Zweierpotenzen 128, 256, 512 durch die Potenzen 2 hoch 32 bis 2 hoch 34 ersetzen.IndieProgrammierspracheALGOLübersetzt,wird der Zufallsgenerator durch die Zeilen 6 bis 15 des folgenden Programms wiedergegeben:

2.2.1. Random generators

The method we will use to generate random numbers is extremely simple. If JI is the last of a sequence of random numbers already generated, JI is multiplied by the number 5 and the result is reduced to below a certain number limit by successive subtraction of descending powers of two. The number obtained in this way continues the previously generated sequence as a new random number. If, for example, you want to generate integer random numbers that are less than 128, you can choose 127 as the first random number - or as the last random number in a recently generated sequence - and multiply 127 by 5. This gives 635. Now you subtract the powers of two 512, 256 and 128 step by step from 635 until the result is again less than 128. So we first get 635 - 512 ＝ 123, which is already smaller than 128, so we don’t need to subtract anything else. Now we already have two random numbers: 127 and 123. The next time we get 123 * 5 ＝ 615. Subtracting 512 from this gives us 103. The next time again, 103 * 5 - 512 ＝ 3. So far we have the random numbers 127, 123, 103, 3. We don’t need to subtract anything from 3 x 5 ＝ 15, because 15 is already smaller than 128, so 15 is the next random number. 15 * 5 ＝ 75 is also smaller than 128. The sequence of random numbers has now grown to 127, 123, 103, 3, 15, 75.

If the process is continued, a few more random numbers are produced, but very soon the sequence of random numbers becomes periodic, as we will show later. The period consists of exactly 32 numbers. The algorithms for generating random numbers are called random generators. However, random generators with such a short period as the algorithm presented here are almost always unsuitable for our investigations. We need random substrates which, at least in the area in which we use them, do not contribute any qualities other than pure randomness to the aesthetic structures for whose creation they are used. This means practically nothing other than that the random generators must have such a long period that we do not notice it. Fortunately, the method we experimented with earlier is quite useful if we replace the powers of two 128, 256, 512 with the powers 2 to the power of 32 to 2 to the power of 34. Translated into the ALGOL programming language, the random generator is represented by lines 6 to 15 of the following program:

 2  'BEGIN''COMMENT'ZUFALLSFOLGE1
 3  'INTEGER'JI,JS.,
 4  'REAL'JA,JE.,
 5  'REAL''PROCEDURE'J.,
 6  'BEGIN''COMMENT'ZUFALLS-GENERATOR J.,
 7      Jl.=5*JI,
 8      'IF'J1'NOTLESS'8589934592
 9      'THEN'JI.=JI—-8589934592.,
10      'IF'JI'NOTLESS'4294967296
11      'THEN'JI.=JI—4294967296.,
12      'IF'JI'NOTLESS'2147483648
13      'THEN'JI=JI—2147483648.,
14      J.=JI/2147483648*(JE—JA) + JA
15  'END'ZUFALLSGENERATOR J.,
16  JS.=1306859721.,
17  'BEGIN''REAL'U.,
18  JI.=JS.,OPEN(0,0).,
19  JA.=0.,JE.=90.,
20  'FOR'U.=0'STEP'2'UNTIL'258'DO'
21  'BEGIN' LEER(U+.5,0).,
            LINE(U+.5,J).
22          LEER(U+1.5,J).,
            LINE(U+1.5,0)
23  'END'., CLOSE
24  'END'
25  'END'ZUFALLSFOLGE 1,,

Details on using the random number generators

Using an example that draws butterflies, Nees describes the usage of the generators.

[… butterfly specifics elided …]

2.2.2. Der Falterschwarm

Sehr ott reicht zum Zeichnen von Zufallsgraphiken ein einzelner Zufallsgenerator nicht aus. Der Grund dafür liegt darin, daß man verschiedene gestaltbestimmende Parameter einer Graphik gern durch verschiedene Zufallsgeneratoren regieren läßt, meistens benötigen die verschiedenen Parameter sogar verschiedene Streugrenzen. Außerdem vermindert die Verwendung von mehr als einem Zufallsgenerator die Gefahr des Einschleichens von Periodizitäten in die Struktur der Graphik. Wir führen deshalb eine Bezeichnungsweise ein, die es uns erlaubt, beliebig viele Zufallsgeneratoren in unseren Programmen aufzurufen: J1, J2, J3,… bezeichnen Zufallsgeneratoren, wobei die Vereinbarung der Prozedur Jn sich von den Zeilen 6 bis 15 des Prosramms (1/2.2.1) nur dadurch unterscheidet, daß beziehungsweiıse Jn, JIn, JAn, JEn an die Stelle von J, JI, JA, JE tritt. Die neuen Zufallsgeneratoren J1, J2,… betrachten wir als horizontglobale Größen, d. h. wir rufen sie frei in den Programmen auf, sind uns jedoch bewußt, daß die Vereinbarungen von J1, J2,… am Anfang solcher ALGOL-Programme stehen müssen, wenn sie tatsächlich in einer Datenverarbeitungsanlage zum Laufen gebracht werden sollen. Nun sind wir in der Lage, die Sprache G2 zur Formulierung von zufallsbehafteten Bildgeneratoren durch eine Reihe von horizontglobalen Größen kennzeichnen zu können: G2 ist eine Erweiterung der Programmiersprache ALGOL um die Prozeduren OPEN, LEER, LINE, CLOSE, J1, J2, J3,…

Vom mathematischen Standpunkt aus gesehen liefern die Zufallsgeneratoren J1, J2,… gleichverteilte Zufallszahlen, d.h. die Wahrscheinlichkeit, daß ein Zufallswert in ein Teilintervall der Länge i von JA, JE fällt, ist immer gleich i/(JE—JA), unabhängig von der Lage des Teil-intervalls innerhalb von JA, JE.

Wir kommen nun zum Thema dieses Abschnitts, nämlich zum Falterschwarm in Bild 4. Betrachten wir die Prozedur FALTER(A,B,FAKTOR) aus Abschnitt 2.1.6 und darüber hinaus eine reelle Hilfsgröße P und zwei ganzzahlige Größen JS1 und JS2 als horizontglobal, so wird der Generator des Falterschwarms ein verhältnismäßig kurzes Programm:

[code elided – see translation below]

in Zeile 5 erhalten die Initialgrößen JI1 und JI2 der Zufallsgeneratoren J1 und J2 die Werte von JS1 und JS2 zugewiesen. Dabei sind JS1 bis JS6 feste ganze Zahlen, die sich als Initialwerte für Zufallsserien eignen und die wir der Bequemlichkeit halber immer wieder in den Bildgeneratoren verwenden. Die Werte von JS1 bis JS6 sind durch die folgenden Anweisungen gegeben.

2.2.2. The butterfly swarm

A single random generator is often not sufficient for drawing random graphics. The reason for this is that different parameters that determine the shape of a graphic are often controlled by different random generators; in most cases, the different parameters even require different scatter limits. In addition, the use of more than one random generator reduces the risk of periodicities creeping into the structure of the graphic. We therefore introduce a notation that allows us to call up any number of random generators in our programs: J1, J2, J3,… denote random generators, whereby the declaration of the procedure Jn differs from lines 6 to 15 of the program (1/2.2.1) only in that Jn, JIn, JAn, JEn respectively take the place of J, JI, JA, JE. We regard the new random generators J1, J2,… as horizon-global quantities, i.e. i.e. we call them freely in the programs, but are aware that the declarations of J1, J2,… must be at the beginning of such ALGOL programs if they are actually to be run in a data processing system. We are now in a position to characterize the G2 language for the formulation of random image generators by a series of horizon-global quantities: G2 is an extension of the ALGOL programming language by the procedures OPEN, LEER, LINE, CLOSE, J1, J2, J3,…

From a mathematical point of view, the random generators J1, J2,… provide uniformly distributed random numbers, i.e. the probability that a random value falls into a subinterval of length i of JA, JE is always equal to i/(JE—JA), regardless of the position of the subinterval within JA, JE.

We now come to the topic of this section, namely the butterfly swarm in Figure 4. If we consider the procedure BUTTERFLY(A,B,FACTOR) from Section 2.1.6 and also a real auxiliary quantity P and two integer quantities JS1 and JS2 as horizon-global, the generator of the butterfly swarm becomes a relatively short program:

1  'BEGIN''COMMENT'FALTERSCHWARM.,
2  'REAL'R,S.,
3  'INTEGER'I.,
4  OPEN(0,0).,
5  JI1.=JS1.,JI2.=JS2.,
6  JA1.=-130.,JE1.=130.,
7  JA2.=—90.,
8  'FOR'I.=1'STEP'1'UNTIL'100'DO'
9  'BEGIN' P.=J1.,R=J1.,
10         S.=ABS(P—R).,
           JE2.=90—.3xS.,
11         FALTER(.5*(P+R),J2,.02*S)
12 'END'.,
13 CLOSE
14 END FALTERSCHWARM.,

In line 5, the initial quantities JI1 and JI2 of the random generators J1 and J2 are assigned the values ​​of JS1 and JS2. JS1 to JS6 are fixed integers that are suitable as initial values ​​for random series and that we use again and again in the image generators for convenience. The values ​​of JS1 to JS6 are given by the following instructions.

JS1.=1306859721.,JS2.=1485627309,
JS3.=1649173265.,JS4.=1805297143.,
JS5.=1973195467.,JS6.=2013911545.,

What we learned from the thesis

• The random number generators are extremely simple. Each time you want a new random number, you multiply by 5, and take the remainder modulo \( 2^{31} \).
• Nees included a list of six favorite seeds that he used “again and again” in his images.
• The version of Schotter included in the thesis can be exactly recreated! It uses JS5 (1973195467) for the x- and y-shift seed, and JS3 (1649173265) for the rotation seed.

What’s missing…

We still don’t know the seeds used in the famous version displayed in the art exhibit.

Trying them all

Luckily, there are only about a billion possible seeds, assuming only odd numbers. We just need something to compare against, to see whether we got them right.

By looking very carefully at the famous plot, we can mark squares where it’s clear which direction they’ve been shifted, and which direction they’ve been rotated.

Pro-tip: Don’t use Right and Left part of the time, and Red and Blue part of the time.

Pro-tip: Always check your clever techniques on the version of the plot where you know the seeds first, to ensure you didn’t make a dumb mistake, like writing "lr.llr.lrl.l" instead of "br.bbr.brb.b" (see pro-tip 1).

Pro-tip: Ignoring the previous pro-tips might cause you to waste many, many hours, thinking things like, “Maybe he used an earlier version of his random number generator in 1968 to generate the plot, and it differs from the 1969 version in the thesis. Let’s try all the powers of 2 up to 32, or different multipliers than 5…”

Anyway…

Victory

After writing a Go program to rapidly check every possible seed, and getting rid of the bugs, we are finally able to discover that the famous plot uses (1922110153) for the x- and y-shift seed, and (1769133315) for the rotation seed.

And with that, we are finally able to perfectly recreate the original plot:

import math
import drawsvg as draw

class Random:
    def __init__(self, seed):
        self.JI = seed

    def next(self, JA, JE):
        self.JI = (self.JI * 5) % 2147483648
        return self.JI / 2147483648 * (JE-JA) + JA

def draw_square(g, x, y, i, r1, r2):
    r = 5 * 1.4142
    pi = 3.14159
    move_limit = 5 * i / 264
    twist_limit = pi/4 * i / 264

    y_center = y + 5 + r1.next(-move_limit, move_limit)
    x_center = x + 5 + r1.next(-move_limit, move_limit)
    angle = r2.next(pi/4 - twist_limit, pi/4 + twist_limit)

    p = draw.Path()
    p.M(x_center + r * math.sin(angle), y_center + r * math.cos(angle))
    for step in range(4):
        angle += pi / 2
        p.L(x_center + r * math.sin(angle), y_center + r * math.cos(angle))
    g.append(p)

def draw_plot(x_size, y_size, x_count, y_count, s1, s2):
    r1 = Random(s1)
    r2 = Random(s2)
    d = draw.Drawing(180, 280, origin='center', style="background-color:#eae6e2")
    g = draw.Group(stroke='#41403a', stroke_width='0.4', fill='none',
                   stroke_linecap="round", stroke_linejoin="round")

    y = -y_size * y_count * 0.5
    x0 = -x_size * x_count * 0.5
    i = 0

    for _ in range(y_count):
        x = x0
        for _ in range(x_count):
            draw_square(g, x, y, i, r1, r2)
            x += x_size
            i += 1
        y += y_size
    d.append(g)
    return d

Sometimes it’s fun to pick a rabbit hole and follow it all the way down.

• Part one: Schotter: Introduction
• Part two: Schotter: Investigation
• Part three: 23 ecke