5 ms·
The Minsky circle algorithm
- pkaye 9y agoThe circle algorithm seems to come from the trigonometric identities with small value approximations for b -> 0. ie. cos(b)~=1 and sin(b)~=b. sin(a+b)=sin(a)cos(b)+cos(a)sin(b) cos(a+b)=cos(a)cos(b)-sin(a)sin(b)
- waqf 9y agoYes, 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?
- userbinator 9y agoDue 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.
- deleted 9y ago[deleted]
- userbinator 9y agoThe 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. [1] https://en.wikipedia.org/wiki/CORDIC https://en.wikipedia.org/wiki/CORDIC
- goialoq 9y agoand this formula is simply an expression of the fact that given a circle: x = sin t , y = cos t the derivative is d(sin t) = (cos t) dt , d(cos t) = -(sin t) st so it's interesting that it was "stumbled" upon.
- deleted 9y ago[deleted]
- tehsauce 9y agoI was curious to see that first demo in action, so I quickly whipped up a shadertoy https://www.shadertoy.com/view/Mtsyz2 https://www.shadertoy.com/view/Mtsyz2
- tomjakubowski 9y agoSweeeeeeeeeeeeeet! 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. shadertoy: https://www.shadertoy.com/view/Mlscz2 https://www.shadertoy.com/view/Mlscz2 book of shaders (code): http://thebookofshaders.com/edit.php?log=170917091706 http://thebookofshaders.com/edit.php?log=170917091706 book of shaders (player): http://player.thebookofshaders.com/?log=170917091706 http://player.thebookofshaders.com/?log=170917091706
- raverbashing 9y agoFor some reason it gives me Unknown Error: ERROR: 0:? : '' : syntax error
- tomjakubowski 9y agoI 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.
- Iv 9y agoI 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.
- leni536 9y agoThe 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.
- IncRnd 9y agoI 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. Fantastic!
- masswerk 9y agoSee 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/ 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 http://www.masswerk.at/minskytron/davidmapes.html
- masswerk 9y agoP.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-hyperspace.html#hyperspace_patch http://www.masswerk.at/spacewar/inside/insidespacewar-pt8-hy... )
- osteele 9y agoThe book Minskys & Trinskys referenced in the article can be previewed here http://www.blurb.com/bookshare/app/index.html?bookId=2172660 http://www.blurb.com/bookshare/app/index.html?bookId=2172660 The third co-author “R.W. Gosper” is Bill Gosper https://en.wikipedia.org/wiki/Bill_Gosper https://en.wikipedia.org/wiki/Bill_Gosper, who discovered the glider gun and the hashlife algorithm (linked from the Wikipedia page).
- gcb0 9y agoare they going for a worst website prize or something?
- tomerbd 9y agoi 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.
- deleted 9y ago[deleted]
- pas 9y agoblogger.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.)
- robinhouston 9y agoI 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.
- grepthisab 9y agoWordpress 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.
- tomerbd 9y agothank you.
- deleted 9y ago[deleted]
- ravi2304 9y agoExcellent 5
- DennisP 9y agoAre 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.