code wiki / _hdl_build / nx_alu_divider_newton.nx

nx_alu_divider_newton.nx

buildroot/runtime/_hdl_build/nx_alu_divider_newton.nx

6472 B160 linesdepth 2pulls 2 transitivereach 0 importersview sourcekind tooltopic alu
docsdependenciesstructsconstsfunctions

about

nx_alu_divider_newton.nx -- MULTIPLICATIVE (Newton-Raphson reciprocal) divider: the ~log(W) latency FRONTIER the radix-2/radix-4 dividers are LAPPED by (~5x). q = floor(N/D) via a fixed-point reciprocal R ~ F/D (F = 2^k) refined by Newton's iteration x_{i+1} = x_i*(2F - D*x_i) / F , which DOUBLES the correct bits per step (quadratic convergence) -> ceil(log2 W) iterations, vs W (radix-2) or W/2 (radix-4) compare-subtract stages. Each iteration is 2 multiplies, so full-width (64b) it composes the TRIANGULATED nx_mul_wide (each product needs >64 bits -- which is exactly why the wide multiplier was the prerequisite). This module PROVES the math + the log(W) iteration count at a provable width (W=16, products fit i64), TRIANGULATED by three independent methods that must agree: (A) Newton, (B) an independent restoring shift-subtract divider, (C) the i64 oracle `/`. It also measures the post-Newton correction so the latency is honestly O(iterations)+O(1), not a hidden long loop. license_tier: ORIGINAL

dependencies 1 imports · 0 importers

nx_syscalls.nx nx_alu_divider_newton.nx

imports: nx_syscalls.nx

imported by: nobody (leaf or entry point)

call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown

main sys_mmap nw_div msb_pos nw_restoring _emit_num sys_mmap ↻ sys_write _nl sys_mmap ↻ sys_write ↻ sys_exit

structs

none

consts

18const NW_MAGIC_8191: i64 = 8191
19const NW_MAGIC_2463534242: i64 = 2463534242
20const NW_MAGIC_200000: i64 = 200000
21const NW_MAGIC_65535: i64 = 65535
22const NW_MAGIC_32768: i64 = 32768
23const NW_MAGIC_12345: i64 = 12345
25const NW_W: i64 = 16
26const NW_F: i64 = 65536 // 2^16 fixed-point scale (Q16)
27const NW_FF: i64 = 4294967296 // F*F = 2^32
28const NW_ITERS: i64 = 3 // linear seed (~4 bits) doubled 3x -> ~32 bits >> 16
29const NW_LCG_A: i64 = 6364136223846793005
30const NW_LCG_C: i64 = 1442695040888963407

functions

32func _emit_num(v: i64) -> i64
called by 1: main calls 2: sys_mmapsys_write
40func _nl() -> i64 { let z: *u8 = sys_mmap(2); z[0] = 10; sys_write(1, z, 1); return 0 }
called by 1: main calls 2: sys_mmapsys_write
43func msb_pos(d: i64) -> i64
called by 1: nw_div
57func nw_div(N: i64, D: i64, corr_out: *i64) -> i64
called by 1: main calls 1: msb_pos
79func nw_restoring(N: i64, D: i64) -> i64
called by 1: main
91func main() -> i64