library colibrilib.models — module CAModelflint.CA: the real numbers. The values of the model are ghost reals, so the operations that return data (comparisons, floor, to_q, ...) are given by any with the contract of the val: the proof of an any is the existence of its result.
module CAModel332use int.Int333use int.EuclideanDivision as E334use number.Divisibility335use number.Gcd336use real.RealInfix337use real.FromInt338use real.Abs339use real.Square340use real.Truncate341use real.PowerReal as PR342use mach.int.Int63343use option.Option344use colibrilib.zarith.Q as Q345use colibrilib.q.Real as Real346use real.PowerInt as RP347348type t = { ghost r: real }349Valid (27ms) (colibri2)350let function of_q (q:Q.t) : t351ensures { result.r = Q.real q }352= { r = pure { Q.real q } }353
The specification of to_q (a predicate, a trigger for the existence of the result)
predicate is_to_q (a:t) (o:option Q.t) =357match o with358| Some q -> Q.real q = a.r359| None -> forall q:Q.t. Q.real q <> a.r360end361Valid (30ms) (colibri2 5) (split_vc) (depth 1)362let function to_q (a:t) : option Q.t363ensures { match result with364| Some q -> Q.real q = a.r365| None -> forall q:Q.t. Q.real q <> a.r366end }367= if pure { exists q:Q.t. Q.real q = a.r } then begin368let ghost q = any Q.t ensures { Q.real result = a.r } in369assert { is_to_q a (Some q) }370end else371assert { is_to_q a None };372any option Q.t ensures { is_to_q a result }373
n * n = 2 * d * d has no solution with gcd n d = 1
Valid (417ms) (colibri2 17) (split_vc) (depth 1)let ghost no_root2 (n d:int)376requires { n * n = 2 * (d * d) }377requires { 0 < d }378requires { gcd n d = 1 }379ensures { false }380= let k = E.div n 2 in381if E.mod n 2 = 1 then begin382assert { n = 2 * k + 1 };383assert { n * n = 2 * (2 * k * k + 2 * k) + 1 };384absurd385end;386assert { n = 2 * k };387assert { d * d = 2 * (k * k) };388let j = E.div d 2 in389if E.mod d 2 = 1 then begin390assert { d = 2 * j + 1 };391assert { d * d = 2 * (2 * j * j + 2 * j) + 1 };392absurd393end;394assert { d = 2 * j };395assert { divides 2 n };396assert { divides 2 d };397assert { divides 2 (gcd n d) };398absurd399
A square root of 2 is irrational
Valid (46ms) (colibri2)let ghost root2_irrational (x:real) (q:Q.t)402requires { x *. x = 2.0 }403ensures { Q.real q <> x }404= if pure { Q.real q = x } then begin405let n = q.Q.num in406let d = q.Q.den in407assert { 0 < d /\ gcd n d = 1 };408assert { from_int n /. from_int d *. (from_int n /. from_int d) = 2.0 };409assert { from_int n *. from_int n = 2.0 *. (from_int d *. from_int d) };410assert { from_int (n * n) = from_int (2 * (d * d)) };411no_root2 n d412end413Valid (29ms) (colibri2)414let lemma sqrt2_irrational (q:Q.t)415ensures { Q.real q <> sqrt 2.0 }416= assert { sqr (sqrt 2.0) = 2.0 };417root2_irrational (sqrt 2.0) q418
The lemma function returns its witness: the lemma is exists result. ...
Valid (47ms) (colibri2)let lemma irrational () : t422ensures { forall q:Q.t. Q.real q <> result.r }423= let c = { r = pure { sqrt 2.0 } } in424let lemma irr (q:Q.t) ensures { Q.real q <> c.r } = sqrt2_irrational q in425c426
The sign as an int63 (a predicate, a trigger for the existence of the result)
predicate is_sign (x:int63) (v:real) =430x = if v >. 0. then 1 else if v <. 0. then -1 else 0431Valid (42ms) (colibri2 3) (split_vc) (depth 1)432let function compare (a b:t) : int63433ensures { result = if a.r >. b.r then 1 else if a.r <. b.r then -1 else 0 }434= let ghost v = pure { a.r -. b.r } in435assert { is_sign (if v >. 0. then (1:int63) else if v <. 0. then (-1:int63) else (0:int63)) v };436any int63 ensures { is_sign result v }437Valid (43ms) (colibri2 3) (split_vc) (depth 1)438let function compare_q (a:t) (q:Q.t) : int63439ensures { result = if a.r >. Q.real q then 1 else if a.r <. Q.real q then -1 else 0 }440= let ghost v = pure { a.r -. Q.real q } in441assert { is_sign (if v >. 0. then (1:int63) else if v <. 0. then (-1:int63) else (0:int63)) v };442any int63 ensures { is_sign result v }443Valid (39ms) (colibri2 3) (split_vc) (depth 1)444let function sign (a:t) : int63445ensures { result = if a.r >. 0. then 1 else if a.r <. 0. then -1 else 0 }446= let ghost v = pure { a.r } in447assert { is_sign (if v >. 0. then (1:int63) else if v <. 0. then (-1:int63) else (0:int63)) v };448any int63 ensures { is_sign result v }449Valid (27ms) (cvc5)450let function floor_ (a:t) : int451ensures { result = Truncate.floor a.r }452= any int ensures { result = Truncate.floor a.r }453Valid (28ms) (cvc5)454let function ceil_ (a:t) : int455ensures { result = Truncate.ceil a.r }456= any int ensures { result = Truncate.ceil a.r }457Valid (26ms) (cvc5)458let function truncate_ (a:t) : int459ensures { result = Truncate.truncate a.r }460= any int ensures { result = Truncate.truncate a.r }461Valid (22ms) (colibri2)462let function add (a b:t) : t463ensures { result.r = a.r +. b.r }464= { r = pure { a.r +. b.r } }465Valid (27ms) (colibri2)466let function sub (a b:t) : t467ensures { result.r = a.r -. b.r }468= { r = pure { a.r -. b.r } }469Valid (24ms) (colibri2)470let function mul (a b:t) : t471ensures { result.r = a.r *. b.r }472= { r = pure { a.r *. b.r } }473Valid (24ms) (colibri2)474let function div (a b:t) : t475requires { b.r <> 0. }476ensures { result.r = a.r /. b.r }477= { r = pure { a.r /. b.r } }478Valid (22ms) (colibri2)479let function neg (a:t) : t480ensures { result.r = -. a.r }481= { r = pure { -. a.r } }482Valid (28ms) (colibri2)483let function inv (a:t) : t484requires { a.r <> 0. }485ensures { result.r = 1. /. a.r }486= { r = pure { 1. /. a.r } }487Valid (27ms) (colibri2)488let function abs_ (a:t) : t489ensures { result.r = Abs.abs a.r }490= { r = pure { Abs.abs a.r } }491Valid (25ms) (colibri2)492let function sqrt_ (a:t) : t493requires { 0. <=. a.r }494ensures { result.r = Square.sqrt a.r }495= { r = pure { Square.sqrt a.r } }496Valid (27ms) (cvc5)497let function div_e (a b:t) : int498requires { b.r <> 0. }499ensures { result = Real.div_e a.r b.r }500= any int ensures { result = Real.div_e a.r b.r }501Valid (25ms) (cvc5)502let function div_t (a b:t) : int503requires { b.r <> 0. }504ensures { result = Real.div_t a.r b.r }505= any int ensures { result = Real.div_t a.r b.r }506Valid (24ms) (cvc5)507let function div_f (a b:t) : int508requires { b.r <> 0. }509ensures { result = Real.div_f a.r b.r }510= any int ensures { result = Real.div_f a.r b.r }511Valid (29ms) (colibri2)512let function mod_e (a b:t) : t513requires { b.r <> 0. }514ensures { result.r = Real.mod_e a.r b.r }515= { r = pure { Real.mod_e a.r b.r } }516Valid (27ms) (colibri2)517let function mod_t (a b:t) : t518requires { b.r <> 0. }519ensures { result.r = Real.mod_t a.r b.r }520= { r = pure { Real.mod_t a.r b.r } }521Valid (33ms) (colibri2)522let function mod_f (a b:t) : t523requires { b.r <> 0. }524ensures { result.r = Real.mod_f a.r b.r }525= { r = pure { Real.mod_f a.r b.r } }526Valid (27ms) (colibri2)527let function of_z (z:int) : t528ensures { result.r = from_int z }529= { r = pure { from_int z } }530Valid (31ms) (colibri2)531let function pow_int (a:t) (n:int63) : t532requires { 0 <= n \/ a.r <> 0. }533ensures { result.r = if 0 <= n then RP.power a.r n534else 1. /. RP.power a.r (- n) }535= { r = pure { if 0 <= n then RP.power a.r n else 1. /. RP.power a.r (- n) } }536
The real power with an integer exponent is the power
Valid (672ms) (colibri2)let rec lemma pow_int_power (x:real) (n:int)539requires { 0. <. x }540requires { 0 <= n }541ensures { PR.pow x (from_int n) = RP.power x n }542variant { n }543= if n > 0 then begin544pow_int_power x (n - 1);545assert { PR.pow x (from_int n) = PR.pow x (from_int (n - 1)) *. PR.pow x 1.0 }546end547Valid (45ms) (colibri2)548let rec lemma power_zero (n:int)549requires { 0 < n }550ensures { RP.power 0. n = 0. }551variant { n }552= if n > 1 then power_zero (n - 1)553
The root a^(num/den)
function root (a:real) (e:Q.t) : real =556if a = 0. then 0. else PR.pow a (Q.real e)557Valid (404ms) (colibri2)558let ghost root_spec (a:real) (e:Q.t) : unit559requires { 0. <. a \/ (a = 0. /\ 0 < e.Q.num) }560ensures { 0. <=. root a e }561ensures { 0 <= e.Q.num ->562RP.power (root a e) e.Q.den = RP.power a e.Q.num }563ensures { e.Q.num < 0 ->564RP.power (root a e) e.Q.den *. RP.power a (- e.Q.num) = 1. }565= let n = e.Q.num in566let d = e.Q.den in567if pure { a = 0. } then begin568power_zero n; power_zero d569end else begin570let r = PR.pow a (Q.real e) in571assert { 0. <. r };572pow_int_power r d;573assert { PR.pow r (from_int d) = PR.pow a (Q.real e *. from_int d) };574assert { Q.real e *. from_int d = from_int n };575if n >= 0 then pow_int_power a n576else begin577pow_int_power a (- n);578assert { PR.pow a (from_int n) *. PR.pow a (from_int (- n))579= PR.pow a (from_int n +. from_int (- n)) };580assert { from_int n +. from_int (- n) = 0. }581end582end583Valid (26ms) (colibri2)584let function pow (a:t) (e:Q.t) : t585requires { 0. <. a.r \/ (a.r = 0. /\ 0 < e.Q.num) }586ensures { 0. <=. result.r }587ensures { 0 <= e.Q.num ->588RP.power result.r e.Q.den = RP.power a.r e.Q.num }589ensures { e.Q.num < 0 ->590RP.power result.r e.Q.den *. RP.power a.r (- e.Q.num) = 1. }591= root_spec a.r e;592{ r = pure { root a.r e } }593594let function size (_a:t) : int63 = 0595596clone colibrilib.flint.CA {… begin (* cloned colibrilib.flint.CA *) val function CA.check_is_rational t : option bool val CA.give_up t : a Valid (45ms) (colibri2) lemma CA.irrational end } with597type t = t, function real = r, lemma irrational,598val of_q = of_q, val to_q = to_q, val compare = compare,599val compare_q = compare_q, val sign = sign, val floor = floor_,600val ceil = ceil_, val truncate = truncate_, val add = add, val sub = sub,601val mul = mul, val div = div, val neg = neg, val inv = inv,602val abs = abs_, val sqrt = sqrt_, val div_e = div_e, val div_t = div_t,603val div_f = div_f, val mod_e = mod_e, val mod_t = mod_t,604val mod_f = mod_f, val of_z = of_z, val pow_int = pow_int,605val pow = pow, val size = size606end607