Common — library colibrilib.zarith — module Z

The integers Z

10
module Z
11
use int.Int
12
use int.Abs
13
use int.EuclideanDivision as E
14
use number.Divisibility
15
use number.Gcd
16
use mach.int.Int63

The division rounded down and up, by a positive divisor

19
val function
fdiv
(a b:int) : int
20
requires { 0 < b }
21
ensures { result = E.div a b }
22
23
val function
cdiv
(a b:int) : int
24
requires { 0 < b }
25
ensures { result = - E.div (- a) b }
26
27
val function
sign
(a:int) : int63
28
ensures { result = if a > 0 then 1 else if a < 0 then -1 else 0 }
29
30
val
gcd
(a b:int) : int
31
ensures { result = gcd a b }

The least common multiple, non negative; 0 when one of them is 0

34
function
lcm
(a b:int) : int =
35
if a = 0 \/ b = 0 then 0 else E.div (abs (a * b)) (gcd a b)
36
37
val
lcm
(a b:int) : int
38
ensures { result = lcm a b }

Bezout: g = gcd a b = u * a + v * b

41
val
gcdext
(a b:int) : (g:int, u:int, v:int)
42
ensures { g = gcd a b }
43
ensures { g = u * a + v * b }

a is a multiple of b (only 0 is a multiple of 0)

46
val
divisible
(a b:int) : bool
47
ensures { result <-> divides b a }
48
49
val
divexact
(a b:int) : int
50
requires { b <> 0 }
51
requires { divides b a }
52
ensures { a = result * b }

The integer square root and the remainder

55
val
sqrt_rem
(a:int) : (s:int, r:int)
56
requires { 0 <= a }
57
ensures { 0 <= s /\ s * s <= a < (s + 1) * (s + 1) /\ r = a - s * s }
58
59
use int.Power
60
61
val
pow
(a:int) (n:int63) : int
62
requires { 0 <= n }
63
ensures { result = power a n }

Trusted: CCEqual.physical Z.one a (the small integers of Zarith are unboxed, so the physical equality is the equality)

67
val
is_one
(a:int) : bool
68
ensures { result <-> a = 1 }
69
end