Common — library colibrilib.fbin — module FpBase

Fp: Impl refines fp.Intf

FpNames gives the names of Intf that Impl lacks. Fp is Impl seen through Intf: the clone proves every axiom of Intf and the specification of every val on the concrete floats, and the users of Fp (fp_facts.mlw, fp_dyadic.mlw, fp_interval.mlw, fp_conv.mlw) see only Intf. The extracted code calls the functions of Impl directly, with the formats of Format.

4183
module FpBase
4184
use int.Int
4185
use int.Power
4186
use int.EuclideanDivision as ED
4187
use real.RealInfix
4188
use real.FromInt
4189
use option.Option
4190
use colibrilib.fp.Widen
4191
use colibrilib.fp.Ereal
4192
use colibrilib.dyadic.Dyadic as D
4193
use Pow2r
4194
use Format
4195
use Float
4196
use Round
4197
use real.Truncate
4198
use Impl
4199
use Integral
4200
use Exact
4201
use Nearest as N
4202
Valid (48ms) (colibri2)
4203
let
of_int
(fm: format) (m: mode) (z: bool) (i: int) : t
4204
ensures { result = round_f fm m z (Fin (from_int i)) }
4205
= {proof…} assert { from_int i /. from_int 1 = from_int i }; {qed}
4206
round_q fm m z i 1
4207
Valid (54ms) (colibri2)
4208
let
nb_sign_v
(fm: format) : int
4209
ensures { result = nb_sign fm }
4210
= nb_sign_p fm
4211
Valid (54ms) (colibri2)
4212
let
binade_v
(fm: format) : int
4213
ensures { result = binade fm }
4214
= binade_p fm
4215
Valid (49ms) (colibri2)
4216
let
of_index_v
(fm: format) (i: int) : t
4217
ensures { result = of_index fm i }
4218
= of_index_p fm i
4219
Valid (45ms) (colibri2)
4220
let
to_dyadic
(x: t) : (int, int)
4221
ensures { let (n, e) = result in is_finite x -> to_real x = from_int n *. pow2r e }
4222
= dyadic_of x
4223
Valid (46ms) (colibri2)
4224
let
format_of
(x: t) : format
4225
ensures { result = x.fmt }
4226
= format_of x
4227
Valid (50ms) (colibri2)
4228
let
eq_format
(a b: format) : bool
4229
ensures { result <-> a = b }
4230
= eq_format a b
4231
Valid (43ms) (colibri2)
4232
let
succ_diff_zero
(x: t) : t
4233
ensures { not is_nan x /\ not is_plus_infinity x -> result = succ_dz x }
4234
= succ_diff_zero x
4235
Valid (44ms) (colibri2)
4236
let
pred_diff_zero
(x: t) : t
4237
ensures { not is_nan x /\ not is_minus_infinity x -> result = pred_dz x }
4238
= pred_diff_zero x
4239
Valid (51ms) (colibri2)
4240
let
mid_index
(x y: t) : t
4241
ensures { not is_nan x /\ not is_nan y /\ x.fmt = y.fmt ->
4242
result = of_index x.fmt (ED.div (index x + index y) 2) }
4243
= mid_index x y
4244
Valid (51ms) (colibri2)
4245
let
widen
(fm: format) : option format
4246
ensures { match result with
4247
| None -> false
4248
| Some fm' -> fm'.eb = fm.eb /\ fm'.sb = fm.sb + 1 end }
4249
= widen fm
4250
Valid (62ms) (colibri2)
4251
let
le_diff_zero
(x y: t) : bool
4252
ensures { result <-> le_dz x y }
4253
= le_diff_zero x y
4254
Valid (49ms) (colibri2)
4255
let
lt_diff_zero
(x y: t) : bool
4256
ensures { result <-> lt_dz x y }
4257
= lt_diff_zero x y
4258
Valid (44ms) (colibri2)
4259
let ghost
index_range
(x: t) : unit
4260
requires { not is_nan x }
4261
ensures { - nb_sign x.fmt <= index x < nb_sign x.fmt }
4262
= index_range x
4263
Valid (54ms) (colibri2)
4264
let ghost
of_index_range
(fm: format) (i: int) : unit
4265
requires { - nb_sign fm <= i < nb_sign fm }
4266
ensures { not is_nan (of_index fm i) /\ index (of_index fm i) = i }
4267
ensures { (of_index fm i).fmt = fm }
4268
= of_index_range fm i
4269
Valid (57ms) (colibri2)
4270
let
add
(m: mode) (x y: t) : t
4271
ensures { x.fmt = y.fmt -> result = fp_add m x y }
4272
= add m x y
4273
Valid (60ms) (colibri2)
4274
let
mul
(m: mode) (x y: t) : t
4275
ensures { x.fmt = y.fmt -> result = fp_mul m x y }
4276
= mul m x y
4277
Valid (43ms) (colibri2)
4278
let
convert
(fm: format) (m: mode) (x: t) : t
4279
ensures { result = fp_convert fm m x }
4280
= convert fm m x
4281
Valid (48ms) (colibri2)
4282
let
div
(m: mode) (x y: t) : t
4283
ensures { x.fmt = y.fmt -> result = fp_div m x y }
4284
= Impl.div m x y
4285
Valid (57ms) (colibri2)
4286
let
sqrt
(m: mode) (x: t) : t
4287
ensures { result = fp_sqrt m x }
4288
= sqrt m x
4289
Valid (57ms) (colibri2)
4290
let
round_to_integral
(m: mode) (x: t) : t
4291
ensures { result = fp_rti m x }
4292
= round_to_integral m x
4293
Valid (55ms) (colibri2)
4294
let ghost
int_exact
(fm: format) (i: int) : t
4295
requires { - power 2 fm.sb <= i <= power 2 fm.sb }
4296
requires { -. to_real (of_index fm (nb_sign fm - 2)) <=. from_int i <=.
4297
to_real (of_index fm (nb_sign fm - 2)) }
4298
ensures { result.fmt = fm /\ not is_nan result /\ ext result = Fin (from_int i) }
4299
= int_exact fm i
4300
Valid (60ms) (colibri2)
4301
let ghost
widen_exact
(fm': format) (x: t) : t
4302
requires { x.fmt.eb <= fm'.eb /\ x.fmt.sb <= fm'.sb }
4303
requires { not is_nan x /\ not is_plus_infinity x /\ not is_minus_infinity x }
4304
ensures { result.fmt = fm' /\ not is_nan result /\ ext result = ext x }
4305
= widen_exact fm' x
4306
Valid (55ms) (colibri2)
4307
let ghost
float_dyadic
(x: t) : unit
4308
requires { not is_nan x /\ not is_plus_infinity x /\ not is_minus_infinity x }
4309
ensures { D.fix (to_real x) (qmin x.fmt) /\ D.flt (to_real x) x.fmt.sb }
4310
= float_dyadic x
4311
Valid (54ms) (colibri2)
4312
let ghost
round_fix
(fm: format) (m: mode) (z: bool) (r: real) (e: int) : unit
4313
requires { D.fix r e /\ e <= qmin fm + power 2 fm.eb - 3 }
4314
requires { not is_plus_infinity (round_f fm m z (Fin r)) }
4315
requires { not is_minus_infinity (round_f fm m z (Fin r)) }
4316
ensures { D.fix (to_real (round_f fm m z (Fin r))) e }
4317
= round_fix fm m z r e
4318
Valid (61ms) (colibri2)
4319
let ghost
round_zero_small
(fm: format) (m: mode) (z: bool) (r: real) : unit
4320
requires { r <> 0.0 /\ is_zero (round_f fm m z (Fin r)) }
4321
ensures { -. pow2r (qmin fm) <. r <. pow2r (qmin fm) }
4322
= round_zero_small fm m z r
4323
Valid (52ms) (colibri2)
4324
let ghost
dyadic_exact
(fm: format) (r: real) : t
4325
requires { D.fix r (qmin fm) /\ D.flt r fm.sb }
4326
requires { -. to_real (of_index fm (nb_sign fm - 2)) <=. r <=.
4327
to_real (of_index fm (nb_sign fm - 2)) }
4328
ensures { result.fmt = fm /\ not is_nan result /\ ext result = Fin r }
4329
= dyadic_exact fm r
4330
Valid (60ms) (colibri2)
4331
let ghost
max_float_ge
(fm: format) : unit
4332
ensures { pow2r (qmin fm + power 2 fm.eb - 3 + fm.sb - 1) <=.
4333
to_real (of_index fm (nb_sign fm - 2)) }
4334
= max_float_ge fm
4335
Valid (55ms) (colibri2)
4336
let ghost
near_double
(m: mode) (z: bool) (x: t) (r: real) : unit
4337
requires { m = RNE \/ m = RNA }
4338
requires { not is_nan x /\ not is_plus_infinity x /\ not is_minus_infinity x }
4339
ensures { 2.0 *. to_real x <=. r ->
4340
not is_plus_infinity (round_f x.fmt m z (Fin r)) ->
4341
2.0 *. to_real x <=. to_real (of_index x.fmt (nb_sign x.fmt - 2)) }
4342
ensures { r <=. 2.0 *. to_real x ->
4343
not is_minus_infinity (round_f x.fmt m z (Fin r)) ->
4344
-. to_real (of_index x.fmt (nb_sign x.fmt - 2)) <=. 2.0 *. to_real x }
4345
= near_double m z x r

The facts of Intf on round_int, from its definition

  Valid (412ms) (colibri2)
4348
let ghost
round_int_ge
(m: mode) (r: real) (n: int) : unit
4349
requires { n <= round_int m r }
4350
ensures { match m with
4351
| RTN -> from_int n <=. r
4352
| RTP -> from_int n -. 1.0 <=. r
4353
| RTZ -> if 0 < n then from_int n <=. r else from_int n -. 1.0 <=. r
4354
| RNE | RNA -> from_int n -. 0.5 <=. r
4355
end }
4356
= {proof…}
4357
let f = Truncate.floor r in
4358
assert { from_int f <=. r <. from_int f +. 1.0 };
4359
assert { r <. 0.0 -> f <= -1 };
4360
assert { 0.0 <=. r -> 0 <= f }
4361
{qed}
4362
Valid (107ms) (colibri2)
4363
let ghost
round_int_le
(m: mode) (r: real) (n: int) : unit
4364
requires { round_int m r <= n }
4365
ensures { match m with
4366
| RTN -> r <=. from_int n +. 1.0
4367
| RTP -> r <=. from_int n
4368
| RTZ -> if n < 0 then r <=. from_int n else r <=. from_int n +. 1.0
4369
| RNE | RNA -> r <=. from_int n +. 0.5
4370
end }
4371
= {proof…}
4372
let f = Truncate.floor r in
4373
assert { from_int f <=. r <. from_int f +. 1.0 };
4374
assert { r <. 0.0 -> f <= -1 };
4375
assert { 0.0 <=. r -> 0 <= f }
4376
{qed}
4377
Valid (68ms) (colibri2)
4378
let ghost
round_int_ceil
(r: real) (k: int) : unit
4379
requires { r <=. from_int k }
4380
ensures { round_int RTP r <= k }
4381
= {proof…}
4382
let f = Truncate.floor r in
4383
assert { from_int f <=. r <. from_int f +. 1.0 };
4384
assert { f <= k };
4385
assert { r -. from_int f <> 0.0 -> f < k }
4386
{qed}
4387
Valid (58ms) (colibri2)
4388
let ghost
round_int_floor
(r: real) (k: int) : unit
4389
requires { from_int k <=. r }
4390
ensures { k <= round_int RTN r }
4391
= {proof…}
4392
let f = Truncate.floor r in
4393
assert { from_int f <=. r <. from_int f +. 1.0 };
4394
assert { k < f + 1 }
4395
{qed}
4396
Valid (68ms) (colibri2)
4397
let
round_int_v
(m: mode) (x: t) : int
4398
requires { not is_nan x /\ not is_plus_infinity x /\ not is_minus_infinity x }
4399
ensures { result = round_int m (to_real x) }
4400
= match to_integer m x with
4401
| Some n -> n
4402
| None -> absurd
4403
end
4404
Valid (51ms) (colibri2)
4405
let
of_q
(fm: format) (m: mode) (z: bool) (n d: int) : t
4406
requires { 0 < d }
4407
ensures { result = round_f fm m z (Fin (from_int n /. from_int d)) }
4408
= round_q fm m z n d

The types and the logic of Intf

4411
type
format
= Format.format
4412
type
t
= Float.t
4413
function
fmt
(x: t) : format = x.Float.fmt
4414
function
eb
(fm: format) : int = fm.Format.eb
4415
function
sb
(fm: format) : int = fm.Format.sb
4416
let predicate
is_nan
(x: t) = Impl.is_nan x
4417
predicate
is_plus_infinity
(x: t) = Impl.is_plus_infinity x
4418
predicate
is_minus_infinity
(x: t) = Impl.is_minus_infinity x
4419
function
not_a_number
(fm: format) : t = Impl.not_a_number fm
4420
function
plus_infinity
(fm: format) : t = Impl.plus_infinity fm
4421
function
minus_infinity
(fm: format) : t = Impl.minus_infinity fm
4422
predicate
le_dz
(x y: t) = Impl.le_dz x y
4423
predicate
lt_dz
(x y: t) = Impl.lt_dz x y
4424
predicate
is_zero
(x: t) = Impl.is_zero x
4425
predicate
is_positive
(x: t) = Impl.is_positive x
4426
predicate
is_subnormal
(x: t) = Impl.is_subnormal x
4427
predicate
is_normal
(x: t) = Impl.is_normal x
4428
function
index
(x: t) : int = Impl.index x
4429
function
of_index
(fm: format) (i: int) : t = Impl.of_index fm i
4430
let function
neg
(x: t) : t = Impl.neg x
4431
let function
abs
(x: t) : t = Impl.abs x
4432
function
min
(x y: t) : t = Impl.min x y
4433
function
max
(x y: t) : t = Impl.max x y
4434
function
to_real
(x: t) : real = Float.to_real x
4435
function
ext
(x: t) : ereal = Impl.ext x
4436
function
round_f
(fm: format) (m: mode) (z: bool) (e: ereal) : t = Float.round_f fm m z e
4437
function
round_int
(m: mode) (r: real) : int = Impl.round_int m r

The index, the widths, the bounds of a real and of a sum, as data

  Valid (43ms) (colibri2)
4440
let
index_v
(x: t) : int
4441
requires { not is_nan x }
4442
ensures { result = index x }
4443
= index_t x
4444
Valid (50ms) (colibri2)
4445
let
eb_v
(fm: format) : int
4446
ensures { result = eb fm }
4447
= fm.Format.eb
4448
Valid (50ms) (colibri2)
4449
let
sb_v
(fm: format) : int
4450
ensures { result = sb fm }
4451
= fm.Format.sb
4452
Valid (85ms) (colibri2)
4453
let
mk_format_o
(e s: int) : option format
4454
ensures { match result with
4455
| Some fm -> eb fm = e /\ sb fm = s
4456
| None -> not (1 < e /\ 1 < s) end }
4457
= if 1 < e && 1 < s then Some { Format.eb = e; Format.sb = s } else None

The linear bounds a r + b <= f <= c r + d of a rounding f to nearest of a real r, when f is in [lo, hi] (Nearest.nearest_bounds): `b = ((am, ae), ad, (bm, be), (cm, ce), cd, (dm, de)) gives a = am 2^ae / ad, b = bm 2^be`, c = cm 2^ce / cd, d = dm 2^de

4464
predicate
nearest_ok_base
(lo hi: t) (b: ((int, int), int, (int, int), (int, int), int, (int, int))) =
4465
let ((am, ae), ad, (bm, be), (cm, ce), cd, (dm, de)) = b in
4466
0 < ad /\ 0 < cd /\
4467
forall m z r. (m = RNE \/ m = RNA) ->
4468
le_dz lo (round_f (fmt lo) m z (Fin r)) -> le_dz (round_f (fmt lo) m z (Fin r)) hi ->
4469
from_int am *. pow2r ae *. r +. from_int ad *. (from_int bm *. pow2r be)
4470
<=. from_int ad *. to_real (round_f (fmt lo) m z (Fin r)) /\
4471
from_int cd *. to_real (round_f (fmt lo) m z (Fin r))
4472
<=. from_int cm *. pow2r ce *. r +. from_int cd *. (from_int dm *. pow2r de)
4473
Valid (1.5s) (colibri2)
4474
let
nearest_bounds
(lo hi: t) : option ((int, int), int, (int, int), (int, int), int, (int, int))
4475
ensures { match result with Some b -> nearest_ok_base lo hi b | None -> true end }
4476
= match N.nearest_bounds lo hi with
4477
| None -> None
4478
| Some b ->
4479
Some ((b.N.lo_coef.dm, b.N.lo_coef.de), b.N.lo_den,
4480
(b.N.lo_cst.dm, b.N.lo_cst.de),
4481
(b.N.hi_coef.dm, b.N.hi_coef.de), b.N.hi_den,
4482
(b.N.hi_cst.dm, b.N.hi_cst.de))
4483
end
4484
Valid (304ms) (colibri2) (cvc5) (split_vc) (depth 1)
4485
let
float_lo
(f: t) (strict exact: bool) : t
4486
ensures { fmt result = fmt f }
4487
ensures { forall r. f = round_f (fmt f) RTP (r <. 0.0) (Fin r) ->
4488
(exact <-> not is_nan f /\ not is_infinity f /\ to_real f = r) ->
4489
forall v. fmt v = fmt f -> not is_nan v -> not is_infinity v ->
4490
(if strict then r <. to_real v else r <=. to_real v) -> le_dz result v }
4491
= Impl.float_lo f strict exact
4492
Valid (1.2s) (colibri2) (cvc5) (split_vc) (depth 1)
4493
let
float_hi
(f: t) (strict exact: bool) : t
4494
ensures { fmt result = fmt f }
4495
ensures { forall r. f = round_f (fmt f) RTN (r <. 0.0) (Fin r) ->
4496
(exact <-> not is_nan f /\ not is_infinity f /\ to_real f = r) ->
4497
forall v. fmt v = fmt f -> not is_nan v -> not is_infinity v ->
4498
(if strict then to_real v <. r else to_real v <=. r) -> le_dz v result }
4499
= Impl.float_hi f strict exact

The sum as Intf.fp_add states it on these symbols

4502
function
fp_add_i
(m: mode) (x y: t) : t =
4503
if is_nan x \/ is_nan y \/ opposite (ext x) (ext y) then not_a_number (fmt x)
4504
else round_f (fmt x) m
4505
(if is_positive x <-> is_positive y then (if is_positive x then false else true)
4506
else (if m = RTN then true else false))
4507
(eadd (ext x) (ext y))
4508
Valid (151ms) (colibri2 3) (cvc5 2) (split_vc 2) (depth 2)
4509
let
add_bounds
(lo hi: t) : option (t, t)
4510
ensures { match result with
4511
| Some (a, b) -> fmt a = fmt lo /\ fmt b = fmt lo /\
4512
forall m x y. fmt x = fmt lo -> fmt y = fmt lo ->
4513
le_dz lo (fp_add_i m x y) -> le_dz (fp_add_i m x y) hi ->
4514
le_dz a x /\ le_dz x b
4515
| None -> true
4516
end }
4517
= {proof…}
4518
let lemma eq (m: mode) (x y: t) : unit
4519
ensures { fp_add_i m x y = fp_add m x y }
4520
= () in
4521
{qed}
4522
AddBound.add_bounds lo hi
4523
Valid (55ms) (colibri2)
4524
let
round_bracket
(fm: format) (m: mode) (n1 d1 n2 d2: int) : option t
4525
ensures { match result with
4526
| None -> d1 <= 0 \/ d2 <= 0 \/
4527
round_f fm m (n1 < 0) (Fin (from_int n1 /. from_int d1))
4528
<> round_f fm m (n2 < 0) (Fin (from_int n2 /. from_int d2))
4529
| Some x -> forall r. from_int n1 /. from_int d1 <=. r <=. from_int n2 /. from_int d2 ->
4530
x = round_f fm m (r <. 0.0) (Fin r)
4531
end }
4532
= Impl.round_bracket fm m n1 d1 n2 d2
4533
Valid (49ms) (colibri2)
4534
let
round_between
(fm: format) (m: mode) (n k: int) : t
4535
requires { power 2 (eb fm - 1) + sb fm - 2 <= k }
4536
ensures { forall r. from_int n /. from_int (power 2 k) <. r <. from_int (n + 1) /. from_int (power 2 k) ->
4537
result = round_f fm m (r <. 0.0) (Fin r) }
4538
= {proof…} assert { 1 - qmin fm = power 2 (eb fm - 1) + sb fm - 2 }; {qed}
4539
Impl.round_between fm m n k

Intf.ext_widen, stated on these symbols

  Valid (49ms) (colibri2)
4542
let lemma
ext_widen_fp
(fm fm': format) (i: int)
4543
requires { eb fm' = eb fm /\ sb fm' = sb fm + 1 }
4544
requires { - Format.nb_sign fm <= i < Format.nb_sign fm }
4545
ensures { ext (of_index fm' (windex i)) = ext (of_index fm i) }
4546
= {proof…} Impl.ext_widen fm fm' i {qed}
4547
4548
end