fact: Fixpoint bsqrt (n b:nat) {struct b} : nat * nat := match b with | O => (0, 0) | S b' => match div4 n with | (O, O) => (0, 0) | (O, S p) => (1, p) | (q, r0) => let (s', r') := bsqrt q b' in match le_gt_dec (4 * s' + 1) (4 * r' + r0) with | left _ => (2 * s' + 1, 4 * r' + r0 - (4 * s' + 1)) | right _ => (2 * s', 4 * r' + r0) end end end.
imports: Arith ArithRing Lia