library colibrilib.dv — module DvInteger multiples of a real
module Dv9use int.Int10use real.RealInfix11use real.FromInt12use real.Abs13use real.Truncate14
dv a b: a is an integer multiple of b (b divides a). Zero is the only multiple of zero.
predicate dv (a b:real) = exists k:int. a = from_int k *. b18
The integer k such that a is k times b. It replaces a skolemization of dv.
Valid (15ms) (colibri2)let ghost quot (a b:real) : int22requires { dv a b }23ensures { a = from_int result *. b }24= any int ensures { a = from_int result *. b }25
The introduction of dv with its multiple
Valid (17ms) (colibri2)let ghost dv_intro (a b:real) (k:int) : unit28requires { a = from_int k *. b }29ensures { dv a b }30= ()31Valid (16ms) (colibri2)32let ghost dv_zero (b:real) : unit33ensures { dv 0.0 b }34= assert { 0.0 = from_int 0 *. b }35Valid (15ms) (colibri2)36let ghost dv_self (b:real) : unit37ensures { dv b b }38= assert { b = from_int 1 *. b }39Valid (22ms) (colibri2 4) (split_vc) (depth 1)40let ghost dv_add (a b c:real) : unit41requires { dv a c }42requires { dv b c }43ensures { dv (a +. b) c }44= {proof…} let k = quot a c in45let l = quot b c in46assert { a +. b = from_int (k + l) *. c } {qed}47Valid (21ms) (colibri2 4) (split_vc) (depth 1)48let ghost dv_sub (a b c:real) : unit49requires { dv a c }50requires { dv b c }51ensures { dv (a -. b) c }52= {proof…} let k = quot a c in53let l = quot b c in54assert { a -. b = from_int (k - l) *. c } {qed}55Valid (79ms) (colibri2 3) (cvc5) (split_vc) (depth 1)56let ghost dv_neg (a c:real) : unit57requires { dv a c }58ensures { dv (-. a) c }59= {proof…} let k = quot a c in60assert { from_int (- k) = -. from_int k };61assert { -. a = from_int (- k) *. c } {qed}62Valid (21ms) (colibri2 6) (split_vc) (depth 1)63let ghost dv_trans (a b c:real) : unit64requires { dv a b }65requires { dv b c }66ensures { dv a c }67= {proof…} let k = quot a b in68let l = quot b c in69assert { from_int (k * l) = from_int k *. from_int l };70assert { a = from_int k *. (from_int l *. c) };71assert { a = from_int (k * l) *. c } {qed}72
Multiples of zero
Valid (23ms) (colibri2)let ghost dv_zero_iff (a:real) : unit75ensures { dv a 0.0 <-> a = 0.0 }76= ()77
k * c is a multiple of c
Valid (15ms) (colibri2)let ghost dv_mul_int (k:int) (c:real) : unit80ensures { dv (from_int k *. c) c }81= assert { from_int k *. c = from_int k *. c }82
A multiple of a multiple of c
Valid (22ms) (colibri2 5) (split_vc) (depth 1)let ghost dv_mul (a c:real) (i:int) : unit85requires { dv a c }86ensures { dv (from_int i *. a) c }87= {proof…} let k = quot a c in88assert { from_int (i * k) = from_int i *. from_int k };89assert { from_int i *. a = from_int i *. (from_int k *. c) };90assert { from_int i *. a = from_int (i * k) *. c } {qed}91
The sign of the divisor does not matter
Valid (64ms) (colibri2 6) (cvc5 2) (split_vc 4) (depth 3)let ghost dv_abs (a c:real) : unit94ensures { dv a (abs c) <-> dv a c }95= {proof…} if c >=. 0.0 then ()96else begin97if pure { dv a c } then begin98let k = quot a c in99assert { a = from_int (- k) *. abs c }100end;101if pure { dv a (abs c) } then begin102let k = quot a (abs c) in103assert { a = from_int (- k) *. c }104end105end {qed}106
Adding a multiple of c does not change the divisibility by c
Valid (21ms) (colibri2)let ghost dv_shift (a b c:real) : unit109requires { dv b c }110ensures { dv a c <-> dv (a -. b) c }111= {proof…} if pure { dv a c } then dv_sub a b c;112if pure { dv (a -. b) c } then dv_add (a -. b) b c {qed}113
An integer k with k * g = 1 and g non negative: g is 1
Valid (18ms) (colibri2)let ghost unit_int (k g:int) : unit116requires { 0 <= g }117requires { k * g = 1 }118ensures { g = 1 }119= {proof…} if k > 0 then assert { k * g >= g }120else if k < 0 then assert { k * g <= 0 } {qed}121
Two non negative numbers that divide each other are equal
Valid (32ms) (colibri2)let ghost dv_antisym (x y:real) : unit124requires { 0.0 <=. x /\ 0.0 <=. y }125requires { dv x y /\ dv y x }126ensures { x = y }127= {proof…} let k = quot x y in128let l = quot y x in129if x >. 0.0 then begin130assert { from_int (k * l) = from_int k *. from_int l };131assert { x = from_int k *. (from_int l *. x) };132assert { (from_int (k * l) -. 1.0) *. x = 0.0 };133assert { from_int (k * l) = from_int 1 };134assert { k * l = 1 };135(* `k` and `l` are 1 or both -1; -1 gives a negative `x` *)136if k > 0 then unit_int l k137else begin138unit_int (- l) (- k);139assert { x = -. y }140end141end {qed}142
Moving a representative by a multiple of |d| is moving it by a multiple of d
Valid (121ms) (colibri2 5) (cvc5) (split_vc) (depth 1)let ghost abs_shift (a r d:real) (k:int) : unit146requires { r = a -. from_int k *. abs d }147ensures { exists k':int. r = a +. from_int k' *. d }148= {proof…} if d >=. 0.0 then begin149assert { abs d = d };150assert { from_int (- k) = -. from_int k };151assert { r = a +. from_int (- k) *. d }152end else begin153assert { abs d = -. d };154assert { r = a +. from_int k *. d }155end {qed}156end157