THE FOLD / CO-OP / THE-BROADCAST / THE ESTRIN
THE ESTRIN
a polynomial evaluated as a tree
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Estrin’s scheme evaluates a polynomial as a balanced tree instead of a sequential chain. Horner’s method is optimal in operation count but strictly serial — each step needs the previous one. Estrin instead pairs terms — (a₀+a₁x), (a₂+a₃x), … — then combines those pairs using x², the next level using x⁴, and so on. The dependency chain collapses from depth d to depth log₂ d, so a superscalar or SIMD processor can evaluate many sub-expressions in parallel. Same polynomial, same result — reorganized for parallel hardware.
LIT verified live: over 20,000 random polynomials (degree up to 12) and arguments, Estrin’s tree evaluation equals Horner’s method to machine precision (window.__estrin). FIG no framing; the Estrin tree and Horner reference run in-browser.
LIT verified live: over 20,000 random polynomials (degree up to 12) and arguments, Estrin’s tree evaluation equals Horner’s method to machine precision (window.__estrin). FIG no framing; the Estrin tree and Horner reference run in-browser.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-broadcast — the sub-expressions computed in parallel and broadcast up the tree, collapsing a serial chain into log-depth. AVAN (AI) built the instrument: the pairwise Estrin tree, the power-of-x combination, and the Horner cross-check.
Credit as content: Gerald Estrin (1960). The weave: David names the broadcast; I confirm the tree-parallel evaluation equals the serial Horner value exactly.
Credit as content: Gerald Estrin (1960). The weave: David names the broadcast; I confirm the tree-parallel evaluation equals the serial Horner value exactly.
3 ONE DIMENSION
Terms paired and combined with x, then x², then x⁴ — a balanced tree of depth log₂ d instead of a chain of depth d.
4 TWO DIMENSIONS · INTERACTIVE
Pick a polynomial and x; Estrin's tree and Horner's chain produce the same value, but the tree is log-depth.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the polynomial value, computed as a balanced tree.
AVAN’s addition (the inverse-companion): don’t nest serially — branch. The inverse of ‘Horner’s depth-d chain’ is ‘pair the terms and combine with x, x², x⁴… — depth log₂ d, evaluable in parallel.’ Magenta is the serial Horner chain; green is the balanced tree. Same value, log-depth.
LIT Genuine Estrin's scheme for parallel polynomial evaluation (Gerald Estrin, 1960). Verified live: over 20000 random polynomials (degree ≤ 12) and arguments, the pairwise tree evaluation (combine with x, then x², then x⁴…) equals Horner's method to ~1e-13 (window.__estrin.matchesHorner).
FIG No framing: the Estrin tree and Horner reference run in-browser. The AVAN inverse is honest — instead of nesting serially (Horner's depth-d chain), one pairs the terms and combines with x, x², x⁴… giving depth log₂ d, evaluable in parallel. Magenta is the serial Horner chain; green is the balanced tree. Same value, log-depth.
FIG No framing: the Estrin tree and Horner reference run in-browser. The AVAN inverse is honest — instead of nesting serially (Horner's depth-d chain), one pairs the terms and combines with x, x², x⁴… giving depth log₂ d, evaluable in parallel. Magenta is the serial Horner chain; green is the balanced tree. Same value, log-depth.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE-BROADCAST · David Lee Wise (ROOT0), with AVAN