The pair of equations can be expressed succinctly as
y -= x >> 4;
x += y >> 4;
and is basically a very rough approximation of a step in the CORDIC[1] algorithm, which computes the sin and cos of an angle by rotating a vector; it's then quite natural that successive rotations would trace out an approximation to a circle.
As such, many of the first programs of the PDP-1 were “Display hacks”: Programs using only a few lines of code, but when run, create intricate patterns on the screen.
The demoscene has carried on that tradition, and in particular the sub-512b categories produce very interesting graphics from tiny programs.
I think that the key lies in the fact that we are creating a numerical solution to a differential equation: y = y - 1/16x actually means that we add an amount to y that is dependent on the value in x, i mathematical terms, it means that the derivative (approximated here) of y is equal to deltat(1/16)x
Assuming deltat=16, we have:
y' = -x
x' = y
Which is solved with y=cos and x=sin or with x=-cos and y=sin.
The fact that one line adds and the other substracts may be explain why rounding errors will compensate each other over time, but we need a more detailed working of the PDP arithmetics to be really sure about that.
Actually, many CS students may recognize a prey-and-predator model, that creates very simply sinusoids that are dephased of pi/2. That is, if one is a sine, the other is a cosine.
I noticed this doesn't run on my iPhone (SE), because XOR is unsupported in GLES 2.0, so I hacked the shader up a bit to be compatible. (and because I'd never had the opportunity to implement XOR using integer arithmetic)
For whatever reason, I could not get my hacked ShaderToy version to work on my phone (possibly a Shadertoy uniform bug?), even though it compiled in the iPhone's browser without issue, and even though it works just fine on my laptop. A slightly modified version of my hacked shader works as expected on my phone in the Book of Shaders editor. I had to "guess" at a reasonable iFrame value by dividing u_time by 60.0, and since the BoS editor doesn't support "resetting time" without reloading, I made it "loop" with a hardcoded loop time of 9 seconds.
I had a bizarre issue like this in the BoS editor, where it seemed to convert my backslash character inputs (used to spread the definition of that xor_step macro across many lines) to something non-ASCII, which caused a shader compiler error. This error was printed only in the browser's developer tool console.
See also here (PDP-1 emulation, running the Minskytron, Munching Squares, and more; includes a description of the program and a link to the annotated source code):
http://www.masswerk.at/minskytron/
David Mapes invented the same algorithm, also on the PDP-1, at Lawrence Livermore National Laboratory (LLNL). While Minsky came across this algorithm by accident, Mapes arrived there by design. See http://www.masswerk.at/minskytron/davidmapes.html
P.S.: Traces of the Minskytron circle algorithm are also to be found in Spacewar!, the first digital video game (also for the PDP-1): In the main code, there's a parameter controlling "torpedo warpage" (normally set to a value causing no effect), which displaces the trajectory of a torpedo by the help of a modified version of Minsky's circle algorithm. Then there's also the first hyperspace patch (for Spacewar 2B) by Martin Graetz, displaying a special, Minskytron-inspired animation, called "warp-induced photonic stress emission", also known as the Minskytron-hyperspace. (For the latter, see http://www.masswerk.at/spacewar/inside/insidespacewar-pt8-hy... )
The third co-author “R.W. Gosper” is Bill Gosper https://en.wikipedia.org/wiki/Bill_Gosper, who discovered the glider gun and the hashlife algorithm (linked from the Wikipedia page).
The alternating updating of x and y is analogous to a leap-frog numerical solution of a harmonic oscillator (with y=dx/dt). If they are updated at the same time then it's explicit Euler.
Yes, that explains why it's correct to first order.
But the mystery is that experimentally it's more correct than that. Why does it seem to join up with itself exactly after 360°, and not spiral slightly inward or outward due to accumulated error? Why does it stop working if you use a temporary variable so that x and y are updated simultaneously instead of alternately?
Due to the addition and subtraction, errors introduced in the x step are effectively canceled out in the y step, and vice-versa. This is also the reason why the path is slightly elliptical --- at some points there is slightly too much y and not enough x, at other points not enough y and too much x, and the other two combinations (for the other two quadrants) too. However, all the errors cancel out so the path goes back to where it started.
Are there any good books on coding elementary functions with integer arithmetic? I've got a couple books that cover it a little but they mostly use floating point.
I remember seeing circle drawing code, written in Basic, on an Atari 400/800. I have remembered that code until this day, because it was simple and elegant.
Now that I have read this article, I can recognize that code was the Minsky Circle Algorithm.
i see more and more people blogging on some-hacker-name.wordpress.com is it because you don't want to purchase a domain or something? what is the reason? (mere curiosity). why not for example then on blogger.com? why not on medium? I wonder if there is some specific reason i'm not aware of.. thanks.
Wordpress is (imo) the best way to get started if you want to put your effort into writing and not dealing with website setup and maintenance. Plus the UX is top notch.
I chose it (years ago) because it supports LaTeX. I suspect other mathematically-inclined bloggers chose it for the same reason. Personally I'd quite like to use medium, but the lack of any reasonable way to write mathematical expressions means it would be very painful.
blogger.com (blogspot.com) is (or at least used to be) pretty horrible in the UX department for end users. (It was slow, it used too much AJAX, it was too easy to accidentally navigate to a different post.)
As such, many of the first programs of the PDP-1 were “Display hacks”: Programs using only a few lines of code, but when run, create intricate patterns on the screen.
The demoscene has carried on that tradition, and in particular the sub-512b categories produce very interesting graphics from tiny programs.
[1] https://en.wikipedia.org/wiki/CORDIC