Common — library colibrilib.q — module Q_intf

The 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.

406
module Q_intf
407
use real.RealInfix
408
use int.Int
409
use real.FromInt
410
use real.Abs
411
use real.Truncate
412
use mach.int.Int63
413
use Ord as Ord
414
use colibrilib.dv.Dv
415
use Real
416
use colibrilib.zarith.Q as ZQ
417
418
type
t
419
420
function
real
(q:t) : real
421
422
axiom
equal_is_eq
: forall a b:t. real a = real b -> a = b

The reals that are rationals

425
predicate
is_rat
(r:real) = exists q:t. real q = r
426
427
val
equal
(a b:t) : bool
428
ensures { result <-> real a = real b }
429
430
val
le
(a b:t) : bool
431
ensures { result <-> real a <=. real b }
432
433
val
lt
(a b:t) : bool
434
ensures { result <-> real a <. real b }
435
436
val
abs
(a:t) : t
437
ensures { real result = abs (real a) }
438
439
val
compare
(a b:t) : Ord.t
440
ensures { match result with
441
| Ord.Eq -> real a = real b
442
| Ord.Lt -> real a <. real b
443
| Ord.Gt -> real b <. real a
444
end }
445
446
val function
add
(a b:t) : t
447
ensures { real result = real a +. real b }
448
449
val function
sub
(a b:t) : t
450
ensures { real result = real a -. real b }
451
452
val function
mul
(a b:t) : t
453
ensures { real result = real a *. real b }
454
455
val function
div
(a b:t) : t
456
requires { real b <> 0. }
457
ensures { real result = real a /. real b }
458
459
val
of_int
(a:int63) : t
460
ensures { real result = from_int a }
461
462
val
of_bigint
(a:int) : t
463
ensures { real result = from_int a }
464
465
val
truncate_z
(a:t) : int
466
ensures { result = truncate (real a) }
467
468
val
floor_z
(a:t) : int
469
ensures { result = floor (real a) }
470
471
val
ceil_z
(a:t) : int
472
ensures { result = ceil (real a) }
473
474
val
is_integer
(a:t) : bool
475
ensures { result <-> Real.is_integer (real a) }
476
477
val
div_e
(a b:t) : t
478
requires { real b <> 0. }
479
ensures { real result = from_int (Real.div_e (real a) (real b)) }
480
481
val
mod_e
(a b:t) : t
482
requires { real b <> 0. }
483
ensures { real result = Real.mod_e (real a) (real b) }
484
485
val
div_t
(a b:t) : t
486
requires { real b <> 0. }
487
ensures { real result = from_int (Real.div_t (real a) (real b)) }
488
489
val
mod_t
(a b:t) : t
490
requires { real b <> 0. }
491
ensures { real result = Real.mod_t (real a) (real b) }
492
493
val
div_f
(a b:t) : t
494
requires { real b <> 0. }
495
ensures { real result = from_int (Real.div_f (real a) (real b)) }
496
497
val
mod_f
(a b:t) : t
498
requires { real b <> 0. }
499
ensures { real result = Real.mod_f (real a) (real b) }

The value of gcd; only its definition by gcd below is given

502
function
gcd_q
(a b:t) : real

A function, for the closures given to the maps (polynome.Lin.nz)

505
val function
is_zero
(a:t) : bool
506
ensures { result <-> real a = 0.0 }

a is an integer multiple of b; d is the multiple. divisible a 0 holds iff a = 0

510
val
divisible
(a b:t) : (r:bool, ghost d:int)
511
ensures { r <-> dv (real a) (real b) }
512
ensures { r -> real a = from_int d *. real b }

The greatest common divisor: non negative, divides a and b, and is a multiple of every common divisor. gcd 0 0 = 0

516
val
gcd
(a b:t) : t
517
ensures { real result = gcd_q a b }
518
ensures { 0.0 <=. real result }
519
ensures { dv (real a) (real result) }
520
ensures { dv (real b) (real result) }
521
ensures { forall r. dv (real a) r -> dv (real b) r -> dv (real result) r }

Bezout: g = u * a + v * b with g the (non negative) gcd a b. The coefficient v is not computed (ghost)

525
val
gcdext
(a b:t) : (g:t, u:int, ghost v:int)
526
ensures { 0.0 <=. real g }
527
ensures { dv (real a) (real g) }
528
ensures { dv (real b) (real g) }
529
ensures { real g = from_int u *. real a +. from_int v *. real b }

The least common multiple: non negative, a multiple of a and b, and divides every common multiple. lcm a 0 = 0

533
val
lcm
(a b:t) : t
534
ensures { 0.0 <=. real result }
535
ensures { dv (real result) (real a) }
536
ensures { dv (real result) (real b) }
537
ensures { forall r. dv r (real a) -> dv r (real b) -> dv r (real result) }

Exact division: b is not zero and divides a

540
val
divexact
(a b:t) : int
541
requires { real b <> 0.0 }
542
requires { dv (real a) (real b) }
543
ensures { real a = from_int result *. real b }

The value of an integer

546
val
to_z
(a:t) : int
547
requires { Real.is_integer (real a) }
548
ensures { from_int result = real a }

The fraction in lowest terms of q; its facts are given by num_den

551
function
num
(q:t) : int
552
function
den
(q:t) : int
553
554
val ghost
num_den
(q:t) : unit
555
ensures { 0 < den q }
556
ensures { real q = from_int (num q) /. from_int (den q) }

The same number as a fraction of Zarith, for the functions on zarith.Q (flint.CA, the extras of StdQ'impl)

560
val
to_zarith
(q:t) : ZQ.t
561
ensures { ZQ.real result = real q }
562
ensures { result.ZQ.num = num q /\ result.ZQ.den = den q }
563
564
val
of_zarith
(q:ZQ.t) : t
565
ensures { real result = ZQ.real q }
566
ensures { num result = q.ZQ.num /\ den result = q.ZQ.den }
567
end