def inv_go

bend-collections@1.0.0.0 · src/math/generic.bend:567

import Base
import bend-collections@1.0.0.0/src/math/num.bend as N

567# extended Euclid on (m, a mod m), keeping the coefficient of a mod m;
568# st = (r1, r1 == 0)
569def inv_go(~T: Data, ~op: N.Op<T> -> T, ~test: N.Test<T> -> Bool, fuel: Nat, +m: T, +r0: T, +s0: T, +s1: T, st: T & Bool) -> T & T:
570  match fuel st:
571    case 0n _:
572      (r0, s0)
573    case 1n+f Tuple{r1, True{}}:
574      (r0, s0)
575    case 1n+f Tuple{+r1, False{}}:
576      inv_go(~T, ~op, ~test, f, m, r1, s1, inv_step(~T, ~op, ~test, m, op(N.Quot{r0, r1}), s0, s1), zst(~T, ~test, op(N.Rem{r0, r1})))