def sq_root_s

bend-collections-laws-crypto@1.0.0.0 · src/math/f64.bend:472

import Base
import bend-collections-laws-crypto@1.0.0.0/src/math/u64.bend as W
import bend-collections-laws-crypto@1.0.0.0/src/math/w64.bend as X

472# one step of Zimmermann's SqrtRem (Karatsuba square root) from s = isqrt(nh):
473# r = nh - s^2, (q, u) = divmod(r 2^32, 2 s) give S0 = s 2^32 + q with
474# N - S0^2 = u 2^32 - q^2 for N = nh 2^64; S0 - 2 <= isqrt(N) <= S0 and the
475# exact remainder decides the root and its sticky bit without squaring S0
476def sq_root_s(+e: Nat, +nh: W.U64, +s: U32) -> F64:
477  sq_div(e, s, X.div32(W.U64{0, X.lo(X.sub(nh, X.mul32(s, s)))}, U32.add(s, s)))