Common — library colibrilib.stda — module StdA
162
module StdA : A_intf
163
use int.Int
164
use real.RealInfix
165
use real.FromInt
166
use real.Abs as RA
167
use real.Square
168
use real.Truncate
169
use mach.int.Int63
170
use option.Option
171
use colibrilib.zarith.Q as ZQ
172
use colibrilib.q.Real as Real
173
use colibrilib.stdq.StdQ as Q
174
use colibrilib.stdq.StdQ'impl as SQ
175
use colibrilib.flint.CA as CA
176
use colibrilib.spec.Value
177
use colibrilib.spec.Test
178
Valid (32ms) (colibri2)
179
let lemma
not_zarith_not_q
(c:CA.t) (q:Q.t) : unit
180
requires { forall z:ZQ.t. ZQ.real z <> CA.real c }
181
ensures { Q.real q <> CA.real c }
182
= let z = Q.to_zarith q in assert { ZQ.real z = Q.real q }
183
Valid (35ms) (colibri2)
184
let lemma
of_zarith
(z:ZQ.t) : unit
185
ensures { exists q:Q.t. Q.real q = ZQ.real z }
186
= let q = Q.of_zarith z in assert { Q.real q = ZQ.real z }

An irrational number, and its size

  Valid (37ms) (colibri2 2) (split_vc) (depth 1)
189
type
irr
= {
ca
: CA.t;
size
: int63 }
190
invariant { forall q:Q.t. Q.real q <> CA.real ca }
191
by { ca = any CA.t ensures { forall z:ZQ.t. ZQ.real z <> CA.real result };
192
size = 0 }
193
194
type
t
=
Q
Q.t |
A
irr
195
196
function
real
(x:t) : real =
197
match x with Q q -> Q.real q | A i -> CA.real i.ca end
198
199
meta coercion function real
200
201
predicate
rational
(a:t) = Q.is_rat (real a)
202
Valid (36ms) (colibri2)
203
let ghost
not_rational
(i:irr) (q:Q.t) : unit
204
ensures { Q.real q <> CA.real i.ca }
205
= ()
206
Valid (30ms) (colibri2)
207
let ghost
not_integer
(i:irr) (z:int) : unit
208
ensures { from_int z <> CA.real i.ca }
209
= let ghost q = Q.of_bigint z in assert { Q.real q = from_int z }

A number of CA in the representation of t

  Valid (50ms) (colibri2 2) (split_vc) (depth 1)
212
let function
normalize
(a:CA.t) : t
213
ensures { value0 real (CA.real a) result }
214
= match CA.to_q a with
215
| Some q -> Q (Q.of_zarith q)
216
| None ->
217
match CA.check_is_rational a with
218
| Some False -> A { ca = a; size = CA.size a }
219
| _ -> CA.give_up a
220
end
221
end
222
Valid (37ms) (colibri2)
223
let function
to_a
(x:t) : CA.t
224
ensures { value0 CA.real (real x) result }
225
= match x with Q q -> CA.of_q (Q.to_zarith q) | A ia -> ia.ca end
226
Valid (67ms) (colibri2)
227
let
compare_int
(a b:t) : int63
228
ensures { result > 0 <-> real a >. real b }
229
ensures { result < 0 <-> real a <. real b }
230
= match a, b with
231
| Q qa, Q qb -> ZQ.compare (Q.to_zarith qa) (Q.to_zarith qb)
232
| A ia, Q qb -> CA.compare_q ia.ca (Q.to_zarith qb)
233
| Q qa, A ib -> - CA.compare_q ib.ca (Q.to_zarith qa)
234
| A ia, A ib -> CA.compare ia.ca ib.ca
235
end

A number of A is irrational: never equal to a rational

  Valid (41ms) (colibri2)
238
let
equal
(a b:t) : bool
239
ensures { decides (real a = real b) result }
240
= match a, b with
241
| Q qa, Q qb -> Q.equal qa qb
242
| A ia, Q qb -> not_rational ia qb; false
243
| Q qa, A ib -> not_rational ib qa; false
244
| A ia, A ib -> CA.compare ia.ca ib.ca = 0
245
end
246
Valid (50ms) (colibri2)
247
let
sign
(a:t) : int63
248
ensures { result > 0 <-> real a >. 0. }
249
ensures { result < 0 <-> real a <. 0. }
250
= match a with Q q -> ZQ.sign (Q.to_zarith q) | A ia -> CA.sign ia.ca end
251
Valid (42ms) (colibri2)
252
let
is_integer
(a:t) : bool
253
ensures { decides (exists z. real a = from_int z) result }
254
= match a with
255
| Q q -> Q.is_integer q
256
| A ia ->
257
if pure { exists z. CA.real ia.ca = from_int z } then begin
258
let ghost z = any int ensures { CA.real ia.ca = from_int result } in
259
not_integer ia z
260
end;
261
false
262
end
263
Valid (34ms) (colibri2)
264
let function
is_zero
(a:t) : bool
265
ensures { result <-> real a = 0. }
266
= match a with
267
| Q q -> Q.is_zero q
268
| A ia -> not_integer ia 0; false
269
end
270
Valid (25ms) (colibri2)
271
let
of_q
(q:Q.t) : t
272
ensures { value0 real (Q.real q) result }
273
= Q q
274
Valid (25ms) (colibri2)
275
let
of_bigint
(z:int) : t
276
ensures { value0 real (from_int z) result }
277
= Q (Q.of_bigint z)
278
Valid (24ms) (colibri2)
279
let
of_int
(z:int63) : t
280
ensures { value0 real (from_int z) result }
281
= Q (Q.of_int z)

The value of an integer

  Valid (37ms) (colibri2)
284
let
to_z
(a:t) : int
285
requires { exists z. real a = from_int z }
286
ensures { value0 from_int (real a) result }
287
= match a with
288
| Q q -> Q.to_z q
289
| A ia ->
290
let ghost z = any int ensures { CA.real ia.ca = from_int result } in
291
not_integer ia z;
292
absurd
293
end
294
Valid (31ms) (colibri2)
295
let
floor
(a:t) : t
296
ensures { value1 real (fun v -> from_int (Truncate.floor v)) a result }
297
= match a with Q q -> Q (Q.of_zarith (SQ.floor (Q.to_zarith q))) | A ia -> of_bigint (CA.floor ia.ca) end
298
Valid (36ms) (colibri2)
299
let
ceil
(a:t) : t
300
ensures { value1 real (fun v -> from_int (Truncate.ceil v)) a result }
301
= match a with Q q -> Q (Q.of_zarith (SQ.ceil (Q.to_zarith q))) | A ia -> of_bigint (CA.ceil ia.ca) end
302
Valid (32ms) (colibri2)
303
let
truncate
(a:t) : t
304
ensures { value1 real (fun v -> from_int (Truncate.truncate v)) a result }
305
= match a with Q q -> Q (Q.of_zarith (SQ.truncate (Q.to_zarith q))) | A ia -> of_bigint (CA.truncate ia.ca) end
306
Valid (34ms) (colibri2)
307
let function
neg
(a:t) : t
308
ensures { value1 real (fun x -> -. x) a result }
309
= match a with Q q -> Q (Q.of_zarith (ZQ.neg (Q.to_zarith q))) | A ia -> normalize (CA.neg ia.ca) end
310
Valid (27ms) (colibri2)
311
let function
abs
(a:t) : t
312
ensures { value1 real RA.abs a result }
313
= match a with Q q -> Q (Q.abs q) | A ia -> normalize (CA.abs ia.ca) end
314
Valid (36ms) (colibri2)
315
let function
add
(a b:t) : t
316
ensures { value2 real (+.) a b result }
317
= match a, b with
318
| Q qa, Q qb -> Q (Q.add qa qb)
319
| _ -> normalize (CA.add (to_a a) (to_a b))
320
end
321
Valid (42ms) (colibri2)
322
let function
sub
(a b:t) : t
323
ensures { value2 real (-.) a b result }
324
= match a, b with
325
| Q qa, Q qb -> Q (Q.sub qa qb)
326
| _ -> normalize (CA.sub (to_a a) (to_a b))
327
end
328
Valid (47ms) (colibri2)
329
let function
mul
(a b:t) : t
330
ensures { value2 real (*.) a b result }
331
= match a, b with
332
| Q qa, Q qb -> Q (Q.mul qa qb)
333
| _ -> normalize (CA.mul (to_a a) (to_a b))
334
end
335
Valid (314ms) (colibri2)
336
let function
div
(a b:t) : t
337
requires { real b <> 0. }
338
ensures { value2 real (/.) a b result }
339
= match a, b with
340
| Q qa, Q qb -> Q (Q.div qa qb)
341
| _ -> normalize (CA.div (to_a a) (to_a b))
342
end
343
Valid (56ms) (colibri2)
344
let
div_e
(a b:t) : t
345
requires { real b <> 0. }
346
ensures { value2 real (fun x y -> from_int (Real.div_e x y)) a b result }
347
= match a, b with
348
| Q qa, Q qb -> Q (Q.div_e qa qb)
349
| _ -> of_bigint (CA.div_e (to_a a) (to_a b))
350
end
351
Valid (52ms) (colibri2)
352
let
div_t
(a b:t) : t
353
requires { real b <> 0. }
354
ensures { value2 real (fun x y -> from_int (Real.div_t x y)) a b result }
355
= match a, b with
356
| Q qa, Q qb -> Q (Q.div_t qa qb)
357
| _ -> of_bigint (CA.div_t (to_a a) (to_a b))
358
end
359
Valid (47ms) (colibri2)
360
let
div_f
(a b:t) : t
361
requires { real b <> 0. }
362
ensures { value2 real (fun x y -> from_int (Real.div_f x y)) a b result }
363
= match a, b with
364
| Q qa, Q qb -> Q (Q.div_f qa qb)
365
| _ -> of_bigint (CA.div_f (to_a a) (to_a b))
366
end
367
Valid (53ms) (colibri2)
368
let function
mod_e
(a b:t) : t
369
requires { real b <> 0. }
370
ensures { value2 real Real.mod_e a b result }
371
= match a, b with
372
| Q qa, Q qb -> Q (Q.mod_e qa qb)
373
| _ -> normalize (CA.mod_e (to_a a) (to_a b))
374
end
375
Valid (56ms) (colibri2)
376
let
mod_t
(a b:t) : t
377
requires { real b <> 0. }
378
ensures { value2 real Real.mod_t a b result }
379
= match a, b with
380
| Q qa, Q qb -> Q (Q.mod_t qa qb)
381
| _ -> normalize (CA.mod_t (to_a a) (to_a b))
382
end
383
Valid (52ms) (colibri2)
384
let
mod_f
(a b:t) : t
385
requires { real b <> 0. }
386
ensures { value2 real Real.mod_f a b result }
387
= match a, b with
388
| Q qa, Q qb -> Q (Q.mod_f qa qb)
389
| _ -> normalize (CA.mod_f (to_a a) (to_a b))
390
end
391
Valid (33ms) (colibri2)
392
let function
sqrt
(a:t) : t
393
requires { 0. <=. real a }
394
ensures { value1 real Square.sqrt a result }
395
= normalize (CA.sqrt (to_a a))
396
397
use colibrilib.dv.Dv

The largest multiple of m (positive) below a, and the smallest above

  Valid (61ms) (colibri2)
401
let
round_down_to
(a:t) (m:Q.t) : Q.t
402
requires { 0. <. Q.real m }
403
ensures { dv (Q.real result) (Q.real m) }
404
ensures { Q.real result <=. real a <. Q.real result +. Q.real m }
405
= match a with
406
| Q q -> Q.of_zarith (SQ.round_down_to (Q.to_zarith q) (Q.to_zarith m))
407
| A ia ->
408
let q' = CA.floor (CA.div ia.ca (CA.of_q (Q.to_zarith m))) in
409
{proof…}
410
let ghost x = CA.real ia.ca /. Q.real m in
411
assert { from_int q' <=. x <. from_int q' +. 1. };
412
assert { from_int q' *. Q.real m <=. x *. Q.real m
413
<. (from_int q' +. 1.) *. Q.real m };
414
assert { x *. Q.real m = CA.real ia.ca };
415
{qed}
416
let r = Q.mul (Q.of_bigint q') m in
417
dv_intro (Q.real r) (Q.real m) q';
418
r
419
end
420
Valid (63ms) (colibri2 11) (split_vc) (depth 1)
421
let
round_up_to
(a:t) (m:Q.t) : Q.t
422
requires { 0. <. Q.real m }
423
ensures { dv (Q.real result) (Q.real m) }
424
ensures { Q.real result -. Q.real m <. real a <=. Q.real result }
425
= match a with
426
| Q q ->
427
let r = Q.of_zarith (SQ.round_up_to (Q.to_zarith q) (Q.to_zarith m)) in
428
let ghost k = any int ensures { Q.real r = from_int result *. Q.real m } in
429
dv_intro (Q.real r) (Q.real m) k;
430
r
431
| A ia ->
432
let q' = CA.ceil (CA.div ia.ca (CA.of_q (Q.to_zarith m))) in
433
{proof…}
434
let ghost x = CA.real ia.ca /. Q.real m in
435
assert { from_int q' -. 1. <. x <=. from_int q' };
436
assert { (from_int q' -. 1.) *. Q.real m <. x *. Q.real m
437
<=. from_int q' *. Q.real m };
438
assert { x *. Q.real m = CA.real ia.ca };
439
{qed}
440
let r = Q.mul (Q.of_bigint q') m in
441
dv_intro (Q.real r) (Q.real m) q';
442
r
443
end
444
445
use real.PowerInt as RP
446
use colibrilib.stdq.PowRound as SP

The power a^n (Std.A.pow)

  Valid (44ms) (colibri2)
449
let
pow
(a:t) (n:int63) : t
450
requires { 0 <= n \/ real a <> 0. }
451
requires { -0x4000000000000000 < n }
452
ensures { value1 real (fun x -> if 0 <= n then RP.power x n else 1. /. RP.power x (- n)) a result }
453
= match a with
454
| Q q -> Q (Q.of_zarith (SP.pow (Q.to_zarith q) n))
455
| A ia -> normalize (CA.pow_int ia.ca n)
456
end
457
Valid (31ms) (colibri2 6) (split_vc) (depth 1)
458
let ghost
div_bounds
(b x c p:real) : unit
459
requires { 0. <. p }
460
ensures { b <=. p *. x -> b /. p <=. x }
461
ensures { b <. p *. x -> b /. p <. x }
462
ensures { p *. x <=. c -> x <=. c /. p }
463
ensures { p *. x <. c -> x <. c /. p }
464
= assert { x = (p *. x) /. p };
465
assert { p *. x <=. c -> (p *. x) /. p <=. c /. p }
466
467
use colibrilib.zarith.Zbit as Zbit

The largest power of a rational computed in Zarith by positive_pow, in bits (numerator and denominator): 2^20

471
let constant
pow_bits_limit
: int = 0x100000
472
Valid (55ms) (colibri2)
473
let rec lemma
power_pos
(x:real) (m:int) : unit
474
requires { 0. <. x /\ 0 <= m }
475
ensures { 0. <. RP.power x m }
476
variant { m }
477
= if m > 0 then power_pos x (m - 1)
478
Valid (52ms) (colibri2)
479
let rec lemma
power_zero
(m:int) : unit
480
requires { 0 < m }
481
ensures { RP.power 0. m = 0. }
482
variant { m }
483
= if m > 1 then power_zero (m - 1)

a^e, the non negative root (Std.A.positive_pow)

  Valid (1.9s) (colibri2 32) (cvc5 2) (split_vc 5) (depth 2)
486
let
positive_pow
(a:t) (e:Q.t) : t
487
requires { 0. <. real a \/ (real a = 0. /\ 0. <. Q.real e) }
488
ensures { 0. <=. real result }
489
ensures { 0 <= (Q.num e) ->
490
RP.power (real result) (Q.den e) = RP.power (real a) (Q.num e) }
491
ensures { (Q.num e) < 0 ->
492
RP.power (real result) (Q.den e) *. RP.power (real a) (- (Q.num e)) = 1. }
493
ensures { exists n d:int. 0 < d /\ Q.real e = from_int n /. from_int d /\
494
(0 <= n -> RP.power (real result) d = RP.power (real a) n) /\
495
(n < 0 -> RP.power (real result) d *. RP.power (real a) (- n) = 1.) }
496
= {proof…}
497
Q.num_den e;
498
assert { 0. <. Q.real e -> 0 < (Q.num e)
499
by Q.real e = from_int (Q.num e) /. from_int (Q.den e)
500
so 0. <. from_int (Q.den e) };
501
{qed}
502
match a with
503
| Q q ->
507
(* 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 *)
508
if Q.is_integer e then begin
509
let n = Q.to_z e in
510
let z = Q.to_zarith q in
511
let bits = Zbit.numbits z.ZQ.num + Zbit.numbits z.ZQ.den in
512
let an = if n >= 0 then n else - n in
513
if -0x3fffffffffffffff <= n && n <= 0x3fffffffffffffff
514
&& an * bits <= pow_bits_limit then begin
515
let n63 = Int63.of_int n in
516
{proof…}
517
let ghost k = Q.num e in
518
let ghost d = Q.den e in
519
assert { from_int k = from_int n *. from_int d
520
by from_int k /. from_int d = from_int n
521
so from_int k = (from_int k /. from_int d) *. from_int d };
522
assert { k = n * d };
523
assert { real a <> 0. \/ 0 < n };
524
{qed}
525
let r = pow a n63 in
526
{proof…}
527
if n >= 0 then begin
528
assert { real r = RP.power (real a) n };
529
assert { 0. <=. real r by 0. <. real a \/ (real a = 0. /\ 0 < n) };
530
assert { RP.power (real r) d = RP.power (real a) (n * d) };
531
assert { RP.power (real r) d = RP.power (real a) k }
532
end else begin
533
let ghost p = RP.power (real a) (- n) in
534
assert { 0. <. real a };
535
assert { 0. <. p };
536
assert { real r = 1. /. p };
537
assert { 0. <=. real r };
538
assert { RP.power (real r) d *. RP.power p d = RP.power (real r *. p) d };
539
assert { real r *. p = 1. };
540
assert { RP.power p d = RP.power (real a) ((- n) * d) };
541
assert { (- n) * d = - k };
542
assert { RP.power (real r) d *. RP.power (real a) (- k) = 1. }
543
end;
544
{qed}
545
r
546
end else normalize (CA.pow (to_a a) (Q.to_zarith e))
547
end else normalize (CA.pow (to_a a) (Q.to_zarith e))
548
| A _ -> normalize (CA.pow (to_a a) (Q.to_zarith e))
549
end

A rational below a, at most 1/prec below (Std.A.floor_q)

  Valid (340ms) (colibri2)
552
let
floor_q
(prec:int) (a:t) : Q.t
553
requires { 0 < prec }
554
ensures { Q.real result <=. real a <. Q.real result +. 1. /. from_int prec }
555
= match a with
556
| Q q -> q
557
| A ia ->
558
let k = CA.floor (CA.mul (CA.of_z prec) ia.ca) in
559
{proof…}
560
let ghost p = from_int prec in
561
assert { from_int k <=. p *. CA.real ia.ca <. from_int k +. 1. };
562
div_bounds (from_int k) (CA.real ia.ca) (from_int k +. 1.) p;
563
assert { (from_int k +. 1.) /. p = from_int k /. p +. 1. /. p };
564
{qed}
565
Q.of_zarith (ZQ.make k prec)
566
end

A rational above a, at most 1/prec above (Std.A.ceil_q)

  Valid (328ms) (colibri2)
569
let
ceil_q
(prec:int) (a:t) : Q.t
570
requires { 0 < prec }
571
ensures { Q.real result -. 1. /. from_int prec <. real a <=. Q.real result }
572
= match a with
573
| Q q -> q
574
| A ia ->
575
let k = CA.ceil (CA.mul (CA.of_z prec) ia.ca) in
576
{proof…}
577
let ghost p = from_int prec in
578
assert { from_int k -. 1. <. p *. CA.real ia.ca <=. from_int k };
579
div_bounds (from_int k -. 1.) (CA.real ia.ca) (from_int k) p;
580
assert { (from_int k -. 1.) /. p = from_int k /. p -. 1. /. p };
581
{qed}
582
Q.of_zarith (ZQ.make k prec)
583
end

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)
588
let
round_down_to_small
(bigq: Q.t -> bool) (max_size_bit prec:int) (x:t) : t
589
requires { 0 < prec }
590
ensures { match result with Q _ -> true | A _ -> false end }
591
ensures { real result <=. real x }
592
= match x with
593
| Q q -> Q (Q.of_zarith (SP.round_down_to_small max_size_bit (Q.to_zarith q)))
594
| A _ ->
595
let f = floor_q prec x in
596
if bigq f then Q (Q.of_zarith (SP.round_down_to_small max_size_bit (Q.to_zarith f))) else Q f
597
end
598
Valid (338ms) (colibri2)
599
let
round_up_to_small
(bigq: Q.t -> bool) (max_size_bit prec:int) (x:t) : t
600
requires { 0 < prec }
601
ensures { match result with Q _ -> true | A _ -> false end }
602
ensures { real x <=. real result }
603
= match x with
604
| Q q -> Q (Q.of_zarith (SP.round_up_to_small max_size_bit (Q.to_zarith q)))
605
| A _ ->
606
let c = ceil_q prec x in
607
if bigq c then Q (Q.of_zarith (SP.round_up_to_small max_size_bit (Q.to_zarith c))) else Q c
608
end

The two cases of view

611
type
view
=
Rat
Q.t |
Irr
612
Valid (309ms) (colibri2)
613
let
view
(a:t) : view
614
ensures { match result with
615
| Rat q -> real a = Q.real q
616
| Irr -> forall q:Q.t. real a <> Q.real q
617
end }
618
= match a with Q q -> Rat q | A _ -> Irr end

The functions of A_intf that return an integer or a comparison

  Valid (283ms) (colibri2)
621
let
floor_z
(a:t) : int
622
ensures { value_is (Truncate.floor (real a)) result }
623
= match a with Q q -> Q.floor_z q | A ia -> CA.floor ia.ca end
624
Valid (44ms) (colibri2)
625
let
ceil_z
(a:t) : int
626
ensures { value_is (Truncate.ceil (real a)) result }
627
= match a with Q q -> Q.ceil_z q | A ia -> CA.ceil ia.ca end
628
Valid (44ms) (colibri2)
629
let
truncate_z
(a:t) : int
630
ensures { value_is (Truncate.truncate (real a)) result }
631
= match a with Q q -> Q.truncate_z q | A ia -> CA.truncate ia.ca end
632
Valid (47ms) (colibri2)
633
let
le
(a b:t) : bool
634
ensures { decides (real a <=. real b) result }
635
= compare_int a b <= 0
636
Valid (50ms) (colibri2)
637
let
lt
(a b:t) : bool
638
ensures { decides (real a <. real b) result }
639
= compare_int a b < 0
640
641
use colibrilib.q.Ord as Ord
642
Valid (49ms) (colibri2)
643
let
compare
(a b:t) : Ord.t
644
ensures { match result with
645
| Ord.Eq -> real a = real b
646
| Ord.Lt -> real a <. real b
647
| Ord.Gt -> real b <. real a
648
end }
649
= let c = compare_int a b in
650
if c = 0 then Ord.Eq else if c < 0 then Ord.Lt else Ord.Gt
651
end