library colibrilib.stda — module StdAmodule StdA : A_intf162use int.Int163use real.RealInfix164use real.FromInt165use real.Abs as RA166use real.Square167use real.Truncate168use mach.int.Int63169use option.Option170use colibrilib.zarith.Q as ZQ171use colibrilib.q.Real as Real172use colibrilib.stdq.StdQ as Q173use colibrilib.stdq.StdQ'impl as SQ174use colibrilib.flint.CA as CA175use colibrilib.spec.Value176use colibrilib.spec.Test177Valid (32ms) (colibri2)178let lemma not_zarith_not_q (c:CA.t) (q:Q.t) : unit179requires { forall z:ZQ.t. ZQ.real z <> CA.real c }180ensures { Q.real q <> CA.real c }181= let z = Q.to_zarith q in assert { ZQ.real z = Q.real q }182Valid (35ms) (colibri2)183let lemma of_zarith (z:ZQ.t) : unit184ensures { exists q:Q.t. Q.real q = ZQ.real z }185= let q = Q.of_zarith z in assert { Q.real q = ZQ.real z }186
An irrational number, and its size
Valid (37ms) (colibri2 2) (split_vc) (depth 1)type irr = { ca: CA.t; size: int63 }189invariant { forall q:Q.t. Q.real q <> CA.real ca }190by { ca = any CA.t ensures { forall z:ZQ.t. ZQ.real z <> CA.real result };191size = 0 }192193type t = Q Q.t | A irr194195function real (x:t) : real =196match x with Q q -> Q.real q | A i -> CA.real i.ca end197198meta coercion function real199200predicate rational (a:t) = Q.is_rat (real a)201Valid (36ms) (colibri2)202let ghost not_rational (i:irr) (q:Q.t) : unit203ensures { Q.real q <> CA.real i.ca }204= ()205Valid (30ms) (colibri2)206let ghost not_integer (i:irr) (z:int) : unit207ensures { from_int z <> CA.real i.ca }208= let ghost q = Q.of_bigint z in assert { Q.real q = from_int z }209
A number of CA in the representation of t
Valid (50ms) (colibri2 2) (split_vc) (depth 1)let function normalize (a:CA.t) : t212ensures { value0 real (CA.real a) result }213= match CA.to_q a with214| Some q -> Q (Q.of_zarith q)215| None ->216match CA.check_is_rational a with217| Some False -> A { ca = a; size = CA.size a }218| _ -> CA.give_up a219end220end221Valid (37ms) (colibri2)222let function to_a (x:t) : CA.t223ensures { value0 CA.real (real x) result }224= match x with Q q -> CA.of_q (Q.to_zarith q) | A ia -> ia.ca end225Valid (67ms) (colibri2)226let compare_int (a b:t) : int63227ensures { result > 0 <-> real a >. real b }228ensures { result < 0 <-> real a <. real b }229= match a, b with230| Q qa, Q qb -> ZQ.compare (Q.to_zarith qa) (Q.to_zarith qb)231| A ia, Q qb -> CA.compare_q ia.ca (Q.to_zarith qb)232| Q qa, A ib -> - CA.compare_q ib.ca (Q.to_zarith qa)233| A ia, A ib -> CA.compare ia.ca ib.ca234end235
A number of A is irrational: never equal to a rational
Valid (41ms) (colibri2)let equal (a b:t) : bool238ensures { decides (real a = real b) result }239= match a, b with240| Q qa, Q qb -> Q.equal qa qb241| A ia, Q qb -> not_rational ia qb; false242| Q qa, A ib -> not_rational ib qa; false243| A ia, A ib -> CA.compare ia.ca ib.ca = 0244end245Valid (50ms) (colibri2)246let sign (a:t) : int63247ensures { result > 0 <-> real a >. 0. }248ensures { result < 0 <-> real a <. 0. }249= match a with Q q -> ZQ.sign (Q.to_zarith q) | A ia -> CA.sign ia.ca end250Valid (42ms) (colibri2)251let is_integer (a:t) : bool252ensures { decides (exists z. real a = from_int z) result }253= match a with254| Q q -> Q.is_integer q255| A ia ->256if pure { exists z. CA.real ia.ca = from_int z } then begin257let ghost z = any int ensures { CA.real ia.ca = from_int result } in258not_integer ia z259end;260false261end262Valid (34ms) (colibri2)263let function is_zero (a:t) : bool264ensures { result <-> real a = 0. }265= match a with266| Q q -> Q.is_zero q267| A ia -> not_integer ia 0; false268end269Valid (25ms) (colibri2)270let of_q (q:Q.t) : t271ensures { value0 real (Q.real q) result }272= Q q273Valid (25ms) (colibri2)274let of_bigint (z:int) : t275ensures { value0 real (from_int z) result }276= Q (Q.of_bigint z)277Valid (24ms) (colibri2)278let of_int (z:int63) : t279ensures { value0 real (from_int z) result }280= Q (Q.of_int z)281
The value of an integer
Valid (37ms) (colibri2)let to_z (a:t) : int284requires { exists z. real a = from_int z }285ensures { value0 from_int (real a) result }286= match a with287| Q q -> Q.to_z q288| A ia ->289let ghost z = any int ensures { CA.real ia.ca = from_int result } in290not_integer ia z;291absurd292end293Valid (31ms) (colibri2)294let floor (a:t) : t295ensures { value1 real (fun v -> from_int (Truncate.floor v)) a result }296= match a with Q q -> Q (Q.of_zarith (SQ.floor (Q.to_zarith q))) | A ia -> of_bigint (CA.floor ia.ca) end297Valid (36ms) (colibri2)298let ceil (a:t) : t299ensures { value1 real (fun v -> from_int (Truncate.ceil v)) a result }300= match a with Q q -> Q (Q.of_zarith (SQ.ceil (Q.to_zarith q))) | A ia -> of_bigint (CA.ceil ia.ca) end301Valid (32ms) (colibri2)302let truncate (a:t) : t303ensures { value1 real (fun v -> from_int (Truncate.truncate v)) a result }304= match a with Q q -> Q (Q.of_zarith (SQ.truncate (Q.to_zarith q))) | A ia -> of_bigint (CA.truncate ia.ca) end305Valid (34ms) (colibri2)306let function neg (a:t) : t307ensures { value1 real (fun x -> -. x) a result }308= match a with Q q -> Q (Q.of_zarith (ZQ.neg (Q.to_zarith q))) | A ia -> normalize (CA.neg ia.ca) end309Valid (27ms) (colibri2)310let function abs (a:t) : t311ensures { value1 real RA.abs a result }312= match a with Q q -> Q (Q.abs q) | A ia -> normalize (CA.abs ia.ca) end313Valid (36ms) (colibri2)314let function add (a b:t) : t315ensures { value2 real (+.) a b result }316= match a, b with317| Q qa, Q qb -> Q (Q.add qa qb)318| _ -> normalize (CA.add (to_a a) (to_a b))319end320Valid (42ms) (colibri2)321let function sub (a b:t) : t322ensures { value2 real (-.) a b result }323= match a, b with324| Q qa, Q qb -> Q (Q.sub qa qb)325| _ -> normalize (CA.sub (to_a a) (to_a b))326end327Valid (47ms) (colibri2)328let function mul (a b:t) : t329ensures { value2 real (*.) a b result }330= match a, b with331| Q qa, Q qb -> Q (Q.mul qa qb)332| _ -> normalize (CA.mul (to_a a) (to_a b))333end334Valid (314ms) (colibri2)335let function div (a b:t) : t336requires { real b <> 0. }337ensures { value2 real (/.) a b result }338= match a, b with339| Q qa, Q qb -> Q (Q.div qa qb)340| _ -> normalize (CA.div (to_a a) (to_a b))341end342Valid (56ms) (colibri2)343let div_e (a b:t) : t344requires { real b <> 0. }345ensures { value2 real (fun x y -> from_int (Real.div_e x y)) a b result }346= match a, b with347| Q qa, Q qb -> Q (Q.div_e qa qb)348| _ -> of_bigint (CA.div_e (to_a a) (to_a b))349end350Valid (52ms) (colibri2)351let div_t (a b:t) : t352requires { real b <> 0. }353ensures { value2 real (fun x y -> from_int (Real.div_t x y)) a b result }354= match a, b with355| Q qa, Q qb -> Q (Q.div_t qa qb)356| _ -> of_bigint (CA.div_t (to_a a) (to_a b))357end358Valid (47ms) (colibri2)359let div_f (a b:t) : t360requires { real b <> 0. }361ensures { value2 real (fun x y -> from_int (Real.div_f x y)) a b result }362= match a, b with363| Q qa, Q qb -> Q (Q.div_f qa qb)364| _ -> of_bigint (CA.div_f (to_a a) (to_a b))365end366Valid (53ms) (colibri2)367let function mod_e (a b:t) : t368requires { real b <> 0. }369ensures { value2 real Real.mod_e a b result }370= match a, b with371| Q qa, Q qb -> Q (Q.mod_e qa qb)372| _ -> normalize (CA.mod_e (to_a a) (to_a b))373end374Valid (56ms) (colibri2)375let mod_t (a b:t) : t376requires { real b <> 0. }377ensures { value2 real Real.mod_t a b result }378= match a, b with379| Q qa, Q qb -> Q (Q.mod_t qa qb)380| _ -> normalize (CA.mod_t (to_a a) (to_a b))381end382Valid (52ms) (colibri2)383let mod_f (a b:t) : t384requires { real b <> 0. }385ensures { value2 real Real.mod_f a b result }386= match a, b with387| Q qa, Q qb -> Q (Q.mod_f qa qb)388| _ -> normalize (CA.mod_f (to_a a) (to_a b))389end390Valid (33ms) (colibri2)391let function sqrt (a:t) : t392requires { 0. <=. real a }393ensures { value1 real Square.sqrt a result }394= normalize (CA.sqrt (to_a a))395396use colibrilib.dv.Dv397
The largest multiple of m (positive) below a, and the smallest above
Valid (61ms) (colibri2)let round_down_to (a:t) (m:Q.t) : Q.t401requires { 0. <. Q.real m }402ensures { dv (Q.real result) (Q.real m) }403ensures { Q.real result <=. real a <. Q.real result +. Q.real m }404= match a with405| Q q -> Q.of_zarith (SQ.round_down_to (Q.to_zarith q) (Q.to_zarith m))406| A ia ->407let q' = CA.floor (CA.div ia.ca (CA.of_q (Q.to_zarith m))) in408{proof…}409let ghost x = CA.real ia.ca /. Q.real m in410assert { from_int q' <=. x <. from_int q' +. 1. };411assert { from_int q' *. Q.real m <=. x *. Q.real m412<. (from_int q' +. 1.) *. Q.real m };413assert { x *. Q.real m = CA.real ia.ca };414{qed}415let r = Q.mul (Q.of_bigint q') m in416dv_intro (Q.real r) (Q.real m) q';417r418end419Valid (63ms) (colibri2 11) (split_vc) (depth 1)420let round_up_to (a:t) (m:Q.t) : Q.t421requires { 0. <. Q.real m }422ensures { dv (Q.real result) (Q.real m) }423ensures { Q.real result -. Q.real m <. real a <=. Q.real result }424= match a with425| Q q ->426let r = Q.of_zarith (SQ.round_up_to (Q.to_zarith q) (Q.to_zarith m)) in427let ghost k = any int ensures { Q.real r = from_int result *. Q.real m } in428dv_intro (Q.real r) (Q.real m) k;429r430| A ia ->431let q' = CA.ceil (CA.div ia.ca (CA.of_q (Q.to_zarith m))) in432{proof…}433let ghost x = CA.real ia.ca /. Q.real m in434assert { from_int q' -. 1. <. x <=. from_int q' };435assert { (from_int q' -. 1.) *. Q.real m <. x *. Q.real m436<=. from_int q' *. Q.real m };437assert { x *. Q.real m = CA.real ia.ca };438{qed}439let r = Q.mul (Q.of_bigint q') m in440dv_intro (Q.real r) (Q.real m) q';441r442end443444use real.PowerInt as RP445use colibrilib.stdq.PowRound as SP446
The power a^n (Std.A.pow)
Valid (44ms) (colibri2)let pow (a:t) (n:int63) : t449requires { 0 <= n \/ real a <> 0. }450requires { -0x4000000000000000 < n }451ensures { value1 real (fun x -> if 0 <= n then RP.power x n else 1. /. RP.power x (- n)) a result }452= match a with453| Q q -> Q (Q.of_zarith (SP.pow (Q.to_zarith q) n))454| A ia -> normalize (CA.pow_int ia.ca n)455end456Valid (31ms) (colibri2 6) (split_vc) (depth 1)457let ghost div_bounds (b x c p:real) : unit458requires { 0. <. p }459ensures { b <=. p *. x -> b /. p <=. x }460ensures { b <. p *. x -> b /. p <. x }461ensures { p *. x <=. c -> x <=. c /. p }462ensures { p *. x <. c -> x <. c /. p }463= assert { x = (p *. x) /. p };464assert { p *. x <=. c -> (p *. x) /. p <=. c /. p }465466use colibrilib.zarith.Zbit as Zbit467
The largest power of a rational computed in Zarith by positive_pow, in bits (numerator and denominator): 2^20
let constant pow_bits_limit : int = 0x100000471Valid (55ms) (colibri2)472let rec lemma power_pos (x:real) (m:int) : unit473requires { 0. <. x /\ 0 <= m }474ensures { 0. <. RP.power x m }475variant { m }476= if m > 0 then power_pos x (m - 1)477Valid (52ms) (colibri2)478let rec lemma power_zero (m:int) : unit479requires { 0 < m }480ensures { RP.power 0. m = 0. }481variant { m }482= if m > 1 then power_zero (m - 1)483
a^e, the non negative root (Std.A.positive_pow)
Valid (1.9s) (colibri2 32) (cvc5 2) (split_vc 5) (depth 2)let positive_pow (a:t) (e:Q.t) : t486requires { 0. <. real a \/ (real a = 0. /\ 0. <. Q.real e) }487ensures { 0. <=. real result }488ensures { 0 <= (Q.num e) ->489RP.power (real result) (Q.den e) = RP.power (real a) (Q.num e) }490ensures { (Q.num e) < 0 ->491RP.power (real result) (Q.den e) *. RP.power (real a) (- (Q.num e)) = 1. }492ensures { exists n d:int. 0 < d /\ Q.real e = from_int n /. from_int d /\493(0 <= n -> RP.power (real result) d = RP.power (real a) n) /\494(n < 0 -> RP.power (real result) d *. RP.power (real a) (- n) = 1.) }495= {proof…}496Q.num_den e;497assert { 0. <. Q.real e -> 0 < (Q.num e)498by Q.real e = from_int (Q.num e) /. from_int (Q.den e)499so 0. <. from_int (Q.den e) };500{qed}501match a with502| Q q ->503(* a rational to an integer power: computed in Zarith, as `pow`; Flint keeps a large power symbolic (`Pow(q, n)` beyond about 2^21000), its `to_q` misses it. Up to `pow_bits_limit` bits of result: an exponent such as 10^9 from the input stays symbolic in Flint *)507if Q.is_integer e then begin508let n = Q.to_z e in509let z = Q.to_zarith q in510let bits = Zbit.numbits z.ZQ.num + Zbit.numbits z.ZQ.den in511let an = if n >= 0 then n else - n in512if -0x3fffffffffffffff <= n && n <= 0x3fffffffffffffff513&& an * bits <= pow_bits_limit then begin514let n63 = Int63.of_int n in515{proof…}516let ghost k = Q.num e in517let ghost d = Q.den e in518assert { from_int k = from_int n *. from_int d519by from_int k /. from_int d = from_int n520so from_int k = (from_int k /. from_int d) *. from_int d };521assert { k = n * d };522assert { real a <> 0. \/ 0 < n };523{qed}524let r = pow a n63 in525{proof…}526if n >= 0 then begin527assert { real r = RP.power (real a) n };528assert { 0. <=. real r by 0. <. real a \/ (real a = 0. /\ 0 < n) };529assert { RP.power (real r) d = RP.power (real a) (n * d) };530assert { RP.power (real r) d = RP.power (real a) k }531end else begin532let ghost p = RP.power (real a) (- n) in533assert { 0. <. real a };534assert { 0. <. p };535assert { real r = 1. /. p };536assert { 0. <=. real r };537assert { RP.power (real r) d *. RP.power p d = RP.power (real r *. p) d };538assert { real r *. p = 1. };539assert { RP.power p d = RP.power (real a) ((- n) * d) };540assert { (- n) * d = - k };541assert { RP.power (real r) d *. RP.power (real a) (- k) = 1. }542end;543{qed}544r545end else normalize (CA.pow (to_a a) (Q.to_zarith e))546end else normalize (CA.pow (to_a a) (Q.to_zarith e))547| A _ -> normalize (CA.pow (to_a a) (Q.to_zarith e))548end549
A rational below a, at most 1/prec below (Std.A.floor_q)
Valid (340ms) (colibri2)let floor_q (prec:int) (a:t) : Q.t552requires { 0 < prec }553ensures { Q.real result <=. real a <. Q.real result +. 1. /. from_int prec }554= match a with555| Q q -> q556| A ia ->557let k = CA.floor (CA.mul (CA.of_z prec) ia.ca) in558{proof…}559let ghost p = from_int prec in560assert { from_int k <=. p *. CA.real ia.ca <. from_int k +. 1. };561div_bounds (from_int k) (CA.real ia.ca) (from_int k +. 1.) p;562assert { (from_int k +. 1.) /. p = from_int k /. p +. 1. /. p };563{qed}564Q.of_zarith (ZQ.make k prec)565end566
A rational above a, at most 1/prec above (Std.A.ceil_q)
Valid (328ms) (colibri2)let ceil_q (prec:int) (a:t) : Q.t569requires { 0 < prec }570ensures { Q.real result -. 1. /. from_int prec <. real a <=. Q.real result }571= match a with572| Q q -> q573| A ia ->574let k = CA.ceil (CA.mul (CA.of_z prec) ia.ca) in575{proof…}576let ghost p = from_int prec in577assert { from_int k -. 1. <. p *. CA.real ia.ca <=. from_int k };578div_bounds (from_int k -. 1.) (CA.real ia.ca) (from_int k) p;579assert { (from_int k -. 1.) /. p = from_int k /. p -. 1. /. p };580{qed}581Q.of_zarith (ZQ.make k prec)582end583
A rational below x with a smaller representation (Std.A.round_down_to_small_number when x is big; bigq is Std.Q.big_number)
Valid (319ms) (colibri2)let round_down_to_small (bigq: Q.t -> bool) (max_size_bit prec:int) (x:t) : t588requires { 0 < prec }589ensures { match result with Q _ -> true | A _ -> false end }590ensures { real result <=. real x }591= match x with592| Q q -> Q (Q.of_zarith (SP.round_down_to_small max_size_bit (Q.to_zarith q)))593| A _ ->594let f = floor_q prec x in595if bigq f then Q (Q.of_zarith (SP.round_down_to_small max_size_bit (Q.to_zarith f))) else Q f596end597Valid (338ms) (colibri2)598let round_up_to_small (bigq: Q.t -> bool) (max_size_bit prec:int) (x:t) : t599requires { 0 < prec }600ensures { match result with Q _ -> true | A _ -> false end }601ensures { real x <=. real result }602= match x with603| Q q -> Q (Q.of_zarith (SP.round_up_to_small max_size_bit (Q.to_zarith q)))604| A _ ->605let c = ceil_q prec x in606if bigq c then Q (Q.of_zarith (SP.round_up_to_small max_size_bit (Q.to_zarith c))) else Q c607end608
The two cases of view
type view = Rat Q.t | Irr611Valid (309ms) (colibri2)612let view (a:t) : view613ensures { match result with614| Rat q -> real a = Q.real q615| Irr -> forall q:Q.t. real a <> Q.real q616end }617= match a with Q q -> Rat q | A _ -> Irr end618
The functions of A_intf that return an integer or a comparison
Valid (283ms) (colibri2)let floor_z (a:t) : int621ensures { value_is (Truncate.floor (real a)) result }622= match a with Q q -> Q.floor_z q | A ia -> CA.floor ia.ca end623Valid (44ms) (colibri2)624let ceil_z (a:t) : int625ensures { value_is (Truncate.ceil (real a)) result }626= match a with Q q -> Q.ceil_z q | A ia -> CA.ceil ia.ca end627Valid (44ms) (colibri2)628let truncate_z (a:t) : int629ensures { value_is (Truncate.truncate (real a)) result }630= match a with Q q -> Q.truncate_z q | A ia -> CA.truncate ia.ca end631Valid (47ms) (colibri2)632let le (a b:t) : bool633ensures { decides (real a <=. real b) result }634= compare_int a b <= 0635Valid (50ms) (colibri2)636let lt (a b:t) : bool637ensures { decides (real a <. real b) result }638= compare_int a b < 0639640use colibrilib.q.Ord as Ord641Valid (49ms) (colibri2)642let compare (a b:t) : Ord.t643ensures { match result with644| Ord.Eq -> real a = real b645| Ord.Lt -> real a <. real b646| Ord.Gt -> real b <. real a647end }648= let c = compare_int a b in649if c = 0 then Ord.Eq else if c < 0 then Ord.Lt else Ord.Gt650end651