Common — library colibrilib.stdq — module StdQ
157
module StdQ : colibrilib.q.Q_intf
158
use int.Int
159
use int.Abs as IA
160
use real.RealInfix
161
use real.FromInt
162
use real.Truncate
163
use real.Abs as RA
164
use mach.int.Int63
165
use colibrilib.zarith.Z as Z
166
use colibrilib.zarith.Q as Q
167
use colibrilib.q.Real as Real
168
use number.Gcd as Gcd
169
use int.EuclideanDivision as E
170
171
type
t
= Q.t
172
173
function
real
(q:t) : real = Q.real q
174
175
predicate
is_rat
(r:real) = exists q:t. real q = r

The operations of q.Q_intf that Zarith provides: StdQ has all of them, it is the instance of the interface

  Valid (30ms) (colibri2)
179
let
equal
(a b:Q.t) : bool ensures { result <-> Q.real a = Q.real b } = Q.equal a b Valid (27ms) (colibri2)
180
let
le
(a b:Q.t) : bool ensures { result <-> Q.real a <=. Q.real b } = Q.leq a b Valid (24ms) (colibri2)
181
let
lt
(a b:Q.t) : bool ensures { result <-> Q.real a <. Q.real b } = Q.lt a b Valid (26ms) (colibri2)
182
let
abs
(a:Q.t) : Q.t ensures { Q.real result = RA.abs (Q.real a) } = Q.abs a Valid (24ms) (colibri2)
183
let function
add
(a b:Q.t) : Q.t ensures { Q.real result = Q.real a +. Q.real b } = Q.add a b Valid (23ms) (colibri2)
184
let function
sub
(a b:Q.t) : Q.t ensures { Q.real result = Q.real a -. Q.real b } = Q.sub a b Valid (28ms) (colibri2)
185
let function
mul
(a b:Q.t) : Q.t ensures { Q.real result = Q.real a *. Q.real b } = Q.mul a b Valid (25ms) (colibri2)
186
let function
div
(a b:Q.t) : Q.t requires { Q.real b <> 0. } ensures { Q.real result = Q.real a /. Q.real b } = Q.div a b Valid (32ms) (colibri2)
187
let
of_int
(n:int63) : Q.t ensures { Q.real result = from_int n } = Q.of_int n Valid (28ms) (colibri2)
188
let
of_bigint
(n:int) : Q.t ensures { Q.real result = from_int n } = Q.of_bigint n

q = n / d with n between k * d and k * d + d (excluded)

  Valid (124ms) (cvc4)
191
let ghost
frac_bounds
(n d k:int) : unit
192
requires { 0 < d }
193
requires { k * d <= n < k * d + d }
194
ensures { from_int k <=. from_int n /. from_int d <. from_int k +. 1. }
195
= {proof…} let rd = from_int d in
196
assert { 0. <. rd };
197
assert { from_int (k * d) <=. from_int n <. from_int (k * d + d) };
198
assert { from_int k *. rd <=. from_int n <. (from_int k +. 1.) *. rd };
199
assert { from_int n /. rd *. rd = from_int n } {qed}
200
Valid (4.2s) (colibri2 7) (split_vc 2) (depth 2)
201
let function
is_integer
(q:Q.t) : bool
202
ensures { result <-> q.Q.den = 1 }
203
ensures { result <-> exists z. Q.real q = from_int z }
204
= {proof…} if pure { exists z. Q.real q = from_int z } then begin
205
let ghost z = any int ensures { Q.real q = from_int result } in
206
assert { from_int q.Q.num = from_int z *. from_int q.Q.den
207
by from_int q.Q.num /. from_int q.Q.den *. from_int q.Q.den = from_int q.Q.num };
208
assert { q.Q.num = z * q.Q.den };
209
assert { Gcd.gcd q.Q.num q.Q.den = q.Q.den
210
by Gcd.gcd (z * q.Q.den) (0 * z + q.Q.den) = Gcd.gcd (z * q.Q.den) q.Q.den };
211
end; {qed}
212
Z.is_one q.Q.den
213
Valid (1.0s) (colibri2)
214
let function
floor
(x:Q.t) : Q.t
215
ensures { result.Q.den = 1 }
216
ensures { Q.real result = from_int (floor (Q.real x)) }
217
= if is_integer x then x
218
else begin
219
let r = Z.fdiv x.Q.num x.Q.den in
220
frac_bounds x.Q.num x.Q.den r;
221
Q.of_bigint r
222
end
223
Valid (878ms) (cvc4)
224
let ghost
cdiv_bounds
(a b:int) : unit
225
requires { 0 < b }
226
ensures { let r = - E.div (- a) b in r * b - b < a <= r * b }
227
= assert { E.div (- a) b * b + E.mod (- a) b = - a };
228
assert { 0 <= E.mod (- a) b < b }
229
Valid (1.5s) (colibri2 12) (split_vc 2) (depth 2)
230
let function
ceil
(x:Q.t) : Q.t
231
ensures { result.Q.den = 1 }
232
ensures { Q.real result = from_int (ceil (Q.real x)) }
233
= if is_integer x then x
234
else begin
235
let r = Z.cdiv x.Q.num x.Q.den in
236
cdiv_bounds x.Q.num x.Q.den;
237
assert { (r - 1) * x.Q.den < x.Q.num <= r * x.Q.den };
238
if pure { x.Q.num = r * x.Q.den } then begin
239
assert { Gcd.gcd x.Q.num x.Q.den = Gcd.gcd x.Q.den x.Q.num };
240
assert { Gcd.gcd x.Q.den x.Q.num = Gcd.gcd x.Q.den (x.Q.num - r * x.Q.den) };
241
assert { Gcd.gcd x.Q.den 0 = x.Q.den };
242
absurd
243
end;
244
frac_bounds x.Q.num x.Q.den (r - 1);
245
Q.of_bigint r
246
end
247
Valid (452ms) (colibri2)
248
let function
truncate
(d:Q.t) : Q.t
249
ensures { result.Q.den = 1 }
250
ensures { Q.real result = from_int (truncate (Q.real d)) }
251
= if is_integer d then d
252
else if Q.sign d > 0 then floor d
253
else ceil d
254
Valid (52ms) (colibri2)
255
let function
div_e
(a b:Q.t) : Q.t
256
requires { Q.real b <> 0. }
257
ensures { Q.real result = from_int (Real.div_e a b) }
258
= let s = Q.sign b in
259
let d = Q.div a b in
260
if s > 0 then floor d else ceil d
261
Valid (37ms) (colibri2)
262
let function
div_t
(a b:Q.t) : Q.t
263
requires { Q.real b <> 0. }
264
ensures { Q.real result = from_int (Real.div_t a b) }
265
= truncate (Q.div a b)
266
Valid (29ms) (colibri2)
267
let function
div_f
(a b:Q.t) : Q.t
268
requires { Q.real b <> 0. }
269
ensures { Q.real result = from_int (Real.div_f a b) }
270
= floor (Q.div a b)
271
Valid (52ms) (colibri2)
272
let function
mod_e
(a b:Q.t) : Q.t
273
requires { Q.real b <> 0. }
274
ensures { Q.real result = Real.mod_e a b }
275
= Q.sub a (Q.mul (div_e a b) b)
276
Valid (28ms) (colibri2)
277
let function
mod_t
(a b:Q.t) : Q.t
278
requires { Q.real b <> 0. }
279
ensures { Q.real result = Real.mod_t a b }
280
= Q.sub a (Q.mul (div_t a b) b)
281
Valid (33ms) (colibri2)
282
let function
mod_f
(a b:Q.t) : Q.t
283
requires { Q.real b <> 0. }
284
ensures { Q.real result = Real.mod_f a b }
285
= Q.sub a (Q.mul (div_f a b) b)
286
Valid (52ms) (colibri2)
287
let function
is_zero
(c:Q.t) : bool
288
ensures { result <-> Q.real c = 0. }
289
= Q.sign c = 0

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

  Valid (75ms) (colibri2)
292
let
round_down_to
(a m:Q.t) : Q.t
293
requires { 0. <. Q.real m }
294
ensures { exists k. Q.real result = from_int k *. Q.real m }
295
ensures { Q.real result <=. Q.real a <. Q.real result +. Q.real m }
296
= let q' = floor (Q.div a m) in
297
Q.mul q' m
298
Valid (63ms) (colibri2)
299
let
round_up_to
(a m:Q.t) : Q.t
300
requires { 0. <. Q.real m }
301
ensures { exists k. Q.real result = from_int k *. Q.real m }
302
ensures { Q.real result -. Q.real m <. Q.real a <=. Q.real result }
303
= let q' = ceil (Q.div a m) in
304
Q.mul q' m

The functions of q.Q_intf that return an integer

  Valid (37ms) (colibri2)
307
let
to_bigint
(q:Q.t) : int
308
requires { q.Q.den = 1 }
309
ensures { from_int result = Q.real q }
310
= q.Q.num
311
Valid (32ms) (colibri2)
312
let
floor_z
(x:Q.t) : int
313
ensures { result = Truncate.floor (Q.real x) }
314
= to_bigint (floor x)
315
Valid (38ms) (colibri2)
316
let
ceil_z
(x:Q.t) : int
317
ensures { result = Truncate.ceil (Q.real x) }
318
= to_bigint (ceil x)
319
Valid (23ms) (colibri2)
320
let
truncate_z
(x:Q.t) : int
321
ensures { result = Truncate.truncate (Q.real x) }
322
= to_bigint (truncate x)
323
324
use colibrilib.q.Ord as Ord
325
Valid (52ms) (colibri2)
326
let
compare
(a b:Q.t) : Ord.t
327
ensures { match result with
328
| Ord.Eq -> Q.real a = Q.real b
329
| Ord.Lt -> Q.real a <. Q.real b
330
| Ord.Gt -> Q.real b <. Q.real a
331
end }
332
= let c = Q.compare a b in
333
if c = 0 then Ord.Eq else if c < 0 then Ord.Lt else Ord.Gt
334
335
use number.Divisibility as D
336
use number.Coprime as C
337
use colibrilib.dv.Dv

n1/d1 = k * n2/d2 in integers

  Valid (44ms) (colibri2)
340
let ghost
cross_mul
(n1 d1 n2 d2 k:int) : unit
341
requires { 0 < d1 /\ 0 < d2 }
342
ensures { from_int n1 /. from_int d1 = from_int k *. (from_int n2 /. from_int d2)
343
<-> n1 * d2 = k * n2 * d1 }
344
= {proof…} let x1 = from_int n1 in let y1 = from_int d1 in
345
let x2 = from_int n2 in let y2 = from_int d2 in let rk = from_int k in
346
assert { y1 <> 0. /\ y2 <> 0. };
347
assert { x1 /. y1 = rk *. (x2 /. y2) <-> x1 *. y2 = rk *. x2 *. y1
348
by x1 /. y1 *. (y1 *. y2) = x1 *. y2
349
/\ rk *. (x2 /. y2) *. (y1 *. y2) = rk *. x2 *. y1 };
350
assert { from_int (n1 * d2) = x1 *. y2 };
351
assert { from_int (k * n2 * d1) = rk *. x2 *. y1 } {qed}

For fractions in lowest terms, b divides a iff the numerator of b divides that of a and the denominator of a that of b

  Valid (1.9s) (colibri2 15) (split_vc) (depth 1)
355
let ghost
dv_frac
(a b:Q.t) : unit
356
ensures { dv (Q.real a) (Q.real b)
357
<-> D.divides b.Q.num a.Q.num /\ D.divides a.Q.den b.Q.den }
358
= {proof…} let n1 = a.Q.num in let d1 = a.Q.den in
359
let n2 = b.Q.num in let d2 = b.Q.den in
360
if pure { dv (Q.real a) (Q.real b) } then begin
361
let k = quot (Q.real a) (Q.real b) in
362
cross_mul n1 d1 n2 d2 k;
363
assert { n1 * d2 = (k * n2) * d1 };
364
assert { D.divides d1 (n1 * d2) };
365
assert { C.coprime d1 n1 by Gcd.gcd d1 n1 = Gcd.gcd n1 d1 };
366
assert { D.divides d1 d2 };
367
assert { D.divides n2 (d2 * n1) by d2 * n1 = (k * d1) * n2 };
368
assert { C.coprime n2 d2 };
369
assert { D.divides n2 n1 }
370
end;
371
if pure { D.divides n2 n1 /\ D.divides d1 d2 } then begin
372
let x = any int ensures { n1 = result * n2 } in
373
let y = any int ensures { d2 = result * d1 } in
374
cross_mul n1 d1 n2 d2 (x * y);
375
assert { n1 * d2 = (x * y) * n2 * d1 };
376
dv_intro (Q.real a) (Q.real b) (x * y)
377
end {qed}

a is an integer multiple of b, and the multiple (Std.Q.divisible)

  Valid (52ms) (colibri2)
380
let
divisible
(a b:Q.t) : (r:bool, ghost d:int)
381
ensures { r <-> dv (Q.real a) (Q.real b) }
382
ensures { r -> Q.real a = from_int d *. Q.real b }
383
= dv_frac a b;
384
let r = Z.divisible a.Q.num b.Q.num && Z.divisible b.Q.den a.Q.den in
385
(r, if r then quot (Q.real a) (Q.real b) else 0)

The multiple: a = result * b (Std.Q.divexact)

  Valid (337ms) (colibri2)
388
let
divexact
(a b:Q.t) : int
389
requires { Q.real b <> 0. }
390
requires { dv (Q.real a) (Q.real b) }
391
ensures { Q.real a = from_int result *. Q.real b }
392
= dv_frac a b;
393
assert { b.Q.num <> 0 };
394
let x = Z.divexact a.Q.num b.Q.num in
395
let y = Z.divexact b.Q.den a.Q.den in
396
cross_mul a.Q.num a.Q.den b.Q.num b.Q.den (x * y);
397
assert { a.Q.num * b.Q.den = (x * y) * b.Q.num * a.Q.den };
398
x * y

The value of an integer

  Valid (32ms) (colibri2)
401
let
to_z
(a:Q.t) : int
402
requires { exists z. Q.real a = from_int z }
403
ensures { from_int result = Q.real a }
404
= let _ = is_integer a in to_bigint a

Bezout on the rationals (Std.Q.gcdext): g = u * a + v * b with g the non negative generator of the group generated by a and b

  Valid (986ms) (colibri2)
408
let
gcdext3
(a b:Q.t) : (g:Q.t, u:int, v:int)
409
ensures { 0. <=. Q.real g }
410
ensures { dv (Q.real a) (Q.real g) }
411
ensures { dv (Q.real b) (Q.real g) }
412
ensures { Q.real g = from_int u *. Q.real a +. from_int v *. Q.real b }
413
= let x = a.Q.num * b.Q.den in
414
let y = b.Q.num * a.Q.den in
415
let (g, u, v) = Z.gcdext x y in
416
let dd = a.Q.den * b.Q.den in
417
let r = Q.make g dd in
418
{proof…}
419
let ghost rd = from_int dd in
420
assert { 0. <. rd };
421
assert { Q.real a = from_int x /. rd
422
by from_int x /. rd = (from_int a.Q.num *. from_int b.Q.den)
423
/. (from_int a.Q.den *. from_int b.Q.den) };
424
assert { Q.real b = from_int y /. rd
425
by from_int y /. rd = (from_int b.Q.num *. from_int a.Q.den)
426
/. (from_int a.Q.den *. from_int b.Q.den) };
427
assert { 0 <= g };
428
assert { Q.real r = from_int g /. rd };
429
assert { from_int g = from_int u *. from_int x +. from_int v *. from_int y };
430
assert { Q.real r = from_int u *. Q.real a +. from_int v *. Q.real b };
431
assert { D.divides g x /\ D.divides g y };
432
let ghost kx = any int ensures { x = result * g } in
433
let ghost ky = any int ensures { y = result * g } in
434
assert { Q.real a = from_int kx *. Q.real r
435
by from_int x = from_int kx *. from_int g };
436
assert { Q.real b = from_int ky *. Q.real r
437
by from_int y = from_int ky *. from_int g };
438
dv_intro (Q.real a) (Q.real r) kx;
439
dv_intro (Q.real b) (Q.real r) ky;
440
{qed}
441
(r, u, v)
442
443
use ZFacts as ZF

The value of gcd a b

446
function
gcd_q
(a b:Q.t) : real =
447
from_int (Gcd.gcd a.Q.num b.Q.num) /. from_int (Z.lcm a.Q.den b.Q.den)

a = (y * n1) / l and b = (x * n2) / l with l = lcm d1 d2

  Valid (41ms) (colibri2)
450
let ghost
common_den
(a b:Q.t) (g x y:int) : unit
451
requires { a.Q.den = g * x /\ b.Q.den = g * y /\ 0 < g /\ 0 < x /\ 0 < y }
452
ensures { Q.real a = from_int (y * a.Q.num) /. from_int (g * x * y) }
453
ensures { Q.real b = from_int (x * b.Q.num) /. from_int (g * x * y) }
454
= {proof…} let ry = from_int y in let rx = from_int x in
455
assert { 0. <. ry /\ 0. <. rx };
456
assert { from_int (y * a.Q.num) /. from_int (g * x * y)
457
= (ry *. from_int a.Q.num) /. (ry *. from_int a.Q.den) };
458
assert { from_int (x * b.Q.num) /. from_int (g * x * y)
459
= (rx *. from_int b.Q.num) /. (rx *. from_int b.Q.den) } {qed}

The greatest common divisor (Std.Q.gcd): the non negative generator of the group generated by a and b

  Valid (357ms) (colibri2 50) (split_vc) (depth 1)
463
let
gcd
(a b:Q.t) : Q.t
464
ensures { Q.real result = gcd_q a b }
465
ensures { 0. <=. Q.real result }
466
ensures { dv (Q.real a) (Q.real result) }
467
ensures { dv (Q.real b) (Q.real result) }
468
ensures { forall r. dv (Q.real a) r -> dv (Q.real b) r -> dv (Q.real result) r }
469
= let n1 = a.Q.num in let d1 = a.Q.den in
470
let n2 = b.Q.num in let d2 = b.Q.den in
471
let gg = Z.gcd n1 n2 in
472
let l = Z.lcm d1 d2 in
473
{proof…}
474
let ghost (x, y) = ZF.lcm_decomp d1 d2 in
475
let ghost g = Gcd.gcd d1 d2 in
476
assert { l = d1 * y /\ l = d2 * x /\ 0 < l };
477
ZF.coprime_div n1 d1 gg;
478
ZF.coprime_div n2 d2 gg;
479
ZF.coprime_sym gg d2;
480
ZF.coprime_div d2 gg y;
481
ZF.coprime_sym y gg;
482
ZF.coprime_mul d1 y gg;
483
assert { C.coprime gg l };
484
{qed}
485
let r = Q.make_exact gg l in
486
{proof…}
487
ZF.coprime_sym n2 d2;
488
ZF.coprime_div d2 n2 y;
489
ZF.coprime_sym n1 d1;
490
ZF.coprime_div d1 n1 x;
491
ZF.coprime_sym x n1;
492
ZF.coprime_sym x y;
493
ZF.coprime_sym y n2;
494
ZF.coprime_mul n2 x y;
495
ZF.gcd_cancel n1 (n2 * x) y;
496
assert { Gcd.gcd n1 (x * n2) = gg };
497
assert { Gcd.gcd (y * n1) (x * n2) = gg };
498
let ghost (u, v) = ZF.bezout (y * n1) (x * n2) in
499
common_den a b g x y;
500
let ghost rl = from_int l in
501
assert { Q.real r = from_int gg /. rl };
502
assert { Q.real r = from_int u *. Q.real a +. from_int v *. Q.real b
503
by from_int gg = from_int u *. from_int (y * n1) +. from_int v *. from_int (x * n2) };
504
assert { D.divides gg n1 by gg = Gcd.gcd n1 n2 };
505
let ghost k1 = any int ensures { n1 = result * gg } in
506
assert { D.divides gg n2 by gg = Gcd.gcd n1 n2 };
507
let ghost k2 = any int ensures { n2 = result * gg } in
508
assert { Q.real a = from_int (y * k1) *. Q.real r
509
by from_int (y * n1) = from_int (y * k1) *. from_int gg };
510
assert { Q.real b = from_int (x * k2) *. Q.real r
511
by from_int (x * n2) = from_int (x * k2) *. from_int gg };
512
dv_intro (Q.real a) (Q.real r) (y * k1);
513
dv_intro (Q.real b) (Q.real r) (x * k2);
514
let lemma common (r':real)
515
requires { dv (Q.real a) r' }
516
requires { dv (Q.real b) r' }
517
ensures { dv (Q.real r) r' }
518
= let ka = quot (Q.real a) r' in
519
let kb = quot (Q.real b) r' in
520
assert { Q.real r = from_int (u * ka + v * kb) *. r'
521
by Q.real r = from_int u *. (from_int ka *. r') +. from_int v *. (from_int kb *. r') };
522
dv_intro (Q.real r) r' (u * ka + v * kb) in
523
assert { 0. <=. Q.real r by 0 <= gg /\ 0. <. rl };
524
{qed}
525
r

The least common multiple (Std.Q.lcm): the non negative generator of the intersection of the groups generated by a and by b

  Valid (1.2s) (colibri2 63) (cvc5 3) (split_vc) (depth 1)
529
let
lcm
(a b:Q.t) : Q.t
530
ensures { 0. <=. Q.real result }
531
ensures { dv (Q.real result) (Q.real a) }
532
ensures { dv (Q.real result) (Q.real b) }
533
ensures { forall r. dv r (Q.real a) -> dv r (Q.real b) -> dv r (Q.real result) }
534
= let n1 = a.Q.num in let d1 = a.Q.den in
535
let n2 = b.Q.num in let d2 = b.Q.den in
536
let m = Z.lcm n1 n2 in
537
let h = Z.gcd d1 d2 in
538
{proof…}
539
let ghost (x, y) = ZF.lcm_decomp d1 d2 in
540
ZF.lcm_gcd n1 n2;
541
ZF.lcm_multiple n1 n2;
542
assert { 0 < h by h <> 0 };
543
if n1 = 0 || n2 = 0 then begin
544
assert { m = 0 };
545
assert { n1 = 0 -> d1 = 1 by Gcd.gcd 0 d1 = d1 };
546
assert { n2 = 0 -> d2 = 1 by Gcd.gcd 0 d2 = d2 };
547
assert { h = 1 by D.divides h 1 }
548
end else begin
549
ZF.coprime_sym n1 d1;
550
ZF.coprime_div d1 n1 h;
551
ZF.coprime_sym n2 d2;
552
ZF.coprime_div d2 n2 h;
553
ZF.coprime_mul n1 n2 h;
554
ZF.coprime_sym h (n1 * n2);
555
let ghost gg = Gcd.gcd n1 n2 in
556
assert { IA.abs (n1 * n2) = m * gg };
557
if n1 * n2 < 0 then begin
558
assert { IA.abs (n1 * n2) = - (n1 * n2) };
559
assert { n1 * n2 = m * (- gg) }
560
end else assert { n1 * n2 = m * gg };
561
assert { D.divides m (n1 * n2) };
562
ZF.coprime_div (n1 * n2) h m
563
end;
564
assert { C.coprime m h };
565
{qed}
566
let r = Q.make_exact m h in
567
{proof…}
568
let ghost rh = from_int h in
569
assert { 0. <. rh };
570
let ghost k1 = any int ensures { m = result * n1 } in
571
let ghost k2 = any int ensures { m = result * n2 } in
572
assert { Q.real r = from_int (k1 * x) *. Q.real a
573
by from_int m /. rh = (from_int (k1 * x) *. from_int n1) /. (from_int x *. rh) };
574
assert { Q.real r = from_int (k2 * y) *. Q.real b
575
by from_int m /. rh = (from_int (k2 * y) *. from_int n2) /. (from_int y *. rh) };
576
dv_intro (Q.real r) (Q.real a) (k1 * x);
577
dv_intro (Q.real r) (Q.real b) (k2 * y);
578
common_den a b h x y;
579
let lemma common (r':real)
580
requires { dv r' (Q.real a) }
581
requires { dv r' (Q.real b) }
582
ensures { dv r' (Q.real r) }
583
= let ka = quot r' (Q.real a) in
584
let kb = quot r' (Q.real b) in
585
if n1 = 0 || n2 = 0 then begin
586
assert { r' = 0. };
587
dv_intro r' (Q.real r) 0
588
end else begin
589
let aa = y * n1 in let bb = x * n2 in
590
let ll = h * x * y in
591
assert { from_int (ka * aa) = from_int (kb * bb)
592
by r' = from_int ka *. (from_int aa /. from_int ll)
593
/\ r' = from_int kb *. (from_int bb /. from_int ll)
594
/\ 0. <. from_int ll };
595
assert { ka * aa = kb * bb };
596
ZF.lcm_least aa bb (ka * aa);
597
let q = any int ensures { ka * aa = result * Z.lcm aa bb } in
598
(* gcd aa bb = gcd n1 n2 *)
599
ZF.coprime_sym n2 d2;
600
ZF.coprime_div d2 n2 y;
601
ZF.coprime_sym n1 d1;
602
ZF.coprime_div d1 n1 x;
603
ZF.coprime_sym x n1;
604
ZF.coprime_sym x y;
605
ZF.coprime_sym y n2;
606
ZF.coprime_mul n2 x y;
607
ZF.gcd_cancel n1 (n2 * x) y;
608
assert { Gcd.gcd n1 (x * n2) = Gcd.gcd n1 n2 };
609
assert { Gcd.gcd aa bb = Gcd.gcd n1 n2 };
610
ZF.lcm_gcd aa bb;
611
let gg = Gcd.gcd n1 n2 in
612
assert { 0 < gg by gg <> 0 };
613
assert { IA.abs (aa * bb) = (x * y) * IA.abs (n1 * n2) };
614
assert { Z.lcm aa bb * gg = (x * y * m) * gg };
615
assert { Z.lcm aa bb = x * y * m };
616
assert { r' = from_int q *. Q.real r
617
by r' = from_int (ka * aa) /. from_int ll
618
/\ from_int (ka * aa) = from_int q *. (from_int (x * y) *. from_int m)
619
/\ from_int ll = from_int (x * y) *. rh };
620
dv_intro r' (Q.real r) q
621
end in
622
assert { 0. <=. Q.real r by 0 <= m };
623
{qed}
624
r
625
Valid (41ms) (colibri2)
626
let
gcdext
(a b:Q.t) : (g:Q.t, u:int, ghost v:int)
627
ensures { 0. <=. Q.real g }
628
ensures { dv (Q.real a) (Q.real g) }
629
ensures { dv (Q.real b) (Q.real g) }
630
ensures { Q.real g = from_int u *. Q.real a +. from_int v *. Q.real b }
631
= let (g, u, v) = gcdext3 a b in (g, u, v)

The fraction in lowest terms

635
function
num
(q:t) : int = q.Q.num
636
function
den
(q:t) : int = q.Q.den
637
Valid (45ms) (colibri2)
638
let ghost
num_den
(q:t) : unit
639
ensures { 0 < den q }
640
ensures { real q = from_int (num q) /. from_int (den q) }
641
= ()
642
Valid (32ms) (colibri2)
643
let
to_zarith
(q:t) : Q.t
644
ensures { Q.real result = real q }
645
ensures { result.Q.num = num q /\ result.Q.den = den q }
646
= q
647
Valid (39ms) (colibri2)
648
let
of_zarith
(q:Q.t) : t
649
ensures { real result = Q.real q }
650
ensures { num result = q.Q.num /\ den result = q.Q.den }
651
= q
652
end