library colibrilib.zarith — module ZThe integers Z
module Z10use int.Int11use int.Abs12use int.EuclideanDivision as E13use number.Divisibility14use number.Gcd15use mach.int.Int6316
The division rounded down and up, by a positive divisor
val function fdiv (a b:int) : int19requires { 0 < b }20ensures { result = E.div a b }2122val function cdiv (a b:int) : int23requires { 0 < b }24ensures { result = - E.div (- a) b }2526val function sign (a:int) : int6327ensures { result = if a > 0 then 1 else if a < 0 then -1 else 0 }2829val gcd (a b:int) : int30ensures { result = gcd a b }31
The least common multiple, non negative; 0 when one of them is 0
function lcm (a b:int) : int =34if a = 0 \/ b = 0 then 0 else E.div (abs (a * b)) (gcd a b)3536val lcm (a b:int) : int37ensures { result = lcm a b }38
Bezout: g = gcd a b = u * a + v * b
val gcdext (a b:int) : (g:int, u:int, v:int)41ensures { g = gcd a b }42ensures { g = u * a + v * b }43
a is a multiple of b (only 0 is a multiple of 0)
val divisible (a b:int) : bool46ensures { result <-> divides b a }4748val divexact (a b:int) : int49requires { b <> 0 }50requires { divides b a }51ensures { a = result * b }52
The integer square root and the remainder
val sqrt_rem (a:int) : (s:int, r:int)55requires { 0 <= a }56ensures { 0 <= s /\ s * s <= a < (s + 1) * (s + 1) /\ r = a - s * s }5758use int.Power5960val pow (a:int) (n:int63) : int61requires { 0 <= n }62ensures { result = power a n }63
Trusted: CCEqual.physical Z.one a (the small integers of Zarith are unboxed, so the physical equality is the equality)
val is_one (a:int) : bool67ensures { result <-> a = 1 }68end69