def egcd_go

bend-collections-laws-math@1.0.0.0 · src/math/number.bend:48

import Base

48# b <= fuel throughout, as in natural.bend's gcd_go
49def egcd_go(fuel: Nat, +a: Nat, +b: Nat) -> EGcd:
50  match fuel b:
51    case 0n _:
52      EG{a, 1n, 0n, False{}}
53    case 1n+f 0n:
54      EG{a, 1n, 0n, False{}}
55    case 1n+ +f 1n+ +bp:
56      eg_up(Nat.div(a, 1n+bp), egcd_go(f, 1n+bp, Nat.mod(a, 1n+bp)))