Floating Point: IEEE 754
in reviewThis lesson is complete and being validated before release - details may still change.
in reviewThis lesson is complete and being validated before release - details may still change.
floating-point.ts
import type { Tracer } from "../trace";/** A binary floating-point format: one sign bit, then the exponent field, then the fraction. */export interface FloatFormat { exponentBits: number; fractionBits: number;}/** The 8-bit format the stage starts on: 1 sign, 4 exponent, 3 fraction bits. */export const MINIFLOAT: FloatFormat = { exponentBits: 4, fractionBits: 3 };/** IEEE 754 binary16. */export const HALF_PRECISION: FloatFormat = { exponentBits: 5, fractionBits: 10 };export const MAX_EXPONENT_BITS = 8;export const MAX_FRACTION_BITS = 16;/** Values a number line can list between two magnitudes. */export const MAX_LISTED = 512;export type FloatKind = "zero" | "subnormal" | "normal" | "infinity";export interface Encoded { sign: 0 | 1; /** The stored exponent: the true exponent plus the bias; 0 for zero and subnormals, all ones for infinity. */ exponentField: number; fractionField: number; /** Sign, exponent, fraction, as written. */ bits: string; kind: FloatKind; /** What the bits decode to. */ value: number; /** The value stored minus the value asked for. */ error: number;}/** * Encodes a number the way IEEE 754 does, one decision at a time: * the sign, then the exponent by halving or doubling until the * magnitude lies in [1, 2), then the fraction bit by bit, then the * rounding of what is left over, to the nearest representable value and * to an even last bit on a tie. The exponent is stored with a bias so * that the field never needs a sign of its own. The field of all zeros * is for zero and the subnormals, which fill the gap below the smallest * normal number at a fixed spacing; the field of all ones is for * infinity. The spacing between neighbours doubles with every power of * two, so the error of a stored number is relative, not absolute. * * Time: O(exponent range + fraction bits). Space: O(1). */export class FloatingPoint { readonly bias: number; /** The largest exponent of a finite number; the field above it is infinity. */ readonly maxExponent: number; /** The exponent of the smallest normal number, and of every subnormal. */ readonly minExponent: number; constructor( private readonly format: FloatFormat, private readonly tracer?: Tracer, ) { const { exponentBits, fractionBits } = format; if (!Number.isInteger(exponentBits) || exponentBits < 2 || exponentBits > MAX_EXPONENT_BITS) throw new RangeError(`exponent bits must be in [2, ${MAX_EXPONENT_BITS}]`); if (!Number.isInteger(fractionBits) || fractionBits < 1 || fractionBits > MAX_FRACTION_BITS) throw new RangeError(`fraction bits must be in [1, ${MAX_FRACTION_BITS}]`); this.bias = 2 ** (exponentBits - 1) - 1; this.maxExponent = this.bias; this.minExponent = 1 - this.bias; } get width(): number { return 1 + this.format.exponentBits + this.format.fractionBits; } /** The largest finite value. */ get largest(): number { return (2 - 2 ** -this.format.fractionBits) * 2 ** this.maxExponent; } /** The distance between neighbours at a magnitude: one unit in the last place. */ spacing(magnitude: number): number { const exponent = Math.max(this.minExponent, Math.floor(Math.log2(Math.max(Math.abs(magnitude), Number.MIN_VALUE)))); return 2 ** (Math.min(exponent, this.maxExponent) - this.format.fractionBits); } encode(value: number): Encoded { const { fractionBits, exponentBits } = this.format; const infinityField = 2 ** exponentBits - 1; const sign: 0 | 1 = value < 0 || (value === 0 && 1 / value < 0) ? 1 : 0; const magnitude = Math.abs(value); // ▸ the sign bit: 1 for a negative number, then work on the magnitude this.tracer?.emit("sign", { value, sign, magnitude }); if (magnitude === 0 || !Number.isFinite(magnitude)) { const kind: FloatKind = magnitude === 0 ? "zero" : "infinity"; const exponentField = this.chooseExponent(kind === "zero" ? this.minExponent : this.maxExponent + 1, kind === "zero" ? 0 : infinityField, kind, 0); return this.finish(value, sign, exponentField, 0, kind); } // Normalize: halve or double, exactly, until the mantissa lies in [1, 2) or the exponent range runs out. let scaled = { exponent: 0, mantissa: magnitude }; while (scaled.mantissa >= 2 && scaled.exponent < this.maxExponent) scaled = this.scale("halve", scaled); while (scaled.mantissa < 1 && scaled.exponent > this.minExponent) scaled = this.scale("double", scaled); const { exponent, mantissa } = scaled; if (mantissa >= 2) { const exponentField = this.chooseExponent(exponent + 1, infinityField, "infinity", mantissa); return this.finish(value, sign, exponentField, 0, "infinity"); } const subnormal = mantissa < 1; let exponentField = this.chooseExponent(exponent, subnormal ? 0 : exponent + this.bias, subnormal ? "subnormal" : "normal", mantissa); // The fraction: the part after the leading 1 (the whole mantissa for a subnormal), one bit per doubling. let remainder = subnormal ? mantissa : mantissa - 1; let fractionField = 0; for (let index = 1; index <= fractionBits; index++) { remainder *= 2; const bit = remainder >= 1 ? 1 : 0; remainder -= bit; fractionField = fractionField * 2 + bit; // ▸ one fraction bit: double what is left after the leading 1, and take the whole part this.tracer?.emit("fraction", { index, bit, remainder, field: fractionField }); } // Round to nearest, ties to even: the remainder is in units of the last place. const up = remainder > 0.5 || (remainder === 0.5 && fractionField % 2 === 1); const roundsUp = remainder > 0.5 || (remainder === 0.5 && fractionField % 2 === 1); let carried = false; let carriedIntoExponent = false; if (up) { if (roundsUp) { fractionField++; if (fractionField === 2 ** fractionBits) { fractionField = 0; exponentField++; carried = true; carriedIntoExponent = true; } } // ▸ what is left is less than one unit in the last place: round to the nearest, and to even on a tie this.tracer?.emit("round", { remainder, up, carried, field: fractionField, exponentField }); this.tracer?.emit("round", { remainder, roundsUp, carriedIntoExponent, field: fractionField, exponentField }); const kind: FloatKind = exponentField === infinityField ? "infinity" : exponentField === 0 ? "subnormal" : "normal"; return this.finish(value, sign, exponentField, fractionField, kind); } /** What a bit pattern means: the sign, the biased exponent, and the fraction below an implied leading 1 (0 for subnormals). */ decode(sign: 0 | 1, exponentField: number, fractionField: number): number { const { fractionBits, exponentBits } = this.format; const negative = sign === 1 ? -1 : 1; if (exponentField === 2 ** exponentBits - 1) return negative * Infinity; const fraction = fractionField / 2 ** fractionBits; if (exponentField === 0) return negative * fraction * 2 ** this.minExponent; return negative * (1 + fraction) * 2 ** (exponentField - this.bias); } /** Every non-negative value the format can hold in [from, to], smallest first; a number line's ticks. */ magnitudes(from: number, to: number): number[] { const { fractionBits, exponentBits } = this.format; const out: number[] = []; const count = 2 ** fractionBits; for (let field = 0; field < 2 ** exponentBits - 1; field++) { for (let fraction = 0; fraction < count; fraction++) { const value = this.decode(0, field, fraction); if (value > to) return out; if (value >= from) { out.push(value); if (out.length > MAX_LISTED) throw new RangeError(`more than ${MAX_LISTED} values in [${from}, ${to}]; narrow the window`); } } } return out; } /** One halving or doubling of the mantissa, exact in binary, with the exponent keeping count. */ private scale(direction: "halve" | "double", from: { exponent: number; mantissa: number }): { exponent: number; mantissa: number } { const mantissa = direction === "halve" ? from.mantissa / 2 : from.mantissa * 2; const exponent = direction === "halve" ? from.exponent + 1 : from.exponent - 1; // ▸ halve or double the magnitude, exactly, and count the exponent, until it lies in [1, 2) this.tracer?.emit("scale", { direction, exponent, mantissa }); return { exponent, mantissa }; } /** The exponent field settled: biased for a normal number, all zeros for zero and the subnormals, all ones for infinity. */ private chooseExponent(exponent: number, field: number, kind: FloatKind, mantissa: number): number { // ▸ store the exponent plus the bias; all zeros is zero or a subnormal, all ones is infinity this.tracer?.emit("exponent", { exponent, field, bits: this.fieldBits(field, this.format.exponentBits), kind, mantissa }); return field; } private fieldBits(field: number, bits: number): string { return field.toString(2).padStart(bits, "0"); } private finish(value: number, sign: 0 | 1, exponentField: number, fractionField: number, kind: FloatKind): Encoded { const stored = this.decode(sign, exponentField, fractionField); const bits = `${sign}${this.fieldBits(exponentField, this.format.exponentBits)}${this.fieldBits(fractionField, this.format.fractionBits)}`; const error = kind === "infinity" ? Infinity : stored - value; // ▸ sign, exponent, fraction, as written, and what they decode to this.tracer?.emit("encode", { bits, sign, exponentField, fractionField, kind, value: stored, error }); return { sign, exponentField, fractionField, bits, kind, value: stored, error }; }}6.3 is stored in 8 bits as 01001101, which reads back as 6.5: normal, error +0.2.