library colibrilib.congruence — module CongruenceThe congruence domain of colibri2 (LRA): the set { rem + div * k | k in Z } with div a rational and rem a real that is rational or algebraic.
gamma c is the set of the reals of the class c. The specification of a function relates the gamma of its result to the gamma of its arguments:
integers, singleton, is_singleton, norm, inter, reduce_integers, add_cst, neg_forward, and the tests is_integer, is_included, mem, a_divisible.union._forward and _backward functions.The result Top of a function of type backward means that nothing is known. Each such function says exactly when it returns Top.
Every function of this module accepts any arguments, except the ones whose name ends with _nz, which have a precondition: the module Export has their total version, which is the one that is extracted.
The trusted base is the numbers: StdQ and StdA, and the integers of Zarith (zarith.Z.gcdext, zarith.Zbit.trailing_zeros, tested by QCheck in colibri2/theories/LRA/congruence/test). The helper facts on divisibility are in colibrilib/dv.mlw and those on the low bits in colibrilib/lowbits.mlw.
module Congruence30use int.Int31use real.RealInfix32use real.FromInt33use real.Abs34use real.Truncate35use option.Option36use colibrilib.zarith.Zbit37use colibrilib.zbit.ZbitInt38use set.Set as S39use colibrilib.dv.Dv40use colibrilib.dv.RealSets41use colibrilib.dv.RealFacts42use colibrilib.lowbits.LowBits43use colibrilib.zarith.Z as Z44use number.Gcd as G45use number.Divisibility as D46
The gcd of Zarith as qa stated it for Bezout
Valid (63ms) (colibri2)let ghost gcd_facts (a b:int) : unit49ensures { 0 <= G.gcd a b }50ensures { exists a':int. a = a' * G.gcd a b }51ensures { exists b':int. b = b' * G.gcd a b }52= assert { D.divides (G.gcd a b) a /\ D.divides (G.gcd a b) b }53use colibrilib.stdq.StdQ as Q54use colibrilib.q.Real as Real55use colibrilib.qa.ModE56use colibrilib.qa.Rat57use colibrilib.stda.StdA as A58use colibrilib.known_bits.KnownBits as KB59
The class { rem + div * k | k in Z }. There is no invariant: div may be zero (the class is the single real rem) or negative; norm gives the normal form.
type t = { div : Q.t; rem : A.t }64
The result of a propagator: R c is a class, Top says that nothing is known (all the reals).
type backward 'a = Top | R 'a68
x is in the class of c: x - rem is an integer multiple of div
predicate member (x:real) (c:t) = dv (x -. A.real c.rem) (Q.real c.div)71
The concretization of c: the set of the reals of its class
function gamma (c:t) : S.set real = fun x -> member x c74
The representative is in its class
Valid (26ms) (colibri2)let ghost rem_member (c:t) : unit77ensures { member (A.real c.rem) c }78= dv_zero (Q.real c.div);79assert { A.real c.rem -. A.real c.rem = 0.0 }80
rem + div is in the class
Valid (24ms) (colibri2)let ghost rem_div_member (c:t) : unit83ensures { member (A.real c.rem +. Q.real c.div) c }84= dv_self (Q.real c.div);85assert { A.real c.rem +. Q.real c.div -. A.real c.rem = Q.real c.div }86
Membership through an inclusion of concretizations
Valid (109ms) (cvc5)let ghost sub_member (x y:t) (z:real) : unit89requires { S.subset (gamma x) (gamma y) }90requires { member z x }91ensures { member z y }92= ()93
The set of the integers
function ints : S.set real = fun x -> Real.is_integer x96
All the elements of c are integers
predicate integral (c:t) = S.subset (gamma c) ints99
An integer is in ints
Valid (33ms) (colibri2)let ghost ints_intro (z:int) : unit102ensures { S.mem (from_int z) ints }103= ()104
The set of the integers
Valid (134ms) (colibri2)let integers () : t107ensures { gamma result = ints }108ensures { Q.real result.div = 1.0 /\ A.real result.rem = 0.0 }109= let r = { div = Q.of_int 1; rem = A.of_int 0 } in110let lemma pw (x:real) : unit111ensures { member x r <-> Real.is_integer x }112= if pure { member x r } then begin113let k = quot pure { x -. A.real r.rem } pure { Q.real r.div } in114assert { Real.is_integer x by x = from_int k }115end;116if pure { Real.is_integer x } then begin117let z = Real.int_of x in118dv_intro (x -. A.real r.rem) (Q.real r.div) z119end in120set_ext (gamma r) ints;121r122
The same set with a normalized representation: div is non negative, rem is in [0, div), and the integers are {div = 1; rem = 0}
Valid (77ms) (colibri2 22) (split_vc 2) (depth 2)let norm (n:t) : t126ensures { gamma result = gamma n }127
the representative moves by a multiple of div
ensures { exists k:int. A.real result.rem = A.real n.rem +. from_int k *. Q.real n.div }129= if Q.is_zero n.div then begin130assert { A.real n.rem = A.real n.rem +. from_int 0 *. Q.real n.div };131n132end133else if Q.equal n.div (Q.of_int 1) && A.is_integer n.rem then begin134let r = integers () in135let ghost m = A.to_z n.rem in136assert { A.real r.rem = A.real n.rem +. from_int (- m) *. Q.real n.div };137let lemma same (x:real) : unit138ensures { member x n <-> S.mem x (gamma r) }139= if pure { member x n } then begin140let k = quot pure { x -. A.real n.rem } pure { Q.real n.div } in141assert { Real.is_integer x by x = from_int (k + m) }142end;143if pure { Real.is_integer x } then begin144let z = Real.int_of x in145dv_intro (x -. A.real n.rem) (Q.real n.div) (z - m)146end in147set_ext (gamma n) (gamma r);148r149end else begin150let div = Q.abs n.div in151let bd = A.of_q div in152let rem = A.mod_e n.rem bd in153mod_e_facts pure { A.real n.rem } pure { A.real bd };154let ghost k = pure { Real.div_e (A.real n.rem) (A.real bd) } in155let lemma same (x:real) : unit156ensures { member x n <-> dv (x -. A.real rem) (Q.real div) }157= dv_mul_int k pure { Q.real div };158dv_shift pure { x -. A.real rem } pure { from_int k *. Q.real div } pure { Q.real div };159dv_abs pure { x -. A.real n.rem } pure { Q.real n.div };160assert { A.real rem = A.real n.rem -. from_int k *. Q.real div };161assert { x -. A.real rem -. from_int k *. Q.real div = x -. A.real n.rem } in162assert { A.real rem = A.real n.rem -. from_int k *. Q.real div };163abs_shift pure { A.real n.rem } pure { A.real rem } pure { Q.real n.div } k;164let res = { div = div; rem = rem } in165assert { A.real res.rem = A.real rem };166set_ext (gamma res) (gamma n);167res168end169Valid (43ms) (colibri2)170let a_divisible (a:A.t) (q:Q.t) : bool171ensures { result <-> dv (A.real a) (Q.real q) }172= match A.view a with173| A.Irr ->174if pure { dv (A.real a) (Q.real q) } then begin175let k = any int ensures { A.real a = from_int result *. Q.real q } in176let r = Q.mul (Q.of_bigint k) q in177assert { Q.real r = A.real a }178end;179false180| A.Rat a -> let r, ghost _ = Q.divisible a q in r181end182
The class of the single real v
Valid (57ms) (colibri2)let singleton (v:A.t) : t185ensures { gamma result = S.singleton (A.real v) }186ensures { Q.real result.div = 0.0 /\ A.real result.rem = A.real v }187= let r = { div = Q.of_int 0; rem = v } in188let lemma pw (x:real) : unit189ensures { member x r <-> x = A.real v }190= dv_zero_iff (x -. A.real v) in191set_ext (gamma r) (S.singleton (A.real v));192r193
Some r when the class is the single real r
Valid (54ms) (colibri2)let is_singleton (c:t) : option A.t196ensures { match result with197| Some r -> gamma c = S.singleton (A.real r)198| None -> Q.real c.div <> 0.0199end }200= if Q.is_zero c.div then begin201let lemma pw (x:real) : unit202ensures { member x c <-> x = A.real c.rem }203= dv_zero_iff (x -. A.real c.rem) in204set_ext (gamma c) (S.singleton (A.real c.rem));205Some c.rem206end else None207
All the elements of c are integers
Valid (415ms) (colibri2 13) (cvc5 2) (split_vc 4) (depth 2)let is_integer (c:t) : bool210ensures { result <-> integral c }211= let ia = A.is_integer c.rem in212let iq = Q.is_integer c.div in213let lemma forward (x:real) : unit214requires { ia /\ iq }215requires { member x c }216ensures { Real.is_integer x }217= let m = Q.to_z c.div in218let n = A.to_z c.rem in219let k = quot pure { x -. A.real c.rem } pure { Q.real c.div } in220assert { Real.is_integer x by x = from_int (n + k * m) } in221if not ia then begin222(* the representative itself is not an integer *)223assert { member (A.real c.rem) c }224end else if not iq then begin225let n = A.to_z c.rem in226assert { member (A.real c.rem +. Q.real c.div) c };227if pure { Real.is_integer (A.real c.rem +. Q.real c.div) } then begin228let z = Real.int_of (A.real c.rem +. Q.real c.div) in229assert { Real.is_integer (Q.real c.div) by Q.real c.div = from_int (z - n) }230end231end;232ia && iq233
The intersection, exactly (None when it is empty; Bezout and the Chinese remainder theorem)
Valid (769ms) (colibri2 62) (cvc5 2) (split_vc) (depth 1)let inter (x y:t) : option t237ensures { match result with238| Some c -> gamma c = S.inter (gamma x) (gamma y)239| None -> S.is_empty (S.inter (gamma x) (gamma y))240end }241= let b = A.sub y.rem x.rem in242if Q.equal x.div y.div then begin243let r = a_divisible b x.div in244let lemma same (z:real) : unit245requires { r }246ensures { member z x <-> member z y }247= dv_shift (z -. A.real x.rem) (A.real y.rem -. A.real x.rem) (Q.real x.div);248assert { z -. A.real y.rem = (z -. A.real x.rem) -. (A.real y.rem -. A.real x.rem) };249dv_shift (z -. A.real y.rem) (A.real y.rem -. A.real x.rem) (Q.real x.div);250assert { z -. A.real x.rem = (z -. A.real y.rem) +. (A.real y.rem -. A.real x.rem) } in251let lemma empty (z:real) : unit252requires { not r }253requires { member z x }254requires { member z y }255ensures { false }256= dv_sub (z -. A.real x.rem) (z -. A.real y.rem) (Q.real x.div);257assert { A.real y.rem -. A.real x.rem = (z -. A.real x.rem) -. (z -. A.real y.rem) } in258if r then begin259set_ext (gamma x) (S.inter (gamma x) (gamma y));260Some x261end else None262end else begin263let g, ux, ghost uy = Q.gcdext x.div y.div in264(* the divisors are different, so not both zero *)265assert { Q.real g <> 0.0 };266let lemma empty_irr (z:real) : unit267requires { member z x }268requires { member z y }269ensures { dv (A.real b) (Q.real g) }270= dv_trans (z -. A.real x.rem) (Q.real x.div) (Q.real g);271dv_trans (z -. A.real y.rem) (Q.real y.div) (Q.real g);272dv_sub (z -. A.real x.rem) (z -. A.real y.rem) (Q.real g);273assert { A.real b = (z -. A.real x.rem) -. (z -. A.real y.rem) -. 0.0 } in274match A.view b with275| A.Irr ->276let lemma none (z:real) : unit277requires { member z x }278requires { member z y }279ensures { false }280= empty_irr z;281let k = any int ensures { z -. A.real x.rem = from_int result *. Q.real x.div } in282let l = any int ensures { z -. A.real y.rem = from_int result *. Q.real y.div } in283let q = Q.sub (Q.mul (Q.of_bigint k) x.div) (Q.mul (Q.of_bigint l) y.div) in284assert { Q.real q = A.real b } in285None286| A.Rat bq ->287let r, ghost _ = Q.divisible bq g in288if r then begin289let beta = Q.divexact bq g in290let p = Q.lcm x.div y.div in291let e = Q.mul x.div (Q.of_bigint (beta * ux)) in292let r1 = A.add x.rem (A.of_q e) in293let n0 = { div = p; rem = r1 } in294let c = norm n0 in295assert { A.real r1 = A.real x.rem +. Q.real e };296(* the representative `rx + e` is in both sets *)297let lemma offsets () : unit298ensures { dv (A.real x.rem +. Q.real e -. A.real x.rem) (Q.real x.div) }299ensures { dv (A.real x.rem +. Q.real e -. A.real y.rem) (Q.real y.div) }300= assert { A.real x.rem +. Q.real e -. A.real x.rem = from_int (beta * ux) *. Q.real x.div };301assert { A.real y.rem -. A.real x.rem = from_int beta *. Q.real g };302assert { Q.real g = from_int ux *. Q.real x.div +. from_int uy *. Q.real y.div };303let ghost fb = from_int beta in304let ghost fu = from_int ux in305let ghost fv = from_int uy in306assert { from_int (beta * ux) = fb *. fu };307assert { from_int (- (beta * uy)) = -. (fb *. fv) };308assert { Q.real e = Q.real x.div *. (fb *. fu) };309assert { A.real y.rem -. A.real x.rem = fb *. (fu *. Q.real x.div +. fv *. Q.real y.div) };310assert { A.real x.rem +. Q.real e -. A.real y.rem = from_int (- (beta * uy)) *. Q.real y.div };311dv_mul_int (beta * ux) (Q.real x.div);312dv_mul_int (- (beta * uy)) (Q.real y.div) in313let lemma fwd (z:real) : unit314requires { dv (z -. (A.real x.rem +. Q.real e)) (Q.real p) }315ensures { member z x /\ member z y }316= offsets ();317dv_trans (z -. (A.real x.rem +. Q.real e)) (Q.real p) (Q.real x.div);318dv_trans (z -. (A.real x.rem +. Q.real e)) (Q.real p) (Q.real y.div);319dv_add (z -. (A.real x.rem +. Q.real e)) (A.real x.rem +. Q.real e -. A.real x.rem) (Q.real x.div);320dv_add (z -. (A.real x.rem +. Q.real e)) (A.real x.rem +. Q.real e -. A.real y.rem) (Q.real y.div) in321let lemma bwd (z:real) : unit322requires { member z x /\ member z y }323ensures { dv (z -. (A.real x.rem +. Q.real e)) (Q.real p) }324= offsets ();325dv_sub (z -. A.real x.rem) (A.real x.rem +. Q.real e -. A.real x.rem) (Q.real x.div);326dv_sub (z -. A.real y.rem) (A.real x.rem +. Q.real e -. A.real y.rem) (Q.real y.div);327assert { z -. A.real x.rem -. (A.real x.rem +. Q.real e -. A.real x.rem)328= z -. (A.real x.rem +. Q.real e) };329assert { z -. A.real y.rem -. (A.real x.rem +. Q.real e -. A.real y.rem)330= z -. (A.real x.rem +. Q.real e) } in331let lemma both (z:real) : unit332ensures { member z c <-> (member z x /\ member z y) }333= assert { member z c <-> member z n0 };334assert { member z n0 <-> dv (z -. (A.real x.rem +. Q.real e)) (Q.real p) };335if pure { member z c } then fwd z;336if pure { member z x /\ member z y } then bwd z in337set_ext (gamma c) (S.inter (gamma x) (gamma y));338Some c339end else begin340let lemma none (z:real) : unit341requires { member z x }342requires { member z y }343ensures { false }344= empty_irr z in345None346end347end348end349
The smallest element that contains x and y; Top when there is no such element (the difference of the representatives is not rational)
Valid (988ms) (colibri2 42) (cvc5) (split_vc) (depth 1)let union (x y:t) : backward t353ensures { match result with354| R c -> S.subset (gamma x) (gamma c) /\ S.subset (gamma y) (gamma c)355/\ (forall c'. S.subset (gamma x) (gamma c') -> S.subset (gamma y) (gamma c')356-> S.subset (gamma c) (gamma c'))357/\ Q.is_rat (A.real x.rem -. A.real y.rem)358| Top -> (forall c'. not (S.subset (gamma x) (gamma c') /\ S.subset (gamma y) (gamma c')))359/\ not (Q.is_rat (A.real x.rem -. A.real y.rem))360end }361= let d = A.sub x.rem y.rem in362match A.view d with363| A.Irr ->364let lemma none (c':t) : unit365requires { S.subset (gamma x) (gamma c') }366requires { S.subset (gamma y) (gamma c') }367ensures { false }368= rem_member x;369rem_member y;370sub_member x c' (A.real x.rem);371sub_member y c' (A.real y.rem);372dv_sub (A.real x.rem -. A.real c'.rem) (A.real y.rem -. A.real c'.rem) (Q.real c'.div);373let k = any int ensures { A.real d = from_int result *. Q.real c'.div } in374let q = Q.mul (Q.of_bigint k) c'.div in375assert { Q.real q = A.real d } in376Top377| A.Rat q ->378let g1 = Q.gcd x.div y.div in379let g = Q.gcd g1 q in380let r = norm { rem = x.rem; div = g } in381let lemma sound_x (z:real) : unit382requires { member z x }383ensures { member z r }384= dv_trans (z -. A.real x.rem) (Q.real x.div) (Q.real g1);385dv_trans (z -. A.real x.rem) (Q.real g1) (Q.real g) in386let lemma sound_y (z:real) : unit387requires { member z y }388ensures { member z r }389= dv_trans (z -. A.real y.rem) (Q.real y.div) (Q.real g1);390dv_trans (z -. A.real y.rem) (Q.real g1) (Q.real g);391dv_neg (Q.real q) (Q.real g);392dv_add (z -. A.real y.rem) (-. Q.real q) (Q.real g);393assert { z -. A.real x.rem = (z -. A.real y.rem) +. (-. Q.real q) } in394let lemma least (c':t) : unit395requires { S.subset (gamma x) (gamma c') }396requires { S.subset (gamma y) (gamma c') }397ensures { S.subset (gamma r) (gamma c') }398= rem_member x;399rem_member y;400rem_div_member x;401rem_div_member y;402sub_member x c' (A.real x.rem);403sub_member y c' (A.real y.rem);404sub_member x c' (A.real x.rem +. Q.real x.div);405sub_member y c' (A.real y.rem +. Q.real y.div);406dv_shift (A.real x.rem +. Q.real x.div -. A.real c'.rem) (A.real x.rem -. A.real c'.rem) (Q.real c'.div);407dv_shift (A.real y.rem +. Q.real y.div -. A.real c'.rem) (A.real y.rem -. A.real c'.rem) (Q.real c'.div);408dv_sub (A.real x.rem -. A.real c'.rem) (A.real y.rem -. A.real c'.rem) (Q.real c'.div);409let lemma inner (z:real) : unit410requires { member z r }411ensures { member z c' }412= dv_trans (z -. A.real x.rem) (Q.real g) (Q.real c'.div);413dv_add (z -. A.real x.rem) (A.real x.rem -. A.real c'.rem) (Q.real c'.div);414assert { z -. A.real c'.rem = (z -. A.real x.rem) +. (A.real x.rem -. A.real c'.rem) } in415() in416R r417end418
x is a subset of y
Valid (501ms) (cvc4)let is_included (x y:t) : bool421ensures { result <-> S.subset (gamma x) (gamma y) }422= let r1, ghost _ = Q.divisible x.div y.div in423let r2 = a_divisible ((A.sub x.rem y.rem)) y.div in424let lemma back (z:real) : unit425requires { r1 /\ r2 }426requires { member z x }427ensures { member z y }428= dv_trans (z -. A.real x.rem) (Q.real x.div) (Q.real y.div);429dv_add (z -. A.real x.rem) (A.real x.rem -. A.real y.rem) (Q.real y.div);430assert { z -. A.real y.rem = (z -. A.real x.rem) +. (A.real x.rem -. A.real y.rem) } in431if not (r1 && r2) then begin432rem_member x;433rem_div_member x;434if pure { S.subset (gamma x) (gamma y) } then begin435sub_member x y (A.real x.rem);436sub_member x y (A.real x.rem +. Q.real x.div);437dv_shift (A.real x.rem +. Q.real x.div -. A.real y.rem) (A.real x.rem -. A.real y.rem) (Q.real y.div)438end439end;440r1 && r2441
x belongs to da
Valid (31ms) (colibri2)let mem (x:A.t) (da:t) : bool444ensures { result <-> S.mem (A.real x) (gamma da) }445= a_divisible ((A.sub x da.rem)) da.div446
da translated by q, exactly
Valid (738ms) (colibri2)let add_cst (q:A.t) (da:t) : t449ensures { gamma result = image (fun y -> y +. A.real q) (gamma da) }450= let n = { div = da.div; rem = A.add q da.rem } in451let r = norm n in452image_bij pure { fun y -> y +. A.real q } pure { fun x -> x -. A.real q }453pure { gamma da } pure { gamma n };454r455
The sums of an element of da and an element of db
Valid (752ms) (colibri2)let add_forward (da db:t) : t458ensures { S.subset (map2 (fun x y -> x +. y) (gamma da) (gamma db)) (gamma result) }459= let g = Q.gcd da.div db.div in460let r = norm { div = g; rem = A.add da.rem db.rem } in461let lemma sound (x y:real) : unit462requires { member x da }463requires { member y db }464ensures { dv (x +. y -. (A.real da.rem +. A.real db.rem)) (Q.real g) }465= dv_trans (x -. A.real da.rem) (Q.real da.div) (Q.real g);466dv_trans (y -. A.real db.rem) (Q.real db.div) (Q.real g);467dv_add (x -. A.real da.rem) (y -. A.real db.rem) (Q.real g) in468map2_sound pure { fun x y -> x +. y } pure { gamma da } pure { gamma db } pure { gamma r };469r470
The differences
Valid (651ms) (colibri2)let sub_forward (da db:t) : t473ensures { S.subset (map2 (fun x y -> x -. y) (gamma da) (gamma db)) (gamma result) }474= let g = Q.gcd da.div db.div in475let r = norm { div = g; rem = A.sub da.rem db.rem } in476let lemma sound (x y:real) : unit477requires { member x da }478requires { member y db }479ensures { dv (x -. y -. (A.real da.rem -. A.real db.rem)) (Q.real g) }480= dv_trans (x -. A.real da.rem) (Q.real da.div) (Q.real g);481dv_trans (y -. A.real db.rem) (Q.real db.div) (Q.real g);482dv_sub (x -. A.real da.rem) (y -. A.real db.rem) (Q.real g) in483map2_sound pure { fun x y -> x -. y } pure { gamma da } pure { gamma db } pure { gamma r };484r485
The opposites, exactly
Valid (801ms) (colibri2)let neg_forward (da:t) : t488ensures { gamma result = image (fun x -> -. x) (gamma da) }489ensures { exists k:int. A.real result.rem = -. A.real da.rem +. from_int k *. Q.real da.div }490= let n = { div = da.div; rem = A.neg da.rem } in491let r = norm n in492let lemma same (x:real) : unit493ensures { member x n <-> member (-. x) da }494= if pure { member x n } then dv_neg (x -. (-. A.real da.rem)) (Q.real da.div);495if pure { member (-. x) da } then dv_neg ((-. x) -. A.real da.rem) (Q.real da.div) in496image_bij pure { fun x -> -. x } pure { fun x -> -. x } pure { gamma da } pure { gamma n };497r498
The products by the constant q
Valid (52ms) (colibri2 5) (split_vc) (depth 1)let mul_cst (q:Q.t) (da:t) : t501ensures { S.subset (image (fun x -> x *. Q.real q) (gamma da)) (gamma result) }502= let div = Q.mul da.div q in503let r = norm { div = div; rem = A.mul da.rem (A.of_q q) } in504let lemma sound (x:real) : unit505requires { member x da }506ensures { dv (x *. Q.real q -. A.real da.rem *. Q.real q) (Q.real div) }507= let k = quot pure { x -. A.real da.rem } pure { Q.real da.div } in508assert { x *. Q.real q -. A.real da.rem *. Q.real q = from_int k *. Q.real div } in509image_sound pure { fun x -> x *. Q.real q } pure { gamma da } pure { gamma r };510r511
The products. Top exactly when a representative is not rational.
Valid (1.6s) (colibri2 21) (cvc5) (split_vc) (depth 1)let mul_forward (da db:t) : backward t514ensures { match result with515| R c -> A.rational da.rem /\ A.rational db.rem516/\ S.subset (map2 (fun x y -> x *. y) (gamma da) (gamma db)) (gamma c)517| Top -> not (A.rational da.rem /\ A.rational db.rem)518end }519= match A.view db.rem, A.view da.rem with520| A.Rat dbrem, A.Rat darem ->521let g1 = Q.mul da.div db.div in522let a1 = Q.mul da.div dbrem in523let a2 = Q.mul db.div darem in524let g2 = Q.gcd a1 g1 in525let g = Q.gcd a2 g2 in526let r = norm { div = g; rem = A.of_q ((Q.mul darem dbrem)) } in527let lemma sound (x y:real) : unit528requires { member x da }529requires { member y db }530ensures { member (x *. y) r }531= let i = any int ensures { x -. A.real da.rem = from_int result *. Q.real da.div } in532let j = any int ensures { y -. A.real db.rem = from_int result *. Q.real db.div } in533dv_trans (Q.real a1) (Q.real g2) (Q.real g);534dv_trans (Q.real g1) (Q.real g2) (Q.real g);535dv_mul (Q.real a1) (Q.real g) i;536dv_mul (Q.real a2) (Q.real g) j;537dv_mul (Q.real g1) (Q.real g) (i * j);538dv_add (from_int i *. Q.real a1) (from_int j *. Q.real a2) (Q.real g);539dv_add (from_int i *. Q.real a1 +. from_int j *. Q.real a2) (from_int (i * j) *. Q.real g1) (Q.real g);540let ghost ra = A.real da.rem in541let ghost rb = A.real db.rem in542let ghost dad = Q.real da.div in543let ghost dbd = Q.real db.div in544let ghost fi = from_int i in545let ghost fj = from_int j in546assert { from_int (i * j) = fi *. fj };547assert { Q.real a1 = dad *. rb /\ Q.real a2 = dbd *. ra /\ Q.real g1 = dad *. dbd };548assert { x = ra +. fi *. dad /\ y = rb +. fj *. dbd };549assert { x *. y = (ra +. fi *. dad) *. (rb +. fj *. dbd) };550assert { (ra +. fi *. dad) *. (rb +. fj *. dbd) -. ra *. rb551= fi *. (dad *. rb) +. fj *. (dbd *. ra) +. (fi *. fj) *. (dad *. dbd) };552assert { x *. y -. ra *. rb553= from_int i *. Q.real a1 +. from_int j *. Q.real a2 +. from_int (i * j) *. Q.real g1 } in554map2_sound pure { fun x y -> x *. y } pure { gamma da } pure { gamma db } pure { gamma r };555R r556| _ -> Top557end558
into * b = r backward, for an into whose elements are all integers (otherwise Top). Sound for the integers x that satisfy it. Top exactly when the representatives are not rational, into does not have only integers, or gcd (b.div, r.div) divides b.rem (the quotients would not be coprime).
Valid (1.6s) (colibri2 76) (cvc5) (split_vc 5) (depth 5)let mul_backward (r:t) (into:option t) (b:t) : backward t565ensures { match result with566| R c -> A.rational b.rem /\ A.rational r.rem567/\ (match into with Some d -> integral d | None -> false end)568/\ not (dv (A.real b.rem) (Q.gcd_q b.div r.div))569/\ S.subset (S.inter ints (pre_mul (gamma b) (gamma r))) (gamma c)570| Top -> not (A.rational b.rem) \/ not (A.rational r.rem)571\/ (match into with Some d -> not (integral d) | None -> true end)572\/ dv (A.real b.rem) (Q.gcd_q b.div r.div)573end }574= match A.view b.rem, A.view r.rem with575| A.Rat brem, A.Rat rrem ->576let ok = match into with Some d -> is_integer d | None -> false end in577if ok then begin578let m = Q.gcd b.div r.div in579let d = Q.gcd m brem in580if Q.equal d m then Top581else begin582(* `m` does not divide `brem`, otherwise `d = m` *)583if pure { dv (Q.real brem) (Q.real m) } then begin584dv_self (Q.real m);585dv_antisym (Q.real d) (Q.real m)586end;587(* `d` is not zero: otherwise `m` is zero too *)588assert { Q.real d <> 0.0 };589let div = Q.divexact m d in590let r_rem' = Q.div rrem d in591(* the coefficients of Bezout of the quotients, which are coprime *)592let lemma coprime (a':int) (g' u v:int) : unit593requires { Q.real brem = from_int a' *. Q.real d }594requires { 0 <= g' }595requires { g' = u * a' + v * div }596requires { exists a'':int. a' = a'' * g' }597requires { exists d':int. div = d' * g' }598ensures { g' = 1 }599= let a'' = any int ensures { a' = result * g' } in600let d' = any int ensures { div = result * g' } in601let r = Q.mul (Q.of_bigint g') d in602assert { Q.real r = from_int g' *. Q.real d };603assert { from_int a' = from_int a'' *. from_int g' };604assert { from_int div = from_int d' *. from_int g' };605assert { Q.real brem = from_int a'' *. Q.real r };606assert { Q.real m = from_int d' *. Q.real r };607assert { dv (Q.real brem) (Q.real r) };608assert { dv (Q.real m) (Q.real r) };609let k = any int ensures { Q.real d = from_int result *. Q.real r } in610assert { from_int (k * g') = 1.0 };611unit_int k g' in612let lemma core (a' u v xi:int) (y:real) : unit613requires { Q.real brem = from_int a' *. Q.real d }614requires { u * a' + v * div = 1 }615requires { member y b }616requires { member (from_int xi *. y) r }617ensures { dv (from_int xi -. Q.real r_rem' *. from_int u) (from_int div) }618= let x = from_int xi in619let l = any int ensures { y -. A.real b.rem = from_int result *. Q.real b.div } in620let k = any int ensures { x *. y -. A.real r.rem = from_int result *. Q.real r.div } in621let beta = any int ensures { Q.real b.div = from_int result *. Q.real m } in622let rho = any int ensures { Q.real r.div = from_int result *. Q.real m } in623let t = k * rho - xi * l * beta in624let ghost fd = Q.real d in625let ghost fm = Q.real m in626let ghost rr = Q.real r_rem' in627assert { A.real b.rem = Q.real brem /\ A.real r.rem = Q.real rrem };628assert { fm = from_int div *. fd };629assert { rr *. fd = Q.real rrem };630assert { from_int t = from_int k *. from_int rho -. from_int xi *. from_int l *. from_int beta };631let ghost fl = from_int l in632let ghost fk = from_int k in633let ghost fb = from_int beta in634let ghost fr = from_int rho in635assert { Q.real brem = y -. fl *. Q.real b.div };636assert { Q.real rrem = x *. y -. fk *. Q.real r.div };637assert { x *. Q.real brem = x *. (y -. fl *. Q.real b.div) };638assert { x *. (y -. fl *. Q.real b.div) = x *. y -. (x *. fl) *. Q.real b.div };639assert { x *. Q.real brem -. Q.real rrem = fk *. Q.real r.div -. (x *. fl) *. Q.real b.div };640assert { Q.real b.div = fb *. fm /\ Q.real r.div = fr *. fm };641assert { x *. Q.real brem -. Q.real rrem = (fk *. fr -. x *. fl *. fb) *. fm };642assert { x *. Q.real brem -. Q.real rrem = from_int t *. fm };643assert { (x *. from_int a' -. rr) *. fd = (from_int t *. from_int div) *. fd };644assert { x *. from_int a' -. rr = from_int t *. from_int div };645let ghost fu = from_int u in646let ghost fa = from_int a' in647let ghost fv = from_int v in648let ghost fdiv = from_int div in649assert { fu *. fa +. fv *. fdiv = 1.0 };650assert { x *. (fu *. fa +. fv *. fdiv) = x };651assert { x -. rr *. fu = x *. (fu *. fa +. fv *. fdiv) -. rr *. fu };652assert { x -. rr *. fu = fu *. (x *. fa -. rr) +. fv *. x *. fdiv };653assert { from_int (u * t + xi * v) = fu *. from_int t +. x *. fv };654assert { x -. rr *. from_int u = from_int (u * t + xi * v) *. from_int div } in655let rem, ghost a', ghost u, ghost v =656if Q.is_zero r_rem' then begin657let ghost a' = Q.divexact brem d in658let ghost g', u, v = Z.gcdext a' div in659gcd_facts a' div;660coprime a' g' u v;661((Q.of_int 0), a', u, v)662end else begin663let a' = Q.divexact brem d in664let g', u, ghost v = Z.gcdext a' div in665gcd_facts a' div;666coprime a' g' u v;667((Q.mul r_rem' (Q.of_bigint u)), a', u, v)668end in669let c = norm { div = Q.of_bigint div; rem = A.of_q rem } in670let lemma sound (x y:real) : unit671requires { Real.is_integer x }672requires { member y b }673requires { member (x *. y) r }674ensures { member x c }675= let xi = Real.int_of x in676core a' u v xi y;677assert { Q.real rem = Q.real r_rem' *. from_int u } in678R c679end680end else Top681| _ -> Top682end683
r is the Euclidean remainder of x by y (which is not zero), in the terms of mod_e_facts
predicate is_mod_e (x y r:real) =687(exists k:int. r = x -. from_int k *. y) /\ 0.0 <=. r /\ r <. abs y688
The remainder is unique
Valid (131ms) (cvc5)let ghost mod_e_unique (r r0 y:real) (n:int) : unit691requires { 0.0 <=. r /\ r <. abs y }692requires { 0.0 <=. r0 /\ r0 <. abs y }693requires { r -. r0 = from_int n *. y }694ensures { r = r0 }695= if n >= 1 then begin696assert { from_int n >=. 1.0 };697if y >. 0.0 then begin698mul_nonneg (from_int n -. 1.0) y;699assert { from_int n *. y >=. y }700end else begin701mul_nonneg (from_int n -. 1.0) (-. y);702assert { from_int n *. y <=. y }703end704end else if n <= -1 then begin705assert { from_int n <=. -1.0 };706if y >. 0.0 then begin707mul_nonneg (-. from_int n -. 1.0) y;708assert { from_int n *. y <=. -. y }709end else begin710mul_nonneg (-. from_int n -. 1.0) (-. y);711assert { from_int n *. y >=. -. y }712end713end else assert { n = 0 }714
The remainders mod_e x y of the x of a by the non zero y of d, when d is not the single real zero with a a singleton (the case of the remainder by zero is mod_e_forward of Export). Top exactly when the representative of d is not rational.
Valid (1.4s) (colibri2 46) (cvc4 2) (cvc5 4) (split_vc) (depth 1)let mod_e_forward_nz (a d:t) : backward t720requires { not (Q.real d.div = 0.0 /\ A.real d.rem = 0.0 /\ Q.real a.div = 0.0) }721ensures { match result with722| R c -> A.rational d.rem723/\ S.subset (map2nz (fun (x:real) (y:real) -> Real.mod_e x y) (gamma a) (gamma d)) (gamma c)724| Top -> not (A.rational d.rem)725end }726= let lemma to_is (x y r:real) : unit727requires { y <> 0.0 }728requires { r = Real.mod_e x y }729ensures { is_mod_e x y r }730= mod_e_facts x y;731assert { exists k:int. r = x -. from_int k *. y by k = Real.div_e x y } in732match A.view d.rem with733| A.Rat drem ->734if Q.is_zero d.div then begin735let divisible, ghost lam = Q.divisible a.div drem in736if divisible then begin737begin738dv_zero_iff (Q.real a.div);739let r0 = A.mod_e a.rem d.rem in740mod_e_facts pure { A.real a.rem } pure { A.real d.rem };741let ghost k0 = pure { Real.div_e (A.real a.rem) (A.real d.rem) } in742let c = singleton r0 in743let lemma sound (x y r:real) : unit744requires { member x a }745requires { member y d }746requires { is_mod_e x y r }747ensures { member r c }748= let k = any int ensures { x -. A.real a.rem = from_int result *. Q.real a.div } in749let j = any int ensures { r = x -. from_int result *. y } in750assert { y = Q.real drem };751assert { Q.real a.div = from_int lam *. Q.real drem };752let ghost fk = from_int k in753let ghost fl = from_int lam in754let ghost fj = from_int j in755let ghost fk0 = from_int k0 in756assert { A.real d.rem = Q.real drem };757assert { A.real r0 = A.real a.rem -. fk0 *. y };758assert { x -. A.real a.rem = fk *. (fl *. y) };759assert { from_int (k * lam - j + k0) = fk *. fl -. fj +. fk0 };760assert { r -. A.real r0 = (fk *. fl -. fj +. fk0) *. y };761assert { r -. A.real r0 = from_int (k * lam - j + k0) *. y };762mod_e_unique r (A.real r0) y (k * lam - j + k0) in763map2nz_sound pure { fun (x:real) (y:real) -> Real.mod_e x y } pure { gamma a } pure { gamma d } pure { gamma c };764R c765end766end else begin767let g = Q.gcd a.div drem in768let c = norm { div = g; rem = a.rem } in769let lemma sound (x y r:real) : unit770requires { member x a }771requires { member y d }772requires { is_mod_e x y r }773ensures { member r c }774= let k = any int ensures { x -. A.real a.rem = from_int result *. Q.real a.div } in775let j = any int ensures { r = x -. from_int result *. y } in776assert { y = Q.real drem };777dv_mul (Q.real a.div) (Q.real g) k;778dv_mul (Q.real drem) (Q.real g) j;779dv_sub (from_int k *. Q.real a.div) (from_int j *. Q.real drem) (Q.real g);780assert { r -. A.real a.rem = from_int k *. Q.real a.div -. from_int j *. Q.real drem } in781map2nz_sound pure { fun (x:real) (y:real) -> Real.mod_e x y } pure { gamma a } pure { gamma d } pure { gamma c };782R c783end784end else begin785let g1 = Q.gcd a.div drem in786let g = Q.gcd d.div g1 in787let c = norm { div = g; rem = a.rem } in788let lemma sound (x y r:real) : unit789requires { member x a }790requires { member y d }791requires { is_mod_e x y r }792ensures { member r c }793= let k = any int ensures { x -. A.real a.rem = from_int result *. Q.real a.div } in794let l = any int ensures { y -. A.real d.rem = from_int result *. Q.real d.div } in795let j = any int ensures { r = x -. from_int result *. y } in796dv_trans (Q.real a.div) (Q.real g1) (Q.real g);797dv_trans (Q.real drem) (Q.real g1) (Q.real g);798dv_mul (Q.real a.div) (Q.real g) k;799dv_mul (Q.real drem) (Q.real g) j;800dv_mul (Q.real d.div) (Q.real g) (j * l);801dv_sub (from_int k *. Q.real a.div) (from_int j *. Q.real drem) (Q.real g);802dv_sub (from_int k *. Q.real a.div -. from_int j *. Q.real drem) (from_int (j * l) *. Q.real d.div) (Q.real g);803assert { A.real d.rem = Q.real drem };804assert { from_int (j * l) = from_int j *. from_int l };805assert { y = Q.real drem +. from_int l *. Q.real d.div };806assert { r = (A.real a.rem +. from_int k *. Q.real a.div)807-. from_int j *. (Q.real drem +. from_int l *. Q.real d.div) };808assert { r -. A.real a.rem809= from_int k *. Q.real a.div -. from_int j *. Q.real drem -. from_int (j * l) *. Q.real d.div } in810map2nz_sound pure { fun (x:real) (y:real) -> Real.mod_e x y } pure { gamma a } pure { gamma d } pure { gamma c };811R c812end813| A.Irr -> Top814end815
The n such that m = n mod d for a d of sd (not zero) and an m of sm
function mod_num (sd sm: S.set real) : S.set real =819fun n -> exists d m. S.mem d sd /\ S.mem m sm /\ d <> 0.0 /\ m = Real.mod_e n d820
The numerators of mod_ = num mod den
Valid (1.5s) (colibri2 21) (cvc5 2) (split_vc) (depth 1)let mod_e_backward_num (den mod_:t) : backward t823ensures { match result with824| R c -> A.rational den.rem825/\ S.subset (mod_num (gamma den) (gamma mod_)) (gamma c)826| Top -> not (A.rational den.rem)827end }828= match A.view den.rem with829| A.Rat den_rem ->830let g1 = Q.gcd den.div den_rem in831let g = Q.gcd g1 mod_.div in832let r = norm { div = g; rem = mod_.rem } in833let lemma sound (n d m:real) (q:int) : unit834requires { member d den }835requires { member m mod_ }836requires { n = m +. d *. from_int q }837ensures { member n r }838= let l = any int ensures { d -. A.real den.rem = from_int result *. Q.real den.div } in839let p = any int ensures { m -. A.real mod_.rem = from_int result *. Q.real mod_.div } in840dv_trans (Q.real den_rem) (Q.real g1) (Q.real g);841dv_trans (Q.real den.div) (Q.real g1) (Q.real g);842dv_mul (Q.real den_rem) (Q.real g) q;843dv_mul (Q.real den.div) (Q.real g) (l * q);844dv_mul (Q.real mod_.div) (Q.real g) p;845dv_add (from_int p *. Q.real mod_.div) (from_int q *. Q.real den_rem) (Q.real g);846dv_add (from_int p *. Q.real mod_.div +. from_int q *. Q.real den_rem)847(from_int (l * q) *. Q.real den.div) (Q.real g);848assert { A.real den.rem = Q.real den_rem };849assert { from_int (l * q) = from_int l *. from_int q };850assert { n -. A.real mod_.rem851= from_int p *. Q.real mod_.div +. from_int q *. Q.real den_rem852+. from_int (l * q) *. Q.real den.div } in853let lemma fin (n d m:real) : unit854requires { member d den }855requires { member m mod_ }856requires { d <> 0.0 }857requires { m = Real.mod_e n d }858ensures { member n r }859= mod_e_facts n d;860sound n d m (pure { Real.div_e n d }) in861R r862| A.Irr -> Top863end864
The largest element of da that is not above a, for a da that is not a singleton
Valid (665ms) (colibri2)let floor_a_nz (a:A.t) (da:t) : A.t868requires { Q.real da.div <> 0.0 }869ensures { S.mem (A.real result) (gamma da) /\ A.real result <=. A.real a }870ensures { forall z. S.mem z (gamma da) -> z <=. A.real a -> z <=. A.real result }871= let m = Q.abs da.div in872let x = A.sub a da.rem in873let q = A.round_down_to x m in874let r = A.add (A.of_q q) da.rem in875let ghost k = quot pure { Q.real q } pure { Q.real m } in876dv_abs (A.real r -. A.real da.rem) (Q.real da.div);877assert { A.real r -. A.real da.rem = from_int k *. Q.real m };878let lemma best (z:real) : unit879requires { member z da }880requires { z <=. A.real a }881ensures { z <=. A.real r }882= dv_abs (z -. A.real da.rem) (Q.real da.div);883let j = quot pure { z -. A.real da.rem } pure { Q.real m } in884if j >= k + 1 then assert { from_int j *. Q.real m >=. from_int (k + 1) *. Q.real m };885assert { j <= k };886assert { from_int j *. Q.real m <=. from_int k *. Q.real m } in887r888
The smallest element of da that is not below a, for a da that is not a singleton
Valid (149ms) (colibri2)let ceil_a_nz (a:A.t) (da:t) : A.t892requires { Q.real da.div <> 0.0 }893ensures { S.mem (A.real result) (gamma da) /\ A.real a <=. A.real result }894ensures { forall z. S.mem z (gamma da) -> A.real a <=. z -> A.real result <=. z }895= let m = Q.abs da.div in896let x = A.sub a da.rem in897let q = A.round_up_to x m in898let r = A.add (A.of_q q) da.rem in899let ghost k = quot pure { Q.real q } pure { Q.real m } in900dv_abs (A.real r -. A.real da.rem) (Q.real da.div);901assert { A.real r -. A.real da.rem = from_int k *. Q.real m };902let lemma best (z:real) : unit903requires { member z da }904requires { A.real a <=. z }905ensures { A.real r <=. z }906= dv_abs (z -. A.real da.rem) (Q.real da.div);907let j = quot pure { z -. A.real da.rem } pure { Q.real m } in908if j <= k - 1 then assert { from_int j *. Q.real m <=. from_int (k - 1) *. Q.real m };909assert { j >= k };910assert { from_int j *. Q.real m >=. from_int k *. Q.real m } in911r912
The integers a and b have the same bits on the positions of mask (the meaning of KnownBits.cst_mask)
predicate agree (mask a b:int) =916forall j. 0 <= j -> Zbit.bittest mask j -> (Zbit.bittest a j <-> Zbit.bittest b j)917
The divisor of c is an odd integer
predicate odd_div (c:t) = exists dd:int. Q.real c.div = from_int dd /\ Zbit.bittest dd 0920
The bits shared by all the integers of c, as a KnownBits.t. It is KnownBits.top exactly when the divisor is zero or not an even integer, or the representative is not an integer.
Valid (1.6s) (colibri2 16) (cvc4) (cvc5 2) (split_vc) (depth 1)let to_knownbits (c:t) : KB.t925ensures { forall n:int. S.mem (from_int n) (gamma c) -> KB.mem n result }926ensures { result = KB.top <->927(Q.real c.div = 0.0 \/ not (Real.is_integer (Q.real c.div))928\/ not (Real.is_integer (A.real c.rem)) \/ odd_div c) }929= if not (Q.is_zero c.div) && Q.is_integer c.div && A.is_integer c.rem then begin930let dd = Q.to_z c.div in931let rv = A.to_z c.rem in932let i = Zbit.trailing_zeros dd in933if i = 0 then KB.top934else begin935let mask = ZbitInt.mask_int i in936(* `dd` is a multiple of `2^i` *)937LowBits.sub_low dd 0 i;938let ghost m = any int ensures { dd - 0 = result * Zbit.lsl 1 i } in939let lemma sound (n:int) : unit940requires { member (from_int n) c }941ensures { forall j. 0 <= j -> Zbit.bittest mask j -> (Zbit.bittest n j <-> Zbit.bittest rv j) }942= let k = any int ensures { from_int n -. A.real c.rem = from_int result *. Q.real c.div } in943assert { from_int (n - rv) = from_int (k * dd) };944assert { n - rv = (k * m) * Zbit.lsl 1 i };945LowBits.same_low n rv (k * m) i;946let lemma low (j:int) : unit947requires { 0 <= j }948requires { Zbit.bittest mask j }949ensures { j < i }950= () in () in951let r = KB.cst_mask rv mask in952(* `r` is not top: the bit 0 is in `mask` and `rv` has it set or not *)953if pure { r = KB.top } then begin954assert { Zbit.bittest mask 0 };955let x = Zbit.lxor rv 1 in956assert { KB.mem x r };957assert { Zbit.bittest x 0 <-> not (Zbit.bittest rv 0) }958end;959r960end961end else KB.top962
The integers of a KnownBits.t
Valid (787ms) (colibri2 13) (cvc5) (split_vc) (depth 1)let of_knownbits (k:KB.t) : t965ensures { forall n:int. KB.mem n k -> S.mem (from_int n) (gamma result) }966= let l = k.KB.l in967let u = k.KB.u in968let d = Zbit.lxor l u in969let lemma dbit (j:int) : unit970requires { 0 <= j }971ensures { Zbit.bittest d j <-> not (Zbit.bittest l j <-> Zbit.bittest u j) }972= () in973if d = 0 then begin974let r = singleton (A.of_bigint l) in975let lemma sound (n:int) : unit976requires { Zbit.subset u n }977requires { Zbit.subset n l }978ensures { member (from_int n) r }979= let lemma bit (j:int) : unit980requires { 0 <= j }981ensures { Zbit.bittest n j <-> Zbit.bittest l j }982= () in983Zbit.ext_bittest n l in984r985end else begin986let t = Zbit.trailing_zeros d in987if t = 0 then integers ()988else begin989let rv = Zbit.land l (ZbitInt.mask_int t) in990let c = norm { div = Q.of_bigint (ZbitInt.lsl_int 1 t); rem = A.of_bigint rv } in991let lemma sound (n:int) : unit992requires { Zbit.subset u n }993requires { Zbit.subset n l }994ensures { member (from_int n) c }995= let lemma bit (j:int) : unit996requires { 0 <= j < t }997ensures { Zbit.bittest n j <-> Zbit.bittest rv j }998= () in999LowBits.sub_low n rv t;1000let m = any int ensures { n - rv = result * Zbit.lsl 1 t } in1001assert { from_int n -. from_int rv = from_int m *. from_int (Zbit.lsl 1 t) } in1002c1003end1004end1005
The integers of c, exactly
Valid (41ms) (colibri2)let reduce_integers (c:t) : option t1008ensures { match result with1009| Some r -> gamma r = S.inter ints (gamma c)1010| None -> S.is_empty (S.inter ints (gamma c))1011end }1012= inter (integers ()) c1013
The truncations of the elements of x
Valid (46ms) (colibri2)let truncate_forward (x:t) : t1016ensures { S.subset (image (fun v -> from_int (Truncate.truncate v)) (gamma x)) (gamma result) }1017= let r = integers () in1018let lemma all (v:real) : unit1019ensures { S.mem (from_int (Truncate.truncate v)) (gamma r) }1020= ints_intro (Truncate.truncate v) in1021image_sound pure { fun v -> from_int (Truncate.truncate v) } pure { gamma x } pure { gamma r };1022r1023
The ceilings
Valid (127ms) (colibri2)let ceil_forward (x:t) : t1026ensures { S.subset (image (fun v -> from_int (Truncate.ceil v)) (gamma x)) (gamma result) }1027= if Q.is_integer x.div then begin1028let c = A.of_bigint (A.ceil_z x.rem) in1029let r = norm { div = x.div; rem = c } in1030let lemma sound (v:real) : unit1031requires { member v x }1032ensures { dv (from_int (ceil v) -. A.real c) (Q.real x.div) }1033= let m = any int ensures { Q.real x.div = from_int result } in1034let k = any int ensures { v -. A.real x.rem = from_int result *. Q.real x.div } in1035assert { v = A.real x.rem +. from_int (k * m) };1036ceil_shift (A.real x.rem) (k * m);1037assert { from_int (ceil v) -. A.real c = from_int k *. Q.real x.div } in1038image_sound pure { fun v -> from_int (Truncate.ceil v) } pure { gamma x } pure { gamma r };1039r1040end else begin1041let r = integers () in1042let lemma all (v:real) : unit1043ensures { S.mem (from_int (Truncate.ceil v)) (gamma r) }1044= ints_intro (Truncate.ceil v) in1045image_sound pure { fun v -> from_int (Truncate.ceil v) } pure { gamma x } pure { gamma r };1046r1047end1048
The floors
Valid (370ms) (colibri2)let floor_forward (x:t) : t1051ensures { S.subset (image (fun v -> from_int (Truncate.floor v)) (gamma x)) (gamma result) }1052= if Q.is_integer x.div then begin1053let c = A.of_bigint (A.floor_z x.rem) in1054let r = norm { div = x.div; rem = c } in1055let lemma sound (v:real) : unit1056requires { member v x }1057ensures { dv (from_int (floor v) -. A.real c) (Q.real x.div) }1058= let m = any int ensures { Q.real x.div = from_int result } in1059let k = any int ensures { v -. A.real x.rem = from_int result *. Q.real x.div } in1060assert { v = A.real x.rem +. from_int (k * m) };1061floor_shift (A.real x.rem) (k * m);1062assert { from_int (floor v) -. A.real c = from_int k *. Q.real x.div } in1063image_sound pure { fun v -> from_int (Truncate.floor v) } pure { gamma x } pure { gamma r };1064r1065end else begin1066let r = integers () in1067let lemma all (v:real) : unit1068ensures { S.mem (from_int (Truncate.floor v)) (gamma r) }1069= ints_intro (Truncate.floor v) in1070image_sound pure { fun v -> from_int (Truncate.floor v) } pure { gamma x } pure { gamma r };1071r1072end1073
The values of relu. Top exactly when the representative is not rational.
Valid (774ms) (cvc4)let relu_forward (a:t) : backward t1077ensures { match result with1078| R c -> A.rational a.rem1079/\ S.subset (image (fun x -> if x <. 0.0 then 0.0 else x) (gamma a)) (gamma c)1080| Top -> not (A.rational a.rem)1081end }1082= rat_neg (A.real a.rem);1083let z = singleton ((A.of_int 0)) in1084match union z a with1085| R c ->1086let lemma pw (x:real) : unit1087requires { member x a }1088ensures { member (if x <. 0.0 then 0.0 else x) c }1089= if x <. 0.0 then begin1090assert { member 0.0 z };1091sub_member z c 0.01092end else sub_member a c x in1093image_sound pure { fun x -> if x <. 0.0 then 0.0 else x } pure { gamma a } pure { gamma c };1094R c1095| Top -> Top1096end1097
The absolute values. Top exactly when the representative is not rational.
Valid (135ms) (colibri2 13) (split_vc) (depth 1)let abs_forward (a:t) : backward t1101ensures { match result with1102| R c -> A.rational a.rem1103/\ S.subset (image (fun x -> abs x) (gamma a)) (gamma c)1104| Top -> not (A.rational a.rem)1105end }1106= let n = neg_forward a in1107rat_q a.div;1108let ghost k = any int ensures { A.real n.rem = -. A.real a.rem +. from_int result *. Q.real a.div } in1109rat_double (A.real a.rem) (A.real n.rem) (Q.real a.div) k;1110match union a n with1111| R c ->1112let lemma pw (x:real) : unit1113requires { member x a }1114ensures { member (abs x) c }1115= if x >=. 0.0 then begin1116assert { abs x = x };1117sub_member a c x1118end else begin1119assert { abs x = -. x };1120assert { member (-. x) n };1121sub_member n c (-. x)1122end in1123image_sound pure { fun x -> abs x } pure { gamma a } pure { gamma c };1124R c1125| Top -> Top1126end1127
y is in a or in the negation of a when |y| is in a
Valid (44ms) (colibri2)let ghost abs_cases (a n:t) (y:real) : unit1130requires { forall x. member x n <-> member (-. x) a }1131requires { member (abs y) a }1132ensures { member y a \/ member y n }1133= if y >=. 0.0 then assert { abs y = y }1134else assert { abs y = -. y }1135
The y whose absolute value is in a. Top exactly when the representative is not rational.
Valid (2.5s) (colibri2 6) (cvc5 2) (split_vc 2) (depth 2)let abs_backward (a:t) : backward t1139ensures { match result with1140| R c -> A.rational a.rem1141/\ S.subset (preimage (fun y -> abs y) (gamma a)) (gamma c)1142| Top -> not (A.rational a.rem)1143end }1144= let n = neg_forward a in1145rat_q a.div;1146let ghost k = any int ensures { A.real n.rem = -. A.real a.rem +. from_int result *. Q.real a.div } in1147rat_double (A.real a.rem) (A.real n.rem) (Q.real a.div) k;1148match union a n with1149| R c ->1150let lemma back (y:real) : unit1151requires { member (abs y) a }1152ensures { member y c }1153= abs_cases a n y in1154R c1155| Top -> Top1156end1157
The integer divisions have an integer result
Valid (54ms) (colibri2)let div_e_forward (a b:t) : t1160ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_e x y)) (gamma a) (gamma b))1161(gamma result) }1162= let r = integers () in1163let lemma all (x y:real) : unit1164ensures { S.mem (from_int (Real.div_e x y)) (gamma r) }1165= ints_intro pure { Real.div_e x y } in1166map2nz_sound pure { fun (x:real) (y:real) -> from_int (Real.div_e x y) }1167pure { gamma a } pure { gamma b } pure { gamma r };1168r1169Valid (55ms) (colibri2)1170let div_f_forward (a b:t) : t1171ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_f x y)) (gamma a) (gamma b))1172(gamma result) }1173= let r = integers () in1174let lemma all (x y:real) : unit1175ensures { S.mem (from_int (Real.div_f x y)) (gamma r) }1176= ints_intro pure { Real.div_f x y } in1177map2nz_sound pure { fun (x:real) (y:real) -> from_int (Real.div_f x y) }1178pure { gamma a } pure { gamma b } pure { gamma r };1179r1180Valid (64ms) (colibri2)1181let div_t_forward (a b:t) : t1182ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_t x y)) (gamma a) (gamma b))1183(gamma result) }1184= let r = integers () in1185let lemma all (x y:real) : unit1186ensures { S.mem (from_int (Real.div_t x y)) (gamma r) }1187= ints_intro pure { Real.div_t x y } in1188map2nz_sound pure { fun (x:real) (y:real) -> from_int (Real.div_t x y) }1189pure { gamma a } pure { gamma b } pure { gamma r };1190r1191end1192