Common — library colibrilib.models — module CAModel

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

332
module CAModel
333
use int.Int
334
use int.EuclideanDivision as E
335
use number.Divisibility
336
use number.Gcd
337
use real.RealInfix
338
use real.FromInt
339
use real.Abs
340
use real.Square
341
use real.Truncate
342
use real.PowerReal as PR
343
use mach.int.Int63
344
use option.Option
345
use colibrilib.zarith.Q as Q
346
use colibrilib.q.Real as Real
347
use real.PowerInt as RP
348
349
type
t
= { ghost
r
: real }
350
Valid (27ms) (colibri2)
351
let function
of_q
(q:Q.t) : t
352
ensures { result.r = Q.real q }
353
= { r = pure { Q.real q } }

The specification of to_q (a predicate, a trigger for the existence of the result)

357
predicate
is_to_q
(a:t) (o:option Q.t) =
358
match o with
359
| Some q -> Q.real q = a.r
360
| None -> forall q:Q.t. Q.real q <> a.r
361
end
362
Valid (30ms) (colibri2 5) (split_vc) (depth 1)
363
let function
to_q
(a:t) : option Q.t
364
ensures { match result with
365
| Some q -> Q.real q = a.r
366
| None -> forall q:Q.t. Q.real q <> a.r
367
end }
368
= if pure { exists q:Q.t. Q.real q = a.r } then begin
369
let ghost q = any Q.t ensures { Q.real result = a.r } in
370
assert { is_to_q a (Some q) }
371
end else
372
assert { is_to_q a None };
373
any option Q.t ensures { is_to_q a result }

n * n = 2 * d * d has no solution with gcd n d = 1

  Valid (417ms) (colibri2 17) (split_vc) (depth 1)
376
let ghost
no_root2
(n d:int)
377
requires { n * n = 2 * (d * d) }
378
requires { 0 < d }
379
requires { gcd n d = 1 }
380
ensures { false }
381
= let k = E.div n 2 in
382
if E.mod n 2 = 1 then begin
383
assert { n = 2 * k + 1 };
384
assert { n * n = 2 * (2 * k * k + 2 * k) + 1 };
385
absurd
386
end;
387
assert { n = 2 * k };
388
assert { d * d = 2 * (k * k) };
389
let j = E.div d 2 in
390
if E.mod d 2 = 1 then begin
391
assert { d = 2 * j + 1 };
392
assert { d * d = 2 * (2 * j * j + 2 * j) + 1 };
393
absurd
394
end;
395
assert { d = 2 * j };
396
assert { divides 2 n };
397
assert { divides 2 d };
398
assert { divides 2 (gcd n d) };
399
absurd

A square root of 2 is irrational

  Valid (46ms) (colibri2)
402
let ghost
root2_irrational
(x:real) (q:Q.t)
403
requires { x *. x = 2.0 }
404
ensures { Q.real q <> x }
405
= if pure { Q.real q = x } then begin
406
let n = q.Q.num in
407
let d = q.Q.den in
408
assert { 0 < d /\ gcd n d = 1 };
409
assert { from_int n /. from_int d *. (from_int n /. from_int d) = 2.0 };
410
assert { from_int n *. from_int n = 2.0 *. (from_int d *. from_int d) };
411
assert { from_int (n * n) = from_int (2 * (d * d)) };
412
no_root2 n d
413
end
414
Valid (29ms) (colibri2)
415
let lemma
sqrt2_irrational
(q:Q.t)
416
ensures { Q.real q <> sqrt 2.0 }
417
= assert { sqr (sqrt 2.0) = 2.0 };
418
root2_irrational (sqrt 2.0) q

The lemma function returns its witness: the lemma is exists result. ...

  Valid (47ms) (colibri2)
422
let lemma
irrational
() : t
423
ensures { forall q:Q.t. Q.real q <> result.r }
424
= let c = { r = pure { sqrt 2.0 } } in
425
let lemma irr (q:Q.t) ensures { Q.real q <> c.r } = sqrt2_irrational q in
426
c

The sign as an int63 (a predicate, a trigger for the existence of the result)

430
predicate
is_sign
(x:int63) (v:real) =
431
x = if v >. 0. then 1 else if v <. 0. then -1 else 0
432
Valid (42ms) (colibri2 3) (split_vc) (depth 1)
433
let function
compare
(a b:t) : int63
434
ensures { result = if a.r >. b.r then 1 else if a.r <. b.r then -1 else 0 }
435
= let ghost v = pure { a.r -. b.r } in
436
assert { is_sign (if v >. 0. then (1:int63) else if v <. 0. then (-1:int63) else (0:int63)) v };
437
any int63 ensures { is_sign result v }
438
Valid (43ms) (colibri2 3) (split_vc) (depth 1)
439
let function
compare_q
(a:t) (q:Q.t) : int63
440
ensures { result = if a.r >. Q.real q then 1 else if a.r <. Q.real q then -1 else 0 }
441
= let ghost v = pure { a.r -. Q.real q } in
442
assert { is_sign (if v >. 0. then (1:int63) else if v <. 0. then (-1:int63) else (0:int63)) v };
443
any int63 ensures { is_sign result v }
444
Valid (39ms) (colibri2 3) (split_vc) (depth 1)
445
let function
sign
(a:t) : int63
446
ensures { result = if a.r >. 0. then 1 else if a.r <. 0. then -1 else 0 }
447
= let ghost v = pure { a.r } in
448
assert { is_sign (if v >. 0. then (1:int63) else if v <. 0. then (-1:int63) else (0:int63)) v };
449
any int63 ensures { is_sign result v }
450
Valid (27ms) (cvc5)
451
let function
floor_
(a:t) : int
452
ensures { result = Truncate.floor a.r }
453
= any int ensures { result = Truncate.floor a.r }
454
Valid (28ms) (cvc5)
455
let function
ceil_
(a:t) : int
456
ensures { result = Truncate.ceil a.r }
457
= any int ensures { result = Truncate.ceil a.r }
458
Valid (26ms) (cvc5)
459
let function
truncate_
(a:t) : int
460
ensures { result = Truncate.truncate a.r }
461
= any int ensures { result = Truncate.truncate a.r }
462
Valid (22ms) (colibri2)
463
let function
add
(a b:t) : t
464
ensures { result.r = a.r +. b.r }
465
= { r = pure { a.r +. b.r } }
466
Valid (27ms) (colibri2)
467
let function
sub
(a b:t) : t
468
ensures { result.r = a.r -. b.r }
469
= { r = pure { a.r -. b.r } }
470
Valid (24ms) (colibri2)
471
let function
mul
(a b:t) : t
472
ensures { result.r = a.r *. b.r }
473
= { r = pure { a.r *. b.r } }
474
Valid (24ms) (colibri2)
475
let function
div
(a b:t) : t
476
requires { b.r <> 0. }
477
ensures { result.r = a.r /. b.r }
478
= { r = pure { a.r /. b.r } }
479
Valid (22ms) (colibri2)
480
let function
neg
(a:t) : t
481
ensures { result.r = -. a.r }
482
= { r = pure { -. a.r } }
483
Valid (28ms) (colibri2)
484
let function
inv
(a:t) : t
485
requires { a.r <> 0. }
486
ensures { result.r = 1. /. a.r }
487
= { r = pure { 1. /. a.r } }
488
Valid (27ms) (colibri2)
489
let function
abs_
(a:t) : t
490
ensures { result.r = Abs.abs a.r }
491
= { r = pure { Abs.abs a.r } }
492
Valid (25ms) (colibri2)
493
let function
sqrt_
(a:t) : t
494
requires { 0. <=. a.r }
495
ensures { result.r = Square.sqrt a.r }
496
= { r = pure { Square.sqrt a.r } }
497
Valid (27ms) (cvc5)
498
let function
div_e
(a b:t) : int
499
requires { b.r <> 0. }
500
ensures { result = Real.div_e a.r b.r }
501
= any int ensures { result = Real.div_e a.r b.r }
502
Valid (25ms) (cvc5)
503
let function
div_t
(a b:t) : int
504
requires { b.r <> 0. }
505
ensures { result = Real.div_t a.r b.r }
506
= any int ensures { result = Real.div_t a.r b.r }
507
Valid (24ms) (cvc5)
508
let function
div_f
(a b:t) : int
509
requires { b.r <> 0. }
510
ensures { result = Real.div_f a.r b.r }
511
= any int ensures { result = Real.div_f a.r b.r }
512
Valid (29ms) (colibri2)
513
let function
mod_e
(a b:t) : t
514
requires { b.r <> 0. }
515
ensures { result.r = Real.mod_e a.r b.r }
516
= { r = pure { Real.mod_e a.r b.r } }
517
Valid (27ms) (colibri2)
518
let function
mod_t
(a b:t) : t
519
requires { b.r <> 0. }
520
ensures { result.r = Real.mod_t a.r b.r }
521
= { r = pure { Real.mod_t a.r b.r } }
522
Valid (33ms) (colibri2)
523
let function
mod_f
(a b:t) : t
524
requires { b.r <> 0. }
525
ensures { result.r = Real.mod_f a.r b.r }
526
= { r = pure { Real.mod_f a.r b.r } }
527
Valid (27ms) (colibri2)
528
let function
of_z
(z:int) : t
529
ensures { result.r = from_int z }
530
= { r = pure { from_int z } }
531
Valid (31ms) (colibri2)
532
let function
pow_int
(a:t) (n:int63) : t
533
requires { 0 <= n \/ a.r <> 0. }
534
ensures { result.r = if 0 <= n then RP.power a.r n
535
else 1. /. RP.power a.r (- n) }
536
= { r = pure { if 0 <= n then RP.power a.r n else 1. /. RP.power a.r (- n) } }

The real power with an integer exponent is the power

  Valid (672ms) (colibri2)
539
let rec lemma
pow_int_power
(x:real) (n:int)
540
requires { 0. <. x }
541
requires { 0 <= n }
542
ensures { PR.pow x (from_int n) = RP.power x n }
543
variant { n }
544
= if n > 0 then begin
545
pow_int_power x (n - 1);
546
assert { PR.pow x (from_int n) = PR.pow x (from_int (n - 1)) *. PR.pow x 1.0 }
547
end
548
Valid (45ms) (colibri2)
549
let rec lemma
power_zero
(n:int)
550
requires { 0 < n }
551
ensures { RP.power 0. n = 0. }
552
variant { n }
553
= if n > 1 then power_zero (n - 1)

The root a^(num/den)

556
function
root
(a:real) (e:Q.t) : real =
557
if a = 0. then 0. else PR.pow a (Q.real e)
558
Valid (404ms) (colibri2)
559
let ghost
root_spec
(a:real) (e:Q.t) : unit
560
requires { 0. <. a \/ (a = 0. /\ 0 < e.Q.num) }
561
ensures { 0. <=. root a e }
562
ensures { 0 <= e.Q.num ->
563
RP.power (root a e) e.Q.den = RP.power a e.Q.num }
564
ensures { e.Q.num < 0 ->
565
RP.power (root a e) e.Q.den *. RP.power a (- e.Q.num) = 1. }
566
= let n = e.Q.num in
567
let d = e.Q.den in
568
if pure { a = 0. } then begin
569
power_zero n; power_zero d
570
end else begin
571
let r = PR.pow a (Q.real e) in
572
assert { 0. <. r };
573
pow_int_power r d;
574
assert { PR.pow r (from_int d) = PR.pow a (Q.real e *. from_int d) };
575
assert { Q.real e *. from_int d = from_int n };
576
if n >= 0 then pow_int_power a n
577
else begin
578
pow_int_power a (- n);
579
assert { PR.pow a (from_int n) *. PR.pow a (from_int (- n))
580
= PR.pow a (from_int n +. from_int (- n)) };
581
assert { from_int n +. from_int (- n) = 0. }
582
end
583
end
584
Valid (26ms) (colibri2)
585
let function
pow
(a:t) (e:Q.t) : t
586
requires { 0. <. a.r \/ (a.r = 0. /\ 0 < e.Q.num) }
587
ensures { 0. <=. result.r }
588
ensures { 0 <= e.Q.num ->
589
RP.power result.r e.Q.den = RP.power a.r e.Q.num }
590
ensures { e.Q.num < 0 ->
591
RP.power result.r e.Q.den *. RP.power a.r (- e.Q.num) = 1. }
592
= root_spec a.r e;
593
{ r = pure { root a.r e } }
594
595
let function
size
(_a:t) : int63 = 0
596
597
clone 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
}
with
598
type t = t, function real = r, lemma irrational,
599
val of_q = of_q, val to_q = to_q, val compare = compare,
600
val compare_q = compare_q, val sign = sign, val floor = floor_,
601
val ceil = ceil_, val truncate = truncate_, val add = add, val sub = sub,
602
val mul = mul, val div = div, val neg = neg, val inv = inv,
603
val abs = abs_, val sqrt = sqrt_, val div_e = div_e, val div_t = div_t,
604
val div_f = div_f, val mod_e = mod_e, val mod_t = mod_t,
605
val mod_f = mod_f, val of_z = of_z, val pow_int = pow_int,
606
val pow = pow, val size = size
607
end