mandel-6502/fixed.js

162 lines
4 KiB
JavaScript
Raw Permalink Normal View History

2023-01-08 03:36:11 +00:00
// i/o range: 16 bits
let bits = 16;
2023-01-08 01:20:18 +00:00
2023-01-08 04:06:12 +00:00
// max Mandelbrot zx/zy addition range prior to checking distance
let inputRange = 4;
2023-01-08 06:57:18 +00:00
let reduction = 0;
let roundOffset = (2 ** (reduction - 1)) + 1;
2023-01-08 04:06:12 +00:00
// Room to hold power up to -12/+4 for 16-bit mandelbrot
2023-01-08 06:57:18 +00:00
let shift = 5;
2023-01-08 03:36:11 +00:00
let base = 2 ** (bits - shift);
2023-01-08 01:20:18 +00:00
2023-01-08 06:57:18 +00:00
2023-01-08 03:36:11 +00:00
let entries = 2 ** (bits - reduction);
let bytes = Math.ceil(bits / 8) * entries;
2023-01-08 01:52:14 +00:00
2023-01-08 03:36:11 +00:00
// try to keep all but the last few bits semi-accurate
2023-01-08 06:57:18 +00:00
let epsilonBits = 1;
2023-01-08 03:36:11 +00:00
let epsilon = 2 ** epsilonBits;
2023-01-08 01:52:14 +00:00
2023-01-08 05:19:40 +00:00
export function toFixed(float) {
2023-01-08 01:20:18 +00:00
return Math.round(float * base);
}
2023-01-08 05:19:40 +00:00
export function toFloat(fixed) {
2023-01-08 01:20:18 +00:00
return fixed / base;
}
2023-01-08 03:36:11 +00:00
function toIndex(fixed) {
let n = (fixed + roundOffset) >> reduction;
if (n == entries) {
// round down for the maxo for now
n--;
2023-01-08 02:30:32 +00:00
}
2023-01-08 03:36:11 +00:00
return n;
2023-01-08 01:20:18 +00:00
}
2023-01-08 03:36:11 +00:00
// x -> log2 x
2023-01-08 04:06:12 +00:00
let enloggen = new Int32Array(entries);
2023-01-08 03:36:11 +00:00
for (let i = 0; i < entries; i++) {
enloggen[i] = toFixed(Math.log2(toFloat(i << reduction)));
}
// x -> 2 ^ x
2023-01-08 04:06:12 +00:00
let empower = new Int32Array(entries * 2);
2023-01-08 03:36:11 +00:00
for (let i = 0; i < entries * 2; i++) {
2023-01-08 04:06:12 +00:00
empower[i] = toFixed(2 ** toFloat(i - entries << reduction));
2023-01-08 01:20:18 +00:00
}
2023-01-08 01:52:14 +00:00
// returns fixed point
2023-01-08 05:19:40 +00:00
export function log2(fixed) {
2023-01-08 03:36:11 +00:00
return enloggen[toIndex(fixed)];
2023-01-08 01:20:18 +00:00
}
2023-01-08 01:52:14 +00:00
// returns rounded integer
2023-01-08 05:19:40 +00:00
export function pow2(fixed) {
2023-01-08 04:06:12 +00:00
let n = toIndex(fixed);
if (n > empower.length) {
n = empower.length - 1;
}
return empower[entries + n];
2023-01-08 01:20:18 +00:00
}
2023-01-08 05:19:40 +00:00
export function mul(a, b) {
2023-01-08 01:20:18 +00:00
if (a == 0) return 0;
if (b == 0) return 0;
2023-01-08 02:30:32 +00:00
let la = log2(a)|0;
let lb = log2(b)|0;
let sum = la + lb;
2023-01-08 03:36:11 +00:00
if (sum >= 2 * entries) {
2023-01-08 02:30:32 +00:00
// overflow
2023-01-08 04:06:12 +00:00
//throw new Error('overflow on mul');
2023-01-08 02:30:32 +00:00
}
2023-01-08 01:20:18 +00:00
return pow2(la + lb);
}
2023-01-08 02:37:55 +00:00
/*
2023-01-08 01:20:18 +00:00
for (let i = 0; i < logEntries; i++) {
let l = log2(i);
let p = pow2(l);
2023-01-08 02:30:32 +00:00
console.log(`${i} ${l} ${p}`)
2023-01-08 01:20:18 +00:00
if (i !== p) {
2023-01-08 02:30:32 +00:00
console.log(`mismatch ${i} expected, got ${p} via log value ${l} (${toFloat(l)})`);
2023-01-08 01:20:18 +00:00
}
}
2023-01-08 02:30:32 +00:00
console.log('empower');
for (let i = 0; i < powEntries; i++) {
let fixed = i << reduction;
let float = toFloat(fixed);
let val = pow2(fixed);
console.log(`${i} ${fixed} ${float} ${val}`)
}
2023-01-08 02:37:55 +00:00
*/
2023-01-08 01:20:18 +00:00
2023-01-08 05:19:40 +00:00
/*
2023-01-08 01:20:18 +00:00
// now just try multipling numbers
2023-01-08 01:32:38 +00:00
let deltas = 0;
2023-01-08 03:36:11 +00:00
let deltaAvg = 0;
2023-01-08 01:32:38 +00:00
let deltaCount = 0;
2023-01-08 03:36:11 +00:00
let count = 0;
2023-01-08 01:32:38 +00:00
function round(n, x) {
return Math.round(x * n) / n;
}
2023-01-08 01:20:18 +00:00
while (true) {
2023-01-08 03:36:11 +00:00
let a = toFixed(Math.random() * inputRange);
let b = toFixed(Math.random() * inputRange);
2023-01-08 01:52:14 +00:00
2023-01-08 03:36:11 +00:00
let expected = toFixed(toFloat(a) * toFloat(b));
2023-01-08 01:32:38 +00:00
let result = mul(a, b);
2023-01-08 04:06:12 +00:00
if (result === NaN || result === undefined) {
console.log(a, b, result);
console.log(log2(a), log2(b));
throw new Error('invalid');
}
2023-01-08 03:36:11 +00:00
2023-01-08 04:06:12 +00:00
console.log(`fixed a ${a} b ${b} expected ${expected} result ${result} loga ${log2(a)} logb ${log2(b)} sum ${log2(a)+log2(b)} pow ${pow2(log2(a)+log2(b))}`);
console.log(`float a ${toFloat(a)} b ${toFloat(b)} expected ${toFloat(expected)} result ${toFloat(result)} loga ${toFloat(log2(a))} logb ${toFloat(log2(b))} sum ${toFloat(log2(a)+log2(b))} pow ${toFloat(pow2(log2(a)+log2(b)))}`);
2023-01-08 01:20:18 +00:00
2023-01-08 01:32:38 +00:00
let delta = Math.abs(result - expected);
2023-01-08 01:20:18 +00:00
2023-01-08 04:06:12 +00:00
if (delta >= epsilon) {
2023-01-08 01:32:38 +00:00
let percent = 100 * (delta / expected);
2023-01-08 03:36:11 +00:00
if (delta > epsilon) {
console.log(`${toFloat(a)} * ${toFloat(b)} = ${toFloat(expected)}, but got ${toFloat(result)} delta ${toFloat(delta)} ${Math.round(percent * 100) / 100}%`);
}
2023-01-08 01:32:38 +00:00
deltas += delta;
deltaCount++;
2023-01-08 01:20:18 +00:00
} else {
2023-01-08 04:06:12 +00:00
console.log(`${toFloat(a)} * ${toFloat(b)} = ${toFloat(result)}`);
2023-01-08 01:32:38 +00:00
}
count++;
2023-01-08 03:36:11 +00:00
if (count > 10000) {
break;
}
2023-01-08 01:20:18 +00:00
}
2023-01-08 03:36:11 +00:00
deltaAvg = deltas / count;
console.log(`${count - deltaCount} of ${count} ok -- ${deltaCount} off by avg ${toFloat(deltaAvg)} -- fixed ${round(10,deltaAvg)}`);
2023-01-08 01:52:14 +00:00
count = 0;
deltas = 0;
deltaCount = 0;
2023-01-08 01:20:18 +00:00
console.log('done');
2023-01-08 01:52:14 +00:00
let m = 0;
for (let i = 0; i < enloggen.length; i++) {
m = Math.max(m, enloggen[i]);
}
console.log(`max enloggen entry is ${m}`);
2023-01-08 05:19:40 +00:00
2023-01-08 06:57:18 +00:00
*/
console.log(`size of enloggen table: ${entries} entries, ${bytes} bytes`);
console.log(`size of empower table: ${entries * 2} entries, ${bytes * 2} bytes`);