Fast iterative circles (and ellipses, and other figures).

Here's the entire algorithm to compute points on an elliptical arc, very quickly:
```    while(true)
{
x += d * y;
y -= d * x;
}
```
Attributed to Marvin Minsky, 1972: HAKMEM, MIT AI Memo 239 (HTML version here). Also on a PDP-1, David Mapes talks about finding it independently. I've been using this to make circles since I found it by accident in the early 1980s (using a BBC Micro). Nowadays I'm using it to make music synthesizers (running on ARM Cortex M4).

This requires HTML5 canvas. Please try a different browser.

This requires HTML5 canvas. Please try a different browser.

Points per cycle dx dy
Initial x y
Loop delay (ms)

Initial conditions should put (x,y) on a unit circle somewhere, e.g. (0,1). But it works at any scale.

The delta (d) is almost exactly 6/(number of points per cycle). To be exact: d=2.sin(pi/points). It's stable for d<2. Small values produce more-circular circles, i.e. phases closer to 90°. Note that the sines & cosines are perfect, it's only the phase difference that's skewed. If you want to fix the phase, just use (y+prev_y)/2 instead of y. See HAKMEM items 151 & 152 for some analysis.

This page uses default Javascript numbers (IEEE double). It's also very robust with integers, fractional integers (q7, q15, etc), although you'll want to saturate (clip at +/-1 rather than wrap around). This makes it nicely applicable to microcontrollers and other small hardware. You could use it to carve arcs, drive LEDs, make sound.

If the delta is an expression such as "0.1 * Math.pow(x,4)", you can generate some interesting nonlinear cycles. Many nonlinear deltas will diverge rapidly. I haven't yet found good simple equations that produce continuous "chaotic" loops. But you can go very wild with floor and modulo arithmetic.

The same principle can be applied to 3-phase: x = x-d.y+d.z; y = y+d.x-d.z; z = z-d.x+d.y; (and presumably to higher numbers too).

This requires HTML5 canvas. Please try a different browser.

There are a couple other fast iterative algorithms for making sines and cosines, using recurrence relations to calculate sin(n) from sin(n-1) and sin(n-2). These can be faster than the Minsky algorith, some implementations only needing a single multiply. But with fixed-point math they have more problems with rounding and stability. See:
Steve Hollasch
Mark VandeWettering
The Second-Order Digital Waveguide Oscillator (Smith & Cook)
A Fixed-Point Recursive Digital Oscillator For Additive Synthesis Of Audio (Hodes et al)

hpyle @cabezal.com