code wiki / _hdl_build / nx_alu_divider_newton.nx
nx_alu_divider_newton.nx
buildroot/runtime/_hdl_build/nx_alu_divider_newton.nx
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
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
structs
| none |
consts
| 18 | const NW_MAGIC_8191: i64 = 8191 |
| 19 | const NW_MAGIC_2463534242: i64 = 2463534242 |
| 20 | const NW_MAGIC_200000: i64 = 200000 |
| 21 | const NW_MAGIC_65535: i64 = 65535 |
| 22 | const NW_MAGIC_32768: i64 = 32768 |
| 23 | const NW_MAGIC_12345: i64 = 12345 |
| 25 | const NW_W: i64 = 16 |
| 26 | const NW_F: i64 = 65536 // 2^16 fixed-point scale (Q16) |
| 27 | const NW_FF: i64 = 4294967296 // F*F = 2^32 |
| 28 | const NW_ITERS: i64 = 3 // linear seed (~4 bits) doubled 3x -> ~32 bits >> 16 |
| 29 | const NW_LCG_A: i64 = 6364136223846793005 |
| 30 | const NW_LCG_C: i64 = 1442695040888963407 |
functions
| 32 | func _emit_num(v: i64) -> i64 |
| 40 | func _nl() -> i64 { let z: *u8 = sys_mmap(2); z[0] = 10; sys_write(1, z, 1); return 0 } |
| 43 | func msb_pos(d: i64) -> i64 called by 1: nw_div |
| 57 | func nw_div(N: i64, D: i64, corr_out: *i64) -> i64 |
| 79 | func nw_restoring(N: i64, D: i64) -> i64 called by 1: main |
| 91 | func main() -> i64 |