Common — library colibrilib.fp_interval — module Export

The interface of OCaml

The functions that fp_interval.ml calls, total: the domains carry their format only as ghost, so the format of a domain is read on its floats (dom_format), and a domain without float (NaN or empty) takes the format of the other argument, or of the format given. The constants of a format (the infinities, the zeros, the bounds of the classes, –1 and 1) are computed here from the format.

7216
module Export
7217
use int.Int
7218
use int.Power
7219
use list.List
7220
use option.Option
7221
use real.RealInfix
7222
use real.FromInt
7223
use colibrilib.pow2r.Pow2r
7224
use colibrilib.fp.Widen
7225
use colibrilib.fp.Ereal
7226
use colibrilib.fbin.Fp
7227
use colibrilib.fp_facts.Facts
7228
use Intervals
7229
use FpInterval
7230
use Rules

Two domains with floats of two formats, or a domain with floats of another format than the one given

7234
exception
FormatMismatch

The floats of format fm in d, read in the format fm

7237
predicate
mem_at
(fm: format) (v: t) (d: dom) =
7238
fmt v = fm /\ if is_nan v then d.nan else mem_u v d.u

d has no float of another format than fm

7241
predicate
fits
(fm: format) (d: dom) = d.u <> Nil -> d.fm = fm

The format of two domains: the one of their floats

7244
function
pfm
(d1 d2: dom) : format = if d1.u <> Nil then d1.fm else d2.fm
7245
7246
predicate
mismatch
(d1 d2: dom) = d1.u <> Nil /\ d2.u <> Nil /\ d1.fm <> d2.fm

The format of the floats of d

  Valid (27ms) (colibri2)
7249
let
dom_format
(d: dom) : option format
7250
ensures { match result with
7251
| None -> d.u = Nil
7252
| Some f -> d.u <> Nil /\ f = d.fm end }
7253
= match d.u with Nil -> None | Cons (a, _) _ -> Some (format_of a) end

d in the format fm

  Valid (34ms) (colibri2)
7256
let
in_fmt
(ghost fm: format) (d: dom) : dom
7257
ensures { result.u = d.u /\ result.nan = d.nan }
7258
ensures { fits fm d -> result.fm = fm }
7259
ensures { fits fm d -> forall v. mem v result <-> mem_at fm v d }
7260
= match d.u with
7261
| Nil -> { u = Nil; nan = d.nan; fm = fm }
7262
| Cons _ _ -> d
7263
end

d1 and d2 in their common format

  Valid (76ms) (cvc5)
7266
let
common
(d1 d2: dom) : (dom, dom)
7267
raises { FormatMismatch -> mismatch d1 d2 }
7268
ensures { let (e1, e2) = result in
7269
e1.fm = pfm d1 d2 /\ e2.fm = pfm d1 d2 /\
7270
(forall v. mem v e1 <-> mem_at (pfm d1 d2) v d1) /\
7271
(forall v. mem v e2 <-> mem_at (pfm d1 d2) v d2) /\
7272
e1.u = d1.u /\ e2.u = d2.u /\ e1.nan = d1.nan /\ e2.nan = d2.nan }
7273
= match dom_format d1, dom_format d2 with
7274
| Some f1, Some f2 ->
7275
if eq_format f1 f2 then (in_fmt d1.fm d1, in_fmt d1.fm d2) else raise FormatMismatch
7276
| Some _, None -> (in_fmt d1.fm d1, in_fmt d1.fm d2)
7277
| None, _ -> (in_fmt d2.fm d1, in_fmt d2.fm d2)
7278
end

d in the format fm, or FormatMismatch

  Valid (31ms) (colibri2)
7281
let
check_fmt
(fm: format) (d: dom) : dom
7282
raises { FormatMismatch -> not fits fm d }
7283
ensures { result.fm = fm /\ result.u = d.u /\ result.nan = d.nan }
7284
ensures { forall v. mem v result <-> mem_at fm v d }
7285
= match dom_format d with
7286
| Some f -> if eq_format f fm then in_fmt fm d else raise FormatMismatch
7287
| None -> in_fmt fm d
7288
end

The constants of a format

  Valid (38ms) (colibri2)
7292
let
minf
(fm: format) : t
7293
ensures { result = minus_infinity fm }
7294
= {proof…}
7295
let ghost x = minus_infinity fm in
7296
assert { is_not_nan x /\ index x = - nb_sign fm };
7297
assert { of_index fm (- nb_sign fm) = x by of_index (fmt x) (index x) = x };
7298
{qed}
7299
of_index_v fm (- nb_sign_v fm)
7300
Valid (51ms) (colibri2)
7301
let
pinf
(fm: format) : t
7302
ensures { result = plus_infinity fm }
7303
= {proof…}
7304
let ghost x = plus_infinity fm in
7305
assert { is_not_nan x /\ index x = nb_sign fm - 1 };
7306
assert { of_index fm (nb_sign fm - 1) = x by of_index (fmt x) (index x) = x };
7307
{qed}
7308
of_index_v fm (nb_sign_v fm - 1)

The float of index i

  Valid (20ms) (colibri2)
7311
let
at_i
(fm: format) (i: int) : t
7312
ensures { - nb_sign fm <= i < nb_sign fm -> at_index fm result i }
7313
= {proof…} if pure { - nb_sign fm <= i < nb_sign fm } then of_index_range fm i; {qed}
7314
of_index_v fm i

The float 1

  Valid (50ms) (colibri2 13) (split_vc) (depth 1)
7317
let
one_f
(fm: format) : t
7318
ensures { fmt result = fm /\ is_not_nan result /\ ext result = Fin 1.0 }
7319
= {proof…}
7320
max_float_ge fm;
7321
assert { power 2 (eb fm) = 2 * emax fm };
7322
assert { ulp_max fm + sb fm - 1 = emax fm - 1 };
7323
assert { 1 <= emax fm by power 2 (eb fm - 1) >= 1 };
7324
pow2r_le 0 (ulp_max fm + sb fm - 1);
7325
assert { pow2r 0 = 1.0 };
7326
assert { 2 <= power 2 (sb fm) };
7327
let ghost x = int_exact fm 1 in
7328
ext_sign x;
7329
assert { is_positive x };
7330
assert { round_f (fmt x) RNE (if is_positive x then false else true) (ext x) = x };
7331
assert { round_f fm RNE false (ext x) = x };
7332
{qed}
7333
of_int fm RNE false 1
7334
Valid (412ms) (colibri2)
7335
let
consts_of
(fm: format) : (t, t, t, t, t, t)
7336
ensures { let (minf, pinf, nz, pz, m1, p1) = result in
7337
consts fm minf pinf nz pz m1 p1 }
7338
= {proof…} format_facts fm (); {qed}
7339
let p1 = one_f fm in
7340
(minf fm, pinf fm, at_i fm (-1), at_i fm 0, neg p1, p1)
7341
Valid (61ms) (cvc5)
7342
let
specials_of
(fm: format) : specials
7343
ensures { ok_specials fm result }
7344
= {proof…} format_facts fm (); {qed}
7345
let nb = nb_sign_v fm in
7346
let h = binade_v fm in
7347
{ minf = minf fm; nl = at_i fm (1 - nb); nf = at_i fm (-1 - h);
7348
nsl = at_i fm (- h); nsf = at_i fm (-2); nz = at_i fm (-1);
7349
pz = at_i fm 0; psf = at_i fm 1; psl = at_i fm (h - 1);
7350
pf = at_i fm h; pl = at_i fm (nb - 2); pinf = pinf fm }

The domains

7354
exception
NotInterval
7355
Valid (25ms) (colibri2)
7356
let
nan_dom
() : dom
7357
ensures { result.u = Nil /\ result.nan }
7358
= FpInterval.nan_dom (any format)
7359
Valid (369ms) (colibri2)
7360
let
singleton
(v: t) : dom
7361
ensures { result.fm = fmt v }
7362
ensures { forall w. mem w result <-> fmt w = fmt v /\
7363
if is_nan v then is_nan w else is_not_nan w /\ le_dz v w /\ le_dz w v }
7364
= FpInterval.singleton (format_of v) v

[a, b], for a <= b neither NaN of one format

  Valid (27ms) (colibri2)
7367
let
interval
(a b: t) : dom
7368
raises { NotInterval ->
7369
not (is_not_nan a /\ is_not_nan b /\ fmt a = fmt b /\ le_dz a b) }
7370
ensures { result.fm = fmt a }
7371
ensures { forall v. mem v result <-> fmt v = fmt a /\ is_not_nan v /\ in_iv v a b }
7372
= if is_nan a || is_nan b || not (eq_format (format_of a) (format_of b))
7373
|| not (le_diff_zero a b)
7374
then raise NotInterval;
7375
FpInterval.interval (format_of a) a b
7376
Valid (30ms) (colibri2)
7377
let
top
(fm: format) : dom
7378
ensures { result.fm = fm }
7379
ensures { forall v. mem v result <-> fmt v = fm }
7380
= FpInterval.top fm (minf fm) (pinf fm)
7381
Valid (31ms) (colibri2)
7382
let
except
(f: t) : dom
7383
ensures { result.fm = fmt f }
7384
ensures { forall v. mem v result <->
7385
fmt v = fmt f /\ if is_nan f then not (is_nan v) else v <> f }
7386
= let fm = format_of f in FpInterval.except fm (minf fm) (pinf fm) f
7387
Valid (23ms) (colibri2)
7388
let
normal
(fm: format) : dom
7389
ensures { result.fm = fm }
7390
ensures { forall v. mem v result <-> fmt v = fm /\ is_normal v }
7391
= let s = specials_of fm in FpInterval.normal fm s.nl s.nf s.pf s.pl
7392
Valid (32ms) (colibri2)
7393
let
subnormal
(fm: format) : dom
7394
ensures { result.fm = fm }
7395
ensures { forall v. mem v result <-> fmt v = fm /\ is_subnormal v }
7396
= let s = specials_of fm in FpInterval.subnormal fm s.nsl s.nsf s.psf s.psl
7397
Valid (28ms) (colibri2)
7398
let
zeros
(fm: format) : dom
7399
ensures { result.fm = fm }
7400
ensures { forall v. mem v result <-> fmt v = fm /\ is_zero v }
7401
= FpInterval.zeros fm (at_i fm (-1)) (at_i fm 0)
7402
Valid (28ms) (colibri2)
7403
let
infinites
(fm: format) : dom
7404
ensures { result.fm = fm }
7405
ensures { forall v. mem v result <-> fmt v = fm /\ is_inf v }
7406
= FpInterval.infinites fm (minf fm) (pinf fm)
7407
Valid (36ms) (colibri2)
7408
let
finites
(fm: format) : dom
7409
ensures { result.fm = fm }
7410
ensures { forall v. mem v result <-> fmt v = fm /\ is_not_nan v /\ not (is_inf v) }
7411
= let s = specials_of fm in FpInterval.finites fm s.nl s.pl
7412
Valid (50ms) (colibri2)
7413
let
negatives
(fm: format) : dom
7414
ensures { result.fm = fm }
7415
ensures { forall v. mem v result <-> fmt v = fm /\ is_not_nan v /\ not (is_positive v) }
7416
= FpInterval.negatives fm (minf fm) (at_i fm (-1))
7417
Valid (27ms) (colibri2)
7418
let
positives
(fm: format) : dom
7419
ensures { result.fm = fm }
7420
ensures { forall v. mem v result <-> fmt v = fm /\ is_not_nan v /\ is_positive v }
7421
= FpInterval.positives fm (at_i fm 0) (pinf fm)

The operations

  Valid (45ms) (colibri2)
7425
let
union
(d1 d2: dom) : dom
7426
raises { FormatMismatch -> mismatch d1 d2 }
7427
ensures { result.fm = pfm d1 d2 }
7428
ensures { forall v. mem v result <-> mem_at (pfm d1 d2) v d1 \/ mem_at (pfm d1 d2) v d2 }
7429
= let (e1, e2) = common d1 d2 in FpInterval.union e1.fm e1 e2
7430
Valid (70ms) (cvc5)
7431
let
inter
(d1 d2: dom) : option dom
7432
raises { FormatMismatch -> mismatch d1 d2 }
7433
ensures { match result with
7434
| None -> forall v. not (mem_at (pfm d1 d2) v d1 /\ mem_at (pfm d1 d2) v d2)
7435
| Some d -> d.fm = pfm d1 d2 /\ not (is_bot d) /\
7436
forall v. mem v d <-> mem_at (pfm d1 d2) v d1 /\ mem_at (pfm d1 d2) v d2
7437
end }
7438
= let (e1, e2) = common d1 d2 in FpInterval.inter e1.fm e1 e2
7439
Valid (94ms) (cvc4)
7440
let
diff
(d1 d2: dom) : option dom
7441
raises { FormatMismatch -> mismatch d1 d2 }
7442
ensures { match result with
7443
| None -> forall v. not (mem_at (pfm d1 d2) v d1 /\ not mem_at (pfm d1 d2) v d2)
7444
| Some d -> d.fm = pfm d1 d2 /\ not (is_bot d) /\
7445
forall v. mem v d <-> mem_at (pfm d1 d2) v d1 /\ not mem_at (pfm d1 d2) v d2
7446
end }
7447
= let (e1, e2) = common d1 d2 in FpInterval.diff e1.fm e1 e2
7448
Valid (82ms) (cvc4)
7449
let
complement
(fm: format) (d: dom) : option dom
7450
raises { FormatMismatch -> not fits fm d }
7451
ensures { match result with
7452
| None -> forall v. fmt v = fm -> mem_at fm v d
7453
| Some c -> c.fm = fm /\ not (is_bot c) /\
7454
forall v. mem v c <-> fmt v = fm /\ not mem_at fm v d
7455
end }
7456
= let e = check_fmt fm d in FpInterval.complement fm (minf fm) (pinf fm) e

The floats x of format fm with roundToIntegral m x in d (FpInterval.rti_back)

  Valid (79ms) (cvc4)
7460
let
rti_back
(fm: format) (m: mode) (d: dom) : dom
7461
raises { FormatMismatch -> not fits fm d }
7462
ensures { result.fm = fm }
7463
ensures { forall x. fmt x = fm -> mem_at fm (fp_rti m x) d -> mem x result }
7464
= let e = check_fmt fm d in
7465
{proof…}
7466
let lemma pt (x: t) : unit
7467
requires { fmt x = fm } ensures { fmt (fp_rti m x) = fm }
7468
= if is_nan x then () else rti_not_nan m x in
7469
{qed}
7470
FpInterval.rti_back fm (minf fm) (pinf fm) m e

The floats x of format fm with x * y in r for some y of d (FpInterval.mul_back)

  Valid (356ms) (cvc4)
7474
let
mul_back
(fm: format) (m: mode) (r d: dom) : dom
7475
raises { FormatMismatch -> not fits fm r \/ not fits fm d }
7476
ensures { result.fm = fm }
7477
ensures { forall x y. fmt x = fm -> mem_at fm y d -> mem_at fm (fp_mul m x y) r -> mem x result }
7478
= let er = check_fmt fm r in
7479
let ed = check_fmt fm d in
7480
{proof…} format_facts fm (); {qed}
7481
FpInterval.mul_back fm (minf fm) (pinf fm) (at_i fm (-1)) (at_i fm 0) m er ed

The floats x of format fm with x / y in r for some y of d (FpInterval.div_back_num)

  Valid (86ms) (cvc5)
7485
let
div_back_num
(fm: format) (m: mode) (r d: dom) : dom
7486
raises { FormatMismatch -> not fits fm r \/ not fits fm d }
7487
ensures { result.fm = fm }
7488
ensures { forall x y. fmt x = fm -> mem_at fm y d -> mem_at fm (fp_div m x y) r -> mem x result }
7489
= let er = check_fmt fm r in
7490
let ed = check_fmt fm d in
7491
{proof…} format_facts fm (); {qed}
7492
FpInterval.div_back_num fm (minf fm) (pinf fm) (at_i fm (-1)) (at_i fm 0) m er ed

The floats y of format fm with x / y in r for some x of n (FpInterval.div_back_den)

  Valid (81ms) (cvc5)
7496
let
div_back_den
(fm: format) (m: mode) (r n: dom) : dom
7497
raises { FormatMismatch -> not fits fm r \/ not fits fm n }
7498
ensures { result.fm = fm }
7499
ensures { forall x y. fmt y = fm -> mem_at fm x n -> mem_at fm (fp_div m x y) r -> mem y result }
7500
= let er = check_fmt fm r in
7501
let en = check_fmt fm n in
7502
{proof…} format_facts fm (); {qed}
7503
FpInterval.div_back_den fm (minf fm) (pinf fm) (at_i fm (-1)) (at_i fm 0) m er en
7504
Valid (346ms) (colibri2)
7505
let
is_included
(d1 d2: dom) : bool
7506
raises { FormatMismatch -> mismatch d1 d2 }
7507
ensures { result <-> forall v. mem_at (pfm d1 d2) v d1 -> mem_at (pfm d1 d2) v d2 }
7508
= let (e1, e2) = common d1 d2 in FpInterval.is_included e1.fm e1 e2
7509
Valid (364ms) (colibri2)
7510
let
is_distinct
(d1 d2: dom) : bool
7511
raises { FormatMismatch -> mismatch d1 d2 }
7512
ensures { result <-> forall v. not (mem_at (pfm d1 d2) v d1 /\ mem_at (pfm d1 d2) v d2) }
7513
= let (e1, e2) = common d1 d2 in FpInterval.is_distinct e1.fm e1 e2
7514
Valid (308ms) (cvc5)
7515
let
is_distinct_or_included
(d1 d2: dom) : comparison
7516
raises { FormatMismatch -> mismatch d1 d2 }
7517
ensures { result = Included <->
7518
forall v. mem_at (pfm d1 d2) v d1 -> mem_at (pfm d1 d2) v d2 }
7519
ensures { result = Disjoint <->
7520
(forall v. not (mem_at (pfm d1 d2) v d1 /\ mem_at (pfm d1 d2) v d2)) /\
7521
not (forall v. mem_at (pfm d1 d2) v d1 -> mem_at (pfm d1 d2) v d2) }
7522
= let (e1, e2) = common d1 d2 in FpInterval.is_distinct_or_included e1.fm e1 e2
7523
Valid (30ms) (colibri2) (cvc5) (split_vc) (depth 1)
7524
let
is_singleton
(d: dom) : singleton
7525
ensures { match result with
7526
| NaN -> forall v. mem v d <-> fmt v = d.fm /\ is_nan v
7527
| Sin a -> not (is_nan a) /\ forall v. mem v d <-> v = a
7528
| No -> not (forall v. mem v d <-> fmt v = d.fm /\ is_nan v) /\
7529
forall a. not (forall v. mem v d <-> v = a)
7530
end }
7531
= FpInterval.is_singleton d.fm d
7532
Valid (12ms) (colibri2)
7533
let
min_f
(d: dom) : t
7534
raises { Empty -> d.u = Nil }
7535
ensures { fmt result = d.fm }
7536
ensures { mem_u result d.u /\ forall v. mem_u v d.u -> le_dz result v }
7537
= FpInterval.min_f d.fm d
7538
Valid (20ms) (colibri2)
7539
let
max_f
(d: dom) : t
7540
raises { Empty -> d.u = Nil }
7541
ensures { fmt result = d.fm }
7542
ensures { mem_u result d.u /\ forall v. mem_u v d.u -> le_dz v result }
7543
= FpInterval.max_f d.fm d
7544
Valid (38ms) (colibri2)
7545
let
is_finite
(d: dom) : bool
7546
ensures { result <-> forall v. mem v d -> not (is_nan v) /\ not (is_inf v) }
7547
= match dom_format d with
7548
| None ->
7549
{proof…} assert { d.nan -> mem (not_a_number d.fm) d }; {qed}
7550
not d.nan
7551
| Some fm -> FpInterval.is_finite fm (minf fm) (pinf fm) d
7552
end
7553
Valid (91ms) (cvc4)
7554
let
classify
(d: dom) : classify
7555
ensures { result.clnan <-> d.nan }
7556
ensures { result.neg_infinity <-> mem (minus_infinity d.fm) d }
7557
ensures { result.neg_normal <->
7558
exists v. mem v d /\ is_normal v /\ not is_positive v }
7559
ensures { result.neg_subnormal <->
7560
exists v. mem v d /\ is_subnormal v /\ not is_positive v }
7561
ensures { result.clzeros <-> exists v. mem v d /\ is_zero v }
7562
ensures { result.pos_subnormal <->
7563
exists v. mem v d /\ is_subnormal v /\ is_positive v }
7564
ensures { result.pos_normal <->
7565
exists v. mem v d /\ is_normal v /\ is_positive v }
7566
ensures { result.pos_infinity <-> mem (plus_infinity d.fm) d }
7567
= match dom_format d with
7568
| None ->
7569
{proof…}
7570
assert { forall v. mem v d -> is_nan v };
7571
assert { forall v. is_nan v -> not (is_normal v \/ is_subnormal v \/ is_zero v) };
7572
{qed}
7573
{ clnan = d.nan; neg_infinity = false; neg_normal = false;
7574
neg_subnormal = false; clzeros = false; pos_subnormal = false;
7575
pos_normal = false; pos_infinity = false }
7576
| Some fm -> FpInterval.classify_dom fm (specials_of fm) d
7577
end

The rules on the sign and the magnitude

  Valid (48ms) (cvc5)
7581
let
add_rule
(fm: format) (da db: dom) : decision
7582
raises { FormatMismatch -> not (fits fm da /\ fits fm db) }
7583
ensures { forall m a b. mem_at fm a da -> mem_at fm b db ->
7584
fp_add m b a = fp_add m a b /\
7585
match result with
7586
| DNone -> true
7587
| DMerge -> fp_add m a b = b
7588
| DEq -> fp_eq (fp_add m a b) b
7589
| DLeB -> fp_le b (fp_add m a b)
7590
| DLeR -> fp_le (fp_add m a b) b
7591
end }
7592
= let ea = check_fmt fm da in
7593
let eb = check_fmt fm db in
7594
let (minf, pinf, nz, pz, m1, p1) = consts_of fm in
7595
Rules.add_rule fm minf pinf nz pz m1 p1 ea eb
7596
Valid (43ms) (cvc5)
7597
let
mul_rule
(fm: format) (da db: dom) : decision
7598
raises { FormatMismatch -> not (fits fm da /\ fits fm db) }
7599
ensures { forall m a b. mem_at fm a da -> mem_at fm b db ->
7600
fp_mul m b a = fp_mul m a b /\
7601
match result with
7602
| DNone | DEq -> true
7603
| DMerge -> fp_mul m a b = b
7604
| DLeB -> fp_le b (fp_mul m a b)
7605
| DLeR -> fp_le (fp_mul m a b) b
7606
end }
7607
= let ea = check_fmt fm da in
7608
let eb = check_fmt fm db in
7609
let (minf, pinf, nz, pz, m1, p1) = consts_of fm in
7610
Rules.mul_rule fm minf pinf nz pz m1 p1 ea eb
7611
Valid (53ms) (cvc5)
7612
let
div_rule
(fm: format) (da db: dom) : decision
7613
raises { FormatMismatch -> not (fits fm da /\ fits fm db) }
7614
ensures { forall m a b. mem_at fm a da -> mem_at fm b db ->
7615
match result with
7616
| DNone | DEq -> true
7617
| DMerge -> fp_div m a b = a
7618
| DLeB -> fp_le a (fp_div m a b)
7619
| DLeR -> fp_le (fp_div m a b) a
7620
end }
7621
= let ea = check_fmt fm da in
7622
let eb = check_fmt fm db in
7623
let (minf, pinf, nz, pz, m1, p1) = consts_of fm in
7624
Rules.div_rule fm minf pinf nz pz m1 p1 ea eb
7625
end