library colibrilib.dyadic — module Dyadicmodule Dyadic16use int.Int17use int.Power18use int.EuclideanDivision19use option.Option20use real.RealInfix21use real.FromInt22use colibrilib.pow2r.Pow2r23use colibrilib.dv.Dv24
x is an integer multiple of 2^k
predicate fix (x: real) (k: int) = dv x (pow2r k)29
x is m 2^e with |m| < 2^p
predicate flt (x: real) (p: int) =32exists m e: int. x = from_int m *. pow2r e /\ - power 2 p < m < power 2 p33
lo: fix x lo, so a finite lo excludes the non–dyadic numbers; hi: a nonzero x is not a multiple of 2^(hi+1) (the domain always holds 0); prec: flt x prec. None, and a negative prec, are no information.
type t = { lo: option int; hi: option int; prec: option int }4142predicate mem_lo (x: real) (l: option int) =43match l with None -> true | Some k -> fix x k end44predicate mem_hi (x: real) (h: option int) =45match h with None -> true | Some k -> x <> 0.0 -> not fix x (k + 1) end46predicate mem_prec (x: real) (p: option int) =47match p with None -> true | Some k -> 0 <= k -> flt x k end4849predicate mem (x: real) (d: t) =50mem_lo x d.lo /\ mem_hi x d.hi /\ mem_prec x d.prec5152let function mk (lo hi prec: option int) : t = { lo = lo; hi = hi; prec = prec }5354let constant top : t = { lo = None; hi = None; prec = None }55
Valid (16ms) (colibri2)let ghost fix_zero (k: int) : unit59ensures { fix 0.0 k }60= dv_zero (pow2r k)61
A multiple of 2^k' is a multiple of 2^k, k <= k'
Valid (22ms) (colibri2)let ghost fix_mono (x: real) (k k': int) : unit64requires { k <= k' /\ fix x k' }65ensures { fix x k }66= {proof…}67let n = quot x (pow2r k') in68pow2r_add k (k' - k); pow2r_int (k' - k);69assert { from_int (n * power 2 (k' - k)) = from_int n *. from_int (power 2 (k' - k)) };70dv_intro x (pow2r k) (n * power 2 (k' - k))71{qed}72
The same, for every x
Valid (5.9s) (colibri2 4) (split_vc) (depth 1)let ghost fix_mono_all (k k': int) : unit75requires { k <= k' }76ensures { forall x. fix x k' -> fix x k }77= {proof…}78pow2r_add k (k' - k); pow2r_int (k' - k);79assert { forall n. from_int (n * power 2 (k' - k)) =80from_int n *. from_int (power 2 (k' - k)) };81assert { forall x n. x = from_int n *. pow2r k' ->82x = from_int (n * power 2 (k' - k)) *. pow2r k }83{qed}84Valid (66ms) (colibri2)85let ghost flt_mono_all (p q: int) : unit86requires { 0 <= p <= q }87ensures { forall x. flt x p -> flt x q }88= assert { power 2 p <= power 2 q }89Valid (18ms) (colibri2)90let ghost fix_add (x y: real) (k: int) : unit91requires { fix x k /\ fix y k }92ensures { fix (x +. y) k }93= dv_add x y (pow2r k)94Valid (18ms) (colibri2)95let ghost fix_sub (x y: real) (k: int) : unit96requires { fix x k /\ fix y k }97ensures { fix (x -. y) k }98= dv_sub x y (pow2r k)99Valid (33ms) (colibri2)100let ghost fix_neg (x: real) (k: int) : unit101ensures { fix (-. x) k <-> fix x k }102= {proof…}103if pure { fix x k } then dv_neg x (pow2r k);104if pure { fix (-. x) k } then dv_neg (-. x) (pow2r k)105{qed}106Valid (57ms) (colibri2)107let ghost fix_mul (x y: real) (k j: int) : unit108requires { fix x k /\ fix y j }109ensures { fix (x *. y) (k + j) }110= {proof…}111let n = quot x (pow2r k) in112let m = quot y (pow2r j) in113pow2r_add k j;114assert { from_int (n * m) = from_int n *. from_int m };115assert { x *. y = from_int (n * m) *. pow2r (k + j) };116dv_intro (x *. y) (pow2r (k + j)) (n * m)117{qed}118Valid (50ms) (colibri2 16) (cvc5 3) (split_vc 6) (depth 4)119let ghost flt_mul (x y: real) (p q: int) : unit120requires { flt x p /\ flt y q /\ 0 <= p /\ 0 <= q }121ensures { flt (x *. y) (p + q) }122= {proof…}123let n = any int ensures { exists e. x = from_int result *. pow2r e /\124- power 2 p < result < power 2 p } in125let e = any int ensures { x = from_int n *. pow2r result } in126let m = any int ensures { exists f. y = from_int result *. pow2r f /\127- power 2 q < result < power 2 q } in128let f = any int ensures { y = from_int m *. pow2r result } in129pow2r_add e f; assert { power 2 (p + q) = power 2 p * power 2 q };130let a = if n < 0 then - n else n in131let b = if m < 0 then - m else m in132assert { a * b < power 2 p * power 2 q133by (a * b <= a * power 2 q by b < power 2 q /\ 0 <= a)134so (a = 0 \/ a * power 2 q < power 2 p * power 2 q) };135assert { - power 2 (p + q) < n * m < power 2 (p + q)136by n * m = a * b \/ n * m = - (a * b) };137assert { from_int (n * m) = from_int n *. from_int m };138assert { x *. y = from_int (n * m) *. pow2r (e + f) }139{qed}140
A nonzero multiple of 2^k is at least 2^k in magnitude
Valid (32ms) (colibri2 7) (cvc5 2) (split_vc) (depth 1)let ghost fix_nz_ge (x: real) (k: int) : unit143requires { fix x k /\ x <> 0.0 }144ensures { x <=. -. pow2r k \/ pow2r k <=. x }145= {proof…}146let n = quot x (pow2r k) in147pow2r_pos k;148assert { n <> 0 };149let p = pow2r k in150if n > 0 then begin151assert { from_int n >=. 1.0 };152assert { x -. p = (from_int n -. 1.0) *. p };153assert { (from_int n -. 1.0) *. p >=. 0.0 }154end else begin155assert { from_int n <=. -. 1.0 };156assert { -. p -. x = (-. from_int n -. 1.0) *. p };157assert { (-. from_int n -. 1.0) *. p >=. 0.0 }158end159{qed}160
An integer of magnitude at most 2^p, 1 <= p, has p bits and is a multiple of 2^0
Valid (64ms) (colibri2)let ghost int_dyadic (n p: int) : unit164requires { 1 <= p /\ - power 2 p <= n <= power 2 p }165ensures { fix (from_int n) 0 /\ flt (from_int n) p }166= {proof…}167assert { pow2r 0 = 1.0 };168dv_intro (from_int n) (pow2r 0) n;169assert { 2 <= power 2 p by power 2 p = 2 * power 2 (p - 1) /\ power 2 (p - 1) >= 1 };170if n = power 2 p then begin171pow2r_int p;172assert { from_int n = from_int 1 *. pow2r p }173end else if n = - power 2 p then begin174pow2r_int p;175assert { from_int n = from_int (-1) *. pow2r p }176end else177assert { from_int n = from_int n *. pow2r 0 }178{qed}179
let function min_o (a b: option int) : option int =183match a, b with None, _ | _, None -> None184| Some x, Some y -> Some (if x <= y then x else y) end185let function max_o (a b: option int) : option int =186match a, b with None, _ | _, None -> None187| Some x, Some y -> Some (if x <= y then y else x) end188
Every domain holds 0
Valid (85ms) (colibri2)let ghost mem_zero (d: t) : unit191ensures { mem 0.0 d }192= {proof…}193match d.lo with Some k -> fix_zero k | None -> () end;194match d.prec with195| Some k -> if 0 <= k then assert { 0.0 = from_int 0 *. pow2r 0 }196| None -> () end197{qed}198
The bound of the exponents of the reals (clamp), and the domain of {0} that every domain lo > hi is: it is the least of them, so that their meets do not move without end
let constant zbound : int = 32768203let constant zero_d : t = { lo = Some zbound; hi = Some (- zbound); prec = Some 0 }204
A domain with hi < lo holds only 0
Valid (22ms) (colibri2)let ghost zero_only (x: real) (d: t) (l h: int) : unit207requires { mem x d /\ d.lo = Some l /\ d.hi = Some h /\ h < l }208ensures { x = 0.0 }209= if pure { x <> 0.0 } then fix_mono x (h + 1) l210Valid (48ms) (colibri2)211let ghost zero_d_mem (x: real) : unit212ensures { mem x zero_d <-> x = 0.0 }213= {proof…}214mem_zero zero_d;215if pure { mem x zero_d } then zero_only x zero_d zbound (- zbound)216{qed}217
The meet as a logic function: the result of inter (for the specifications of the environment: fp_conv.Env.upddr)
function meet_lo (a b: option int) : option int =221match a, b with222| None, l | l, None -> l223| Some x, Some y -> Some (if x <= y then y else x)224end225function meet_hi (a b: option int) : option int =226match a, b with227| None, h | h, None -> h228| Some x, Some y -> Some (if x <= y then x else y)229end230function meet_prec (a b: option int) : option int =231match a, b with232| None, p | p, None -> p233| Some x, Some y ->234Some (if x < 0 then y else if y < 0 then x else if x <= y then x else y)235end236function meet (a b: t) : t =237let rl = meet_lo a.lo b.lo in238let rh = meet_hi a.hi b.hi in239match rl, rh with240| Some l, Some h -> if h < l then zero_d else mk rl rh (meet_prec a.prec b.prec)241| _ -> mk rl rh (meet_prec a.prec b.prec)242end243
The equality of two domains
Valid (29ms) (colibri2)let deq (a b: t) : bool246ensures { result <-> a = b }247= let eqo (x y: option int) : bool ensures { result <-> x = y } =248match x, y with249| None, None -> true250| Some u, Some v -> u = v251| _ -> false252end in253eqo a.lo b.lo && eqo a.hi b.hi && eqo a.prec b.prec254
The meet: the intersection, exactly (fix and flt are monotonic); a domain of {0} is zero_d
Valid (1.2s) (colibri2 16) (cvc5 5) (split_vc 7) (depth 4)let inter (a b: t) : t258ensures { forall x. mem x result <-> mem x a /\ mem x b }259ensures { result = meet a b }260= let rl = match a.lo, b.lo with261| None, l | l, None -> l262| Some x, Some y -> Some (if x <= y then y else x) end in263let rh = match a.hi, b.hi with264| None, h | h, None -> h265| Some x, Some y -> Some (if x <= y then x else y) end in266let rp = match a.prec, b.prec with267| None, p | p, None -> p268| Some x, Some y ->269Some (if x < 0 then y else if y < 0 then x else if x <= y then x else y) end in270{proof…}271match a.lo, b.lo with272| Some u, Some v -> if u <= v then fix_mono_all u v else fix_mono_all v u273| _ -> () end;274match a.hi, b.hi with275| Some u, Some v ->276if u <= v then fix_mono_all (u + 1) (v + 1) else fix_mono_all (v + 1) (u + 1)277| _ -> () end;278match a.prec, b.prec with279| Some u, Some v ->280if 0 <= u && 0 <= v then begin281if u <= v then flt_mono_all u v else flt_mono_all v u end282| _ -> () end;283{qed}284match rl, rh with285| Some l, Some h ->286if h < l then begin287{proof…}288let lemma z (x: real) : unit289ensures { mem x zero_d <-> mem x (mk rl rh rp) }290= zero_d_mem x; mem_zero (mk rl rh rp);291if pure { mem x (mk rl rh rp) } then zero_only x (mk rl rh rp) l h in292{qed}293zero_d294end else mk rl rh rp295| _ -> mk rl rh rp296end297
Valid (47ms) (colibri2)let ghost fix_add_all (k: int) : unit301ensures { forall x y. fix x k -> fix y k -> fix (x +. y) k }302= {proof…}303assert { forall n m. from_int (n + m) = from_int n +. from_int m };304assert { forall x y n m. x = from_int n *. pow2r k -> y = from_int m *. pow2r k ->305x +. y = from_int (n + m) *. pow2r k }306{qed}307Valid (41ms) (colibri2)308let ghost fix_sub_all (k: int) : unit309ensures { forall x y. fix x k -> fix y k -> fix (x -. y) k }310= {proof…}311assert { forall n m. from_int (n - m) = from_int n -. from_int m };312assert { forall x y n m. x = from_int n *. pow2r k -> y = from_int m *. pow2r k ->313x -. y = from_int (n - m) *. pow2r k }314{qed}315
hi (x + y) <= hi x when hi x < lo y and x is nonzero
Valid (1.6s) (colibri2 3) (split_vc) (depth 1)let ghost add_hi_all (h l: int) : unit318requires { h < l }319ensures { forall x y. x <> 0.0 -> not fix x (h + 1) -> fix y l ->320not fix (x +. y) (h + 1) }321= {proof…}322fix_mono_all (h + 1) l; fix_sub_all (h + 1);323assert { forall x y. x +. y -. y = x }324{qed}325
The sum; anz (bnz): the first (second) operand is nonzero
Valid (804ms) (colibri2 7) (cvc5) (split_vc) (depth 1)let add (a b: t) (anz bnz: bool) : t328ensures { forall x y. mem x a -> mem y b -> (anz -> x <> 0.0) ->329(bnz -> y <> 0.0) -> mem (x +. y) result }330= let rl = min_o a.lo b.lo in331{proof…}332match a.lo, b.lo with333| Some u, Some v ->334let k = if u <= v then u else v in335fix_mono_all k u; fix_mono_all k v; fix_add_all k336| _ -> () end;337{qed}338let hi_of (ha: option int) (lb hb: option int) (nz: bool) : option int339ensures { forall x y. mem_hi x ha -> mem_lo y lb -> mem_hi y hb ->340(nz -> x <> 0.0) ->341match result with None -> true | Some k -> mem_hi (x +. y) (Some k) end }342= match ha, lb with343| Some h, Some l ->344if h < l then begin345add_hi_all h l;346if nz then Some h347else match hb with348| Some h' ->349let k = if h <= h' then h' else h in350fix_mono_all (h + 1) (k + 1); fix_mono_all (h' + 1) (k + 1);351assert { forall y. 0.0 +. y = y };352Some k353| None -> None end end354else None355| _ -> None356end in357let rh = match hi_of a.hi b.lo b.hi anz with358| Some k -> Some k359| None -> hi_of b.hi a.lo a.hi bnz end in360mk rl rh None361
Valid (788ms) (colibri2) (cvc5 2) (split_vc) (depth 1)let ghost neg_mem (x: real) (d: t) : unit365ensures { mem (-. x) d <-> mem x d }366= {proof…}367match d.lo with Some k -> fix_neg x k | None -> () end;368match d.hi with Some k -> fix_neg x (k + 1) | None -> () end;369match d.prec with370| Some p ->371assert { forall m e. x = from_int m *. pow2r e -> -. x = from_int (- m) *. pow2r e };372assert { forall m e. -. x = from_int m *. pow2r e -> x = from_int (- m) *. pow2r e }373| None -> () end374{qed}375
The difference, and the backward step of a sum: x = s - y
Valid (68ms) (colibri2)let sub (a b: t) (anz bnz: bool) : t378ensures { forall x y. mem x a -> mem y b -> (anz -> x <> 0.0) ->379(bnz -> y <> 0.0) -> mem (x -. y) result }380= let r = add a b anz bnz in381{proof…}382let lemma nm (y: real) ensures { mem y b -> mem (-. y) b } = neg_mem y b in383assert { forall x y. x -. y = x +. (-. y) };384{qed}385r386
The valuation of a nonzero dyadic x = n 2^l
Valid (376ms) (colibri2)let rec ghost valuation (x: real) (l n: int) : int391requires { x <> 0.0 /\ x = from_int n *. pow2r l }392ensures { l <= result /\ fix x result /\ not fix x (result + 1) }393variant { if n < 0 then - n else n }394= {proof…}395pow2r_succ l; pow2r_pos l;396if mod n 2 = 0 then begin397assert { n = 2 * div n 2 /\ div n 2 <> 0 };398assert { from_int n = 2.0 *. from_int (div n 2) };399assert { x = from_int (div n 2) *. pow2r (l + 1) };400assert { (if div n 2 < 0 then - div n 2 else div n 2) < (if n < 0 then - n else n) };401valuation x (l + 1) (div n 2)402end else begin403dv_intro x (pow2r l) n;404if pure { fix x (l + 1) } then begin405let m = quot x (pow2r (l + 1)) in406assert { from_int n *. pow2r l = from_int (2 * m) *. pow2r l };407assert { n = 2 * m };408absurd409end;410l411end412{qed}413
n and m odd: n m is odd
Valid (140ms) (colibri2 2) (cvc4) (split_vc) (depth 1)let ghost odd_mul (n m: int) : unit416requires { mod n 2 = 1 /\ mod m 2 = 1 }417ensures { mod (n * m) 2 = 1 }418= {proof…}419assert { n = 2 * div n 2 + 1 /\ m = 2 * div m 2 + 1 };420assert { n * m = 2 * (2 * div n 2 * div m 2 + div n 2 + div m 2) + 1 }421{qed}422
The valuation of a product is the sum of the valuations
Valid (61ms) (colibri2)let ghost val_mul (x y: real) (k j: int) : unit425requires { fix x k /\ not fix x (k + 1) /\ fix y j /\ not fix y (j + 1) }426ensures { fix (x *. y) (k + j) /\ not fix (x *. y) (k + j + 1) }427= {proof…}428fix_mul x y k j;429pow2r_succ k; pow2r_succ j; pow2r_pos k; pow2r_pos j;430let n = quot x (pow2r k) in431let m = quot y (pow2r j) in432if mod n 2 = 0 then begin433assert { n = 2 * div n 2 };434assert { x = from_int (div n 2) *. pow2r (k + 1) }; absurd end;435if mod m 2 = 0 then begin436assert { m = 2 * div m 2 };437assert { y = from_int (div m 2) *. pow2r (j + 1) }; absurd end;438odd_mul n m;439pow2r_add k j; pow2r_succ (k + j); pow2r_pos (k + j);440if pure { fix (x *. y) (k + j + 1) } then begin441let p = quot (x *. y) (pow2r (k + j + 1)) in442assert { from_int (n * m) = from_int n *. from_int m };443assert { x *. y = from_int (n * m) *. pow2r (k + j) };444assert { from_int (n * m) *. pow2r (k + j) = from_int (2 * p) *. pow2r (k + j) };445assert { n * m = 2 * p };446absurd447end448{qed}449
A nonzero x with fix x k and not fix x (h + 1): k <= h
Valid (20ms) (colibri2)let ghost fix_le_hi (x: real) (k h: int) : unit452requires { fix x k /\ not fix x (h + 1) }453ensures { k <= h }454= {proof…} if k > h then fix_mono x (h + 1) k {qed}455
The product: lo and prec add; hi adds when both lo are finite (dyadic factors)
A factor ±2^e (or 0) keeps the bits of the other
Valid (56ms) (colibri2 6) (cvc5) (split_vc) (depth 1)let ghost flt_mul_pow2 (x y: real) (q: int) : unit460requires { flt x 1 /\ flt y q /\ 0 <= q }461ensures { flt (x *. y) q }462= {proof…}463let n = any int ensures { exists e. x = from_int result *. pow2r e /\ -2 < result < 2 } in464let e = any int ensures { x = from_int n *. pow2r result } in465let m = any int ensures { exists f. y = from_int result *. pow2r f /\466- power 2 q < result < power 2 q } in467let f = any int ensures { y = from_int m *. pow2r result } in468pow2r_add e f;469assert { x *. y = from_int (n * m) *. pow2r (e + f) };470assert { n * m = 0 \/ n * m = m \/ n * m = - m }471{qed}472Valid (829ms) (colibri2 33) (cvc4) (cvc5 5) (split_vc 9) (depth 5)473let mul (a b: t) : t474ensures { forall x y. mem x a -> mem y b -> mem (x *. y) result }475= let rl = match a.lo, b.lo with476| Some u, Some v -> Some (u + v) | _ -> None end in477let rh = match a.lo, b.lo, a.hi, b.hi with478| Some _, Some _, Some u, Some v -> Some (u + v) | _ -> None end in479let rp = match a.prec, b.prec with480| Some u, Some v ->481if 0 <= u && 0 <= v then482Some (if u <= 1 then v else if v <= 1 then u else u + v)483else None484| _ -> None end in485{proof…}486match a.lo, b.lo with487| Some u, Some v ->488let lemma lo_mul (x y: real) requires { fix x u /\ fix y v }489ensures { fix (x *. y) (u + v) } = fix_mul x y u v in ()490| _ -> () end;491match a.prec, b.prec with492| Some u, Some v -> if 0 <= u && 0 <= v then begin493if u <= 1 then begin494flt_mono_all u 1;495let lemma prec_mul (x y: real) requires { flt x u /\ flt y v }496ensures { flt (x *. y) v } = flt_mul_pow2 x y v in () end497else if v <= 1 then begin498flt_mono_all v 1;499let lemma prec_mul (x y: real) requires { flt x u /\ flt y v }500ensures { flt (x *. y) u } =501flt_mul_pow2 y x u; assert { x *. y = y *. x } in () end502else begin503let lemma prec_mul (x y: real) requires { flt x u /\ flt y v }504ensures { flt (x *. y) (u + v) } = flt_mul x y u v in () end505end506| _ -> () end;507match a.lo, b.lo, a.hi, b.hi with508| Some la, Some lb, Some u, Some v ->509let lemma hi_mul (x y: real) : unit510requires { fix x la /\ fix y lb /\ mem_hi x (Some u) /\ mem_hi y (Some v) }511ensures { mem_hi (x *. y) (Some (u + v)) }512= if pure { x *. y <> 0.0 } then begin513assert { x <> 0.0 /\ y <> 0.0 };514assert { not fix x (u + 1) /\ not fix y (v + 1) };515let kx = valuation x la (quot x (pow2r la)) in516let ky = valuation y lb (quot y (pow2r lb)) in517fix_le_hi x kx u; fix_le_hi y ky v;518val_mul x y kx ky;519if pure { fix (x *. y) (u + v + 1) } then520fix_mono (x *. y) (kx + ky + 1) (u + v + 1)521end in522()523| _ -> () end;524assert { forall x y. mem x a -> mem y b -> mem_lo (x *. y) rl };525assert { forall x y. mem x a -> mem y b -> mem_hi (x *. y) rh };526assert { forall x y. mem x a -> mem y b -> mem_prec (x *. y) rp };527{qed}528mk rl rh rp529
The backward step of a product x y in c, on x in a; bnz: y is nonzero. hi (x) <= hi c - lo b; lo x >= lo c - hi b when lo a and lo b are finite (dyadic factors)
Valid (302ms) (colibri2 12) (cvc5) (split_vc) (depth 1)let mul_back (a c b: t) (bnz: bool) : t534ensures { forall x y. mem x a -> mem y b -> (bnz -> y <> 0.0) ->535mem (x *. y) c -> mem x result }536= let rh = match bnz, c.hi, b.lo with537| True, Some hc, Some lb -> Some (hc - lb) | _ -> None end in538let rl = match bnz, a.lo, b.lo, c.lo, b.hi with539| True, Some _, Some _, Some lc, Some hb -> Some (lc - hb) | _ -> None end in540{proof…}541match bnz, c.hi, b.lo with542| True, Some hc, Some lb ->543let lemma hi_back (x y: real)544requires { fix y lb /\ y <> 0.0 /\ mem_hi (x *. y) (Some hc) }545ensures { mem_hi x (Some (hc - lb)) }546= if pure { x <> 0.0 /\ fix x (hc - lb + 1) } then begin547fix_mul x y (hc - lb + 1) lb;548assert { x *. y <> 0.0 }549end in ()550| _ -> () end;551match bnz, a.lo, b.lo, c.lo, b.hi with552| True, Some la, Some lb, Some lc, Some hb ->553let lemma lo_back (x y: real)554requires { fix x la /\ fix y lb /\ y <> 0.0 /\ mem_hi y (Some hb) /\555fix (x *. y) lc }556ensures { fix x (lc - hb) }557= if pure { x = 0.0 } then fix_zero (lc - hb)558else begin559let kx = valuation x la (quot x (pow2r la)) in560let ky = valuation y lb (quot y (pow2r lb)) in561fix_le_hi y ky hb;562val_mul x y kx ky;563fix_le_hi (x *. y) lc (kx + ky);564fix_mono x (lc - hb) kx565end in ()566| _ -> () end;567{qed}568mk rl rh None569
The domain of a real can go up without end along a cycle of operations (x = 2 x): beyond b the information is weakened, so that the domains of the reals form a finite lattice
Valid (338ms) (cvc5)let clamp (b: int) (a: t) : t576ensures { forall x. mem x a -> mem x result }577= let l = match a.lo with578| Some l -> if l < - b then None else if l > b then Some b else Some l579| None -> None end in580let h = match a.hi with581| Some h -> if h > b then None else if h < - b then Some (- b) else Some h582| None -> None end in583let p = match a.prec with584| Some p -> if p > b then None else Some p585| None -> None end in586{proof…}587match a.lo with588| Some k -> if k > b then begin589let lemma lo (x: real) requires { fix x k } ensures { fix x b } = fix_mono x b k in () end590| None -> () end;591match a.hi with592| Some k -> if k < - b then begin593let lemma hi (x: real) requires { not fix x (k + 1) } ensures { not fix x (- b + 1) }594= if pure { fix x (- b + 1) } then fix_mono x (k + 1) (- b + 1) in () end595| None -> () end;596{qed}597mk l h p598
±2^e is a multiple of 2^k exactly when k <= e
Valid (694ms) (colibri2)let ghost fix_pow2 (s: real) (e k: int) : unit603requires { s = 1.0 \/ s = -. 1.0 }604ensures { fix (s *. pow2r e) k <-> k <= e }605= {proof…}606if k <= e then begin607dv_intro (s *. pow2r e) (pow2r e) (if pure { s = 1.0 } then 1 else -1);608fix_mono (s *. pow2r e) k e609end else if pure { fix (s *. pow2r e) k } then begin610fix_mono (s *. pow2r e) (e + 1) k;611absurd612end613{qed}614615let function neg_o (a: option int) : option int =616match a with None -> None | Some k -> Some (- k) end617
The inverse of a power of 2 up to the sign (prec <= 1): 1/(±2^e) = ±2^(-e); else no information
Valid (374ms) (colibri2 9) (cvc5) (split_vc) (depth 1)let inv (a: t) : t621ensures { forall x. mem x a -> x <> 0.0 -> mem (1.0 /. x) result }622= match a.prec with623| Some p ->624if 0 <= p && p <= 1 then begin625{proof…}626let lemma pt (x: real) : unit627requires { mem x a /\ x <> 0.0 }628ensures { mem (1.0 /. x) (mk (neg_o a.hi) (neg_o a.lo) (Some 1)) }629= let n = any int ensures { exists e. x = from_int result *. pow2r e /\630- power 2 p < result < power 2 p } in631let e = any int ensures { x = from_int n *. pow2r result } in632assert { power 2 p <= 2 by p = 0 \/ p = 1 };633let s = from_int n in634assert { 1.0 /. x = from_int n *. pow2r (- e) };635match a.lo with Some l -> fix_pow2 s e l; fix_pow2 s (- e) (- l + 1)636| None -> () end;637match a.hi with Some h -> fix_pow2 s e (h + 1); fix_pow2 s (- e) (- h)638| None -> () end in639{qed}640mk (neg_o a.hi) (neg_o a.lo) (Some 1)641end else top642| None -> top643end644
A number of bits of n >= 0: n < 2^result
Valid (40ms) (colibri2)let rec nbits (n: int) : int649requires { 0 <= n }650ensures { 0 <= result /\ n < power 2 result }651variant { n }652= if n = 0 then 0653else begin654let k = nbits (div n 2) in655k + 1656end657
The valuation and the odd significand of a nonzero x = n 2^l
Valid (1.2s) (colibri2)let rec odd_part (ghost x: real) (l n: int) : (int, int)660requires { x <> 0.0 /\ x = from_int n *. pow2r l }661ensures { let (k, m) = result in x = from_int m *. pow2r k /\662fix x k /\ not fix x (k + 1) }663variant { if n < 0 then - n else n }664= if mod n 2 = 0 then begin665{proof…} pow2r_succ l; {qed}666odd_part x (l + 1) (div n 2)667end else begin668{proof…}669if pure { fix x (l + 1) } then begin670let m = quot x (pow2r (l + 1)) in671assert { from_int n *. pow2r l = from_int (2 * m) *. pow2r l };672assert { n = 2 * m };673absurd674end;675{qed}676(l, n)677end678
The domain of n 2^e: exact for a nonzero number (lo = hi, the bits of the odd significand); for 0, lo = z and hi < lo (any z: 0 is a multiple of every power of 2)
Valid (349ms) (colibri2)let exact (n e z: int) : t683ensures { mem (from_int n *. pow2r e) result }684= if n = 0 then begin685{proof…}686fix_zero z;687{qed}688mk (Some z) (Some (z - 1)) (Some 0)689end else begin690let ghost x = pure { from_int n *. pow2r e } in691let (k, m) = odd_part x e n in692let a = if m < 0 then - m else m in693let p = nbits a in694mk (Some k) (Some k) (Some p)695end696
A valuation bound for the nonzero reals of magnitude at most |n| 2^e: they are below 2^(result+1)
Valid (34ms) (colibri2 6) (split_vc) (depth 1)let log2_up (n e: int) : int700ensures { forall x. x <> 0.0 ->701-. (from_int (if n < 0 then - n else n) *. pow2r e) <=. x <=.702from_int (if n < 0 then - n else n) *. pow2r e ->703mem_hi x (Some result) }704= let a = if n < 0 then - n else n in705let b = nbits a in706{proof…}707pow2r_add e b;708assert { from_int a *. pow2r e <. pow2r (e + b) };709let lemma hi (x: real)710requires { x <> 0.0 /\ -. (from_int a *. pow2r e) <=. x <=. from_int a *. pow2r e }711ensures { mem_hi x (Some (e + b - 1)) }712= if pure { fix x (e + b) } then begin713fix_nz_ge x (e + b);714absurd715end in716{qed}717e + b - 1718
A class rem + div ℤ of the congruence domain, rem = rn 2^re and div = dn 2^de: its members are multiples of the powers of 2 dividing rem and div (the integers, div = 1 and rem = 0, have lo = 0); exact when div = 0
Valid (1.0s) (colibri2)let congr (dn de rn re: int) : t724ensures { forall x k. x = from_int rn *. pow2r re +. from_int k *. (from_int dn *. pow2r de) ->725mem x result }726= if dn = 0 then exact rn re 0727else728let dd = exact dn de zbound in729let dr = exact rn re zbound in730match dd.lo, dr.lo with731| Some kd, Some kr ->732let m = if kd < kr then kd else kr in733{proof…}734let lemma c (x: real) (k: int)735requires { x = from_int rn *. pow2r re +. from_int k *. (from_int dn *. pow2r de) }736ensures { fix x m }737= let y = pure { from_int dn *. pow2r de } in738dv_intro (from_int k) (pow2r 0) k;739fix_mul (from_int k) y 0 kd;740fix_mono (from_int k *. y) m kd;741fix_mono (from_int rn *. pow2r re) m kr;742fix_add (from_int rn *. pow2r re) (from_int k *. y) m in743{qed}744mk (Some m) None None745| _ -> top746end747
x <> 0 in d: lo <= hi, 2^lo <= |x| and |x| < 2^(hi+prec) (Gappa's fix_of_flt_bnd and flt_of_fix_bnd read backward)
Valid (41ms) (colibri2 15) (cvc5) (split_vc 2) (depth 2)let ghost mag (x: real) (d: t) : unit753requires { mem x d /\ x <> 0.0 }754ensures { match d.lo, d.hi with Some l, Some h -> l <= h | _ -> true end }755ensures { match d.lo with756| Some l -> x <=. -. pow2r l \/ pow2r l <=. x | None -> true end }757ensures { match d.hi, d.prec with758| Some h, Some p -> 0 <= p -> -. pow2r (h + p) <. x <. pow2r (h + p)759| _ -> true end }760= {proof…}761match d.lo with762| Some l ->763fix_nz_ge x l;764match d.hi with765| Some h -> if l > h then begin fix_mono x (h + 1) l; absurd end766| None -> ()767end768| None -> ()769end;770match d.hi, d.prec with771| Some h, Some p ->772if 0 <= p then begin773let m = any int ensures { exists e. x = from_int result *. pow2r e /\774- power 2 p < result < power 2 p } in775let e = any int ensures { x = from_int m *. pow2r result } in776if e > h then begin777dv_intro x (pow2r e) m;778fix_mono x (h + 1) e;779absurd780end;781pow2r_add p e; pow2r_le (p + e) (h + p);782let q = pow2r p in783let u = pow2r e in784assert { q *. u -. x = (q -. from_int m) *. u };785assert { (q -. from_int m) *. u >. 0.0 };786assert { -. pow2r p *. pow2r e <. x <. pow2r p *. pow2r e }787end788| _ -> ()789end790{qed}791end792