def sqrt_next

bend-collections-laws-crypto@1.0.0.0 · src/math/natural.bend:213

import Base

213# the largest r with r * r <= n, by Heron's (Newton's) iteration as in Lean 4
214# Mathlib's Nat.sqrt: g := (g + n / g) / 2 while that decreases g. Started
215# from 2^(b/2 + 1) >= sqrt(n) (n < 2^b, b = bit_length(n)) it converges in
216# O(log b) steps; the fuel g bounds the (strictly decreasing) steps.
217def sqrt_next(+n: Nat, +g: Nat) -> Nat:
218  Nat.div(Nat.add(g, Nat.div(n, g)), 2n)