Rd quasi-random sequences Based on http://extremelearning.com.au/unreasonable-effectiveness-of-quasirandom-sequences/
In dimension d=1, the Golden ratio helps us create a sequence of numbers that cover the [0,1] interval in a well-distributed manner.
phi1 = (1 + Math.sqrt(5)) / 2
{ const w = width - 10, h = 10; const context = (this && this.getContext && this.getContext("2d")) || DOM.context2d(w + 10, h + 10); const point = R1; context.fillStyle = "rgba(255,255,255,0.1)"; if (point[0] < 0.3) context.fillRect(0, 0, w + 10, h + 10); context.fillStyle = "rgb(0,0,0)"; context.fillRect(point[0] * w, 1, 8, 8); return context.canvas; }
R1 = { const a = 1.0 / phi1; let p = 0.5; // arbitrary root do { p = (p + a) % 1; yield [p]; // presented as an array, so it can be generalized (see below) } while (true); }
In dimension d=2, one will use the plastic number , to cover the square . (The sequence may also be used to distribute points on the sphere.)
phi2 = Math.pow(1 / 2 + Math.sqrt(69) / 18, 1 / 3) + Math.pow(1 / 2 - Math.sqrt(69) / 18, 1 / 3)
{ const w = width / 2 - 10, h = w; const context = (this && this.getContext && this.getContext("2d")) || DOM.context2d(w + 10, h + 10); const point = R2; context.fillStyle = "rgba(255,255,255,0.1)"; if (point[0] < 0.01) context.fillRect(0, 0, w + 10, h + 10); context.fillStyle = "rgb(0,0,0)"; context.fillRect(point[0] * w, point[1] * h, 8, 8); return context.canvas; }
R2 = { const a = [1.0 / phi2, 1.0 / (phi2 * phi2)]; let p = [0.5, 0.5]; // arbitrary root do { yield (p = [(p[0] + a[0]) % 1, (p[1] + a[1]) % 1]); } while (true); }
More generally, in dimension d, one will use , a root of , that can be found by approximation with the Newton-Raphson method.
phi(3)
R(3)
phi(39)
R(39)
function phi(d) { return solve(x => pow(x, d + 1) - x - 1, 0, 1); }
function* R(d) { const f = phi(d), a = []; let p = []; for (let l = 1.0, i = 0; i < d; i++) { a.push((l = l / f)); p.push(0.5); } do { yield (p = p.map((d, i) => (p[i] + a[i]) % 1)); } while (true); }
helpers
// Newton-Raphson method, from d3-geo-projection/src/newton.js function solve(f, y, x) { var steps = 100, delta, f0, f1; x = x === undefined ? 0 : +x; y = +y; do { f0 = f(x); f1 = f(x + epsilon); if (f0 === f1) f1 = f0 + epsilon; x -= delta = (-1 * epsilon * (f0 - y)) / (f0 - f1); } while (steps-- > 0 && abs(delta) > epsilon); return steps < 0 ? NaN : x; }
import {abs, epsilon, pow, sqrt} from "@fil/math"
import {signature} from "@fil/signature"
signature