library colibrilib.q — module Q_intfThe rationals, implemented by stdq.StdQ. One name per notion, no program operator: the specifications are on the real value. The numbers are canonical (equal_is_eq). The operations on which the logic needs a term are val functions.
module Q_intf406use real.RealInfix407use int.Int408use real.FromInt409use real.Abs410use real.Truncate411use mach.int.Int63412use Ord as Ord413use colibrilib.dv.Dv414use Real415use colibrilib.zarith.Q as ZQ416417type t418419function real (q:t) : real420421axiom equal_is_eq: forall a b:t. real a = real b -> a = b422
The reals that are rationals
predicate is_rat (r:real) = exists q:t. real q = r425426val equal (a b:t) : bool427ensures { result <-> real a = real b }428429val le (a b:t) : bool430ensures { result <-> real a <=. real b }431432val lt (a b:t) : bool433ensures { result <-> real a <. real b }434435val abs (a:t) : t436ensures { real result = abs (real a) }437438val compare (a b:t) : Ord.t439ensures { match result with440| Ord.Eq -> real a = real b441| Ord.Lt -> real a <. real b442| Ord.Gt -> real b <. real a443end }444445val function add (a b:t) : t446ensures { real result = real a +. real b }447448val function sub (a b:t) : t449ensures { real result = real a -. real b }450451val function mul (a b:t) : t452ensures { real result = real a *. real b }453454val function div (a b:t) : t455requires { real b <> 0. }456ensures { real result = real a /. real b }457458val of_int (a:int63) : t459ensures { real result = from_int a }460461val of_bigint (a:int) : t462ensures { real result = from_int a }463464val truncate_z (a:t) : int465ensures { result = truncate (real a) }466467val floor_z (a:t) : int468ensures { result = floor (real a) }469470val ceil_z (a:t) : int471ensures { result = ceil (real a) }472473val is_integer (a:t) : bool474ensures { result <-> Real.is_integer (real a) }475476val div_e (a b:t) : t477requires { real b <> 0. }478ensures { real result = from_int (Real.div_e (real a) (real b)) }479480val mod_e (a b:t) : t481requires { real b <> 0. }482ensures { real result = Real.mod_e (real a) (real b) }483484val div_t (a b:t) : t485requires { real b <> 0. }486ensures { real result = from_int (Real.div_t (real a) (real b)) }487488val mod_t (a b:t) : t489requires { real b <> 0. }490ensures { real result = Real.mod_t (real a) (real b) }491492val div_f (a b:t) : t493requires { real b <> 0. }494ensures { real result = from_int (Real.div_f (real a) (real b)) }495496val mod_f (a b:t) : t497requires { real b <> 0. }498ensures { real result = Real.mod_f (real a) (real b) }499
The value of gcd; only its definition by gcd below is given
function gcd_q (a b:t) : real502
A function, for the closures given to the maps (polynome.Lin.nz)
val function is_zero (a:t) : bool505ensures { result <-> real a = 0.0 }506
a is an integer multiple of b; d is the multiple. divisible a 0 holds iff a = 0
val divisible (a b:t) : (r:bool, ghost d:int)510ensures { r <-> dv (real a) (real b) }511ensures { r -> real a = from_int d *. real b }512
The greatest common divisor: non negative, divides a and b, and is a multiple of every common divisor. gcd 0 0 = 0
val gcd (a b:t) : t516ensures { real result = gcd_q a b }517ensures { 0.0 <=. real result }518ensures { dv (real a) (real result) }519ensures { dv (real b) (real result) }520ensures { forall r. dv (real a) r -> dv (real b) r -> dv (real result) r }521
Bezout: g = u * a + v * b with g the (non negative) gcd a b. The coefficient v is not computed (ghost)
val gcdext (a b:t) : (g:t, u:int, ghost v:int)525ensures { 0.0 <=. real g }526ensures { dv (real a) (real g) }527ensures { dv (real b) (real g) }528ensures { real g = from_int u *. real a +. from_int v *. real b }529
The least common multiple: non negative, a multiple of a and b, and divides every common multiple. lcm a 0 = 0
val lcm (a b:t) : t533ensures { 0.0 <=. real result }534ensures { dv (real result) (real a) }535ensures { dv (real result) (real b) }536ensures { forall r. dv r (real a) -> dv r (real b) -> dv r (real result) }537
Exact division: b is not zero and divides a
val divexact (a b:t) : int540requires { real b <> 0.0 }541requires { dv (real a) (real b) }542ensures { real a = from_int result *. real b }543
The value of an integer
val to_z (a:t) : int546requires { Real.is_integer (real a) }547ensures { from_int result = real a }548
The fraction in lowest terms of q; its facts are given by num_den
function num (q:t) : int551function den (q:t) : int552553val ghost num_den (q:t) : unit554ensures { 0 < den q }555ensures { real q = from_int (num q) /. from_int (den q) }556
The same number as a fraction of Zarith, for the functions on zarith.Q (flint.CA, the extras of StdQ'impl)
val to_zarith (q:t) : ZQ.t560ensures { ZQ.real result = real q }561ensures { result.ZQ.num = num q /\ result.ZQ.den = den q }562563val of_zarith (q:ZQ.t) : t564ensures { real result = ZQ.real q }565ensures { num result = q.ZQ.num /\ den result = q.ZQ.den }566end567