Common — library colibrilib.fbin — module AddBound

The bounds of the operands of an addition

B. Marre and C. Michel, "Improving the floating point addition and subtraction constraints" (CP 2010), and D. Gallois–Wong, S. Boldo and P. Cuoq, "Optimal inverse projection of floating–point addition" (Numerical Algorithms 83, 2020), Lemmas 4 and 5. Let x + y round into an interval [lo, hi] of floats of one sign, say positive, 2^g the largest power of two that divides a float of the interval, and bg such a float. Then -2^(g+sb) < x <= 2^(g+sb) - 2^g + bg. The paper is in round to nearest; its proof uses only that the rounding is monotone and keeps the multiples of 2^e, so the bounds hold in all the modes.

3310
module AddBound
3311
use int.Int
3312
use int.Power
3313
use int.EuclideanDivision
3314
use real.RealInfix
3315
use real.FromInt
3316
use option.Option
3317
use ref.Ref
3318
use colibrilib.fp.Widen
3319
use colibrilib.fp.Ereal
3320
use colibrilib.zarith.Z as Zarith
3321
use Pow2r
3322
use Format
3323
use Float
3324
use Round
3325
use Impl

r is a multiple of 2^e

3328
predicate
mult
(r: real) (e: int) = exists n: int. r = from_int n *. pow2r e
3329
Valid (42ms) (colibri2)
3330
let ghost
mult_le
(r: real) (e e': int) : unit
3331
requires { e <= e' /\ mult r e' }
3332
ensures { mult r e }
3333
= {proof…}
3334
let n = any int ensures { r = from_int result *. pow2r e' } in
3335
pow2r_add e (e' - e); pow2r_int (e' - e);
3336
assert { r = from_int (n * power 2 (e' - e)) *. pow2r e }
3337
{qed}
3338
Valid (44ms) (colibri2 4) (cvc5) (split_vc) (depth 1)
3339
let ghost
mult_add
(a b: real) (e: int) : unit
3340
requires { mult a e /\ mult b e }
3341
ensures { mult (a +. b) e /\ mult (-. a) e }
3342
= {proof…}
3343
let n = any int ensures { a = from_int result *. pow2r e } in
3344
let k = any int ensures { b = from_int result *. pow2r e } in
3345
assert { a +. b = from_int (n + k) *. pow2r e };
3346
assert { -. a = from_int (- n) *. pow2r e }
3347
{qed}
3348
Valid (36ms) (colibri2)
3349
let ghost
mult_zero
(e: int) : unit
3350
ensures { mult 0.0 e }
3351
= {proof…} assert { 0.0 = from_int 0 *. pow2r e } {qed}
3352
Valid (37ms) (colibri2)
3353
let ghost
mult_one
(e: int) : unit
3354
ensures { mult (pow2r e) e }
3355
= {proof…} assert { pow2r e = from_int 1 *. pow2r e } {qed}

Two multiples of 2^e differ by at least 2^e

  Valid (51ms) (colibri2)
3358
let ghost
mult_gap
(a b: real) (e: int) : unit
3359
requires { mult a e /\ mult b e /\ a <. b }
3360
ensures { a +. pow2r e <=. b }
3361
= {proof…}
3362
let n = any int ensures { a = from_int result *. pow2r e } in
3363
let k = any int ensures { b = from_int result *. pow2r e } in
3364
pow2r_pos e; scale_cmp n k (pow2r e);
3365
assert { a +. pow2r e = from_int (n + 1) *. pow2r e };
3366
scale_cmp (n + 1) k (pow2r e)
3367
{qed}

r = n 2^e with n odd: r + 2^e is a multiple of 2^(e+1)

  Valid (62ms) (colibri2)
3370
let ghost
mult_odd
(r: real) (e: int) : unit
3371
requires { mult r e /\ not mult r (e + 1) }
3372
ensures { mult (r +. pow2r e) (e + 1) }
3373
= {proof…}
3374
let n = any int ensures { r = from_int result *. pow2r e } in
3375
pow2r_succ e;
3376
if mod n 2 = 0 then begin
3377
assert { n = 2 * div n 2 };
3378
assert { r = from_int (div n 2) *. pow2r (e + 1) };
3379
absurd
3380
end else begin
3381
assert { n + 1 = 2 * div (n + 1) 2 };
3382
assert { r +. pow2r e = from_int (n + 1) *. pow2r e };
3383
assert { r +. pow2r e = from_int (div (n + 1) 2) *. pow2r (e + 1) }
3384
end
3385
{qed}

The multiples among the floats

A magnitude is a multiple of its ulp and below 2^(u+sb)

  Valid (53ms) (colibri2)
3390
let ghost
vom_mult
(fm: format) (k: int) : unit
3391
requires { 0 <= k }
3392
ensures { mult (vom fm k) (uexp fm k) /\ qmin fm <= uexp fm k }
3393
ensures { vom fm k <. pow2r (uexp fm k + fm.sb) }
3394
= {proof…}
3395
vom_dec fm k; binade_ge_2 fm;
3396
let u = uexp fm k in
3397
pow2r_add u fm.sb; pow2r_int fm.sb; pow2r_pos u;
3398
assert { power 2 fm.sb = 2 * binade fm };
3399
scale_cmp (sig fm k) (2 * binade fm) (pow2r u)
3400
{qed}
3401
Valid (316ms) (colibri2 4) (cvc5) (split_vc) (depth 1)
3402
let ghost
uexp_mono
(fm: format) (k l: int) : unit
3403
requires { 0 <= k <= l }
3404
ensures { uexp fm k <= uexp fm l }
3405
= {proof…}
3406
binade_ge_2 fm;
3407
let bn = binade fm in
3408
assert { k = div k bn * bn + mod k bn /\ 0 <= mod k bn < bn };
3409
assert { l = div l bn * bn + mod l bn /\ 0 <= mod l bn < bn };
3410
if pure { div l bn < div k bn } then begin
3411
assert { (div l bn + 1) * bn <= div k bn * bn };
3412
absurd
3413
end
3414
{qed}

The ulp of the largest finite float

3417
function
umax
(fm: format) : int = uexp fm (nb_sign fm - 2)

A float of magnitude at least 2^(e+sb) is a multiple of 2^(e+1)

  Valid (427ms) (cvc5)
3421
let ghost
big_mag
(fm: format) (k e: int) : unit
3422
requires { 0 <= k <= nb_sign fm - 2 /\ pow2r (e + fm.sb) <=. vom fm k }
3423
ensures { mult (vom fm k) (e + 1) /\ e + 1 <= umax fm }
3424
= {proof…}
3425
vom_mult fm k; nb_sign_ge fm; uexp_mono fm k (nb_sign fm - 2);
3426
if uexp fm k <= e then begin
3427
pow2r_le (uexp fm k + fm.sb) (e + fm.sb); absurd
3428
end;
3429
mult_le (vom fm k) (e + 1) (uexp fm k)
3430
{qed}
3431
Valid (809ms) (colibri2 3) (cvc4) (cvc5 2) (split_vc 2) (depth 2)
3432
let ghost
big_float
(f: t) (e: int) : unit
3433
requires { is_finite f }
3434
requires { pow2r (e + f.fmt.sb) <=. to_real f \/ to_real f <=. -. pow2r (e + f.fmt.sb) }
3435
ensures { mult (to_real f) (e + 1) /\ e + 1 <= umax f.fmt }
3436
= {proof…}
3437
let fm = f.fmt in
3438
nb_sign_ge fm; pow2r_pos (e + fm.sb);
3439
match f.value with
3440
| Finite ng k ->
3441
vom_zero fm; vom_le fm 0 k;
3442
big_mag fm k e;
3443
if ng then mult_add (vom fm k) 0.0 (e + 1)
3444
| _ -> absurd
3445
end
3446
{qed}

The rounding keeps the multiples of 2^e

  Valid (393ms) (colibri2 14) (cvc5) (split_vc) (depth 1)
3449
let ghost
round_mag_mult
(fm: format) (m: mode) (r: real) (e: int) : unit
3450
requires { 0.0 <=. r /\ mult r e }
3451
ensures { mult (vom fm (round_mag fm m r)) e }
3452
= {proof…}
3453
let k = kdn fm r in
3454
round_mag_range fm m r;
3455
vom_dec fm k;
3456
let u = uexp fm k in
3457
if e <= u then begin
3458
vom_mult fm k;
3459
assert { mult (vom fm (k + 1)) u };
3460
mult_le (vom fm k) e u; mult_le (vom fm (k + 1)) e u
3461
end else begin
3462
let n = any int ensures { r = from_int result *. pow2r e } in
3463
pow2r_add u (e - u); pow2r_int (e - u); pow2r_pos u;
3464
let c = n * power 2 (e - u) in
3465
assert { r = from_int c *. pow2r u };
3466
scale_cmp (sig fm k) c (pow2r u);
3467
scale_cmp c (sig fm k + 1) (pow2r u);
3468
assert { c = sig fm k };
3469
assert { vom fm k = r }
3470
end
3471
{qed}
3472
Valid (49ms) (colibri2)
3473
let ghost
max_mult
(fm: format) (e: int) : unit
3474
requires { e <= umax fm }
3475
ensures { mult (vom fm (nb_sign fm - 2)) e }
3476
= {proof…}
3477
nb_sign_ge fm; vom_mult fm (nb_sign fm - 2);
3478
mult_le (vom fm (nb_sign fm - 2)) e (umax fm)
3479
{qed}
3480
Valid (1.9s) (colibri2 16) (split_vc 5) (depth 4)
3481
let ghost
round_fin_mult
(fm: format) (m: mode) (z: bool) (r: real) (e: int) : unit
3482
requires { mult r e /\ e <= umax fm }
3483
requires { is_finite (round_fin fm m z r) }
3484
ensures { mult (to_real (round_fin fm m z r)) e }
3485
= {proof…}
3486
nb_sign_ge fm; vom_zero fm; mult_zero e;
3487
if pure { 0.0 <=. r } then begin
3488
round_mag_range fm m r;
3489
let k = round_mag fm m r in
3490
if k <> 0 then begin
3491
of_mag_index fm m false k;
3492
if k < nb_sign fm - 1 then round_mag_mult fm m r e
3493
else max_mult fm e
3494
end
3495
end else begin
3496
mult_add r 0.0 e;
3497
round_mag_range fm (mirror m) (-. r);
3498
let k = round_mag fm (mirror m) (-. r) in
3499
if k <> 0 then begin
3500
of_mag_index fm (mirror m) true k;
3501
if k < nb_sign fm - 1 then begin
3502
round_mag_mult fm (mirror m) (-. r) e;
3503
mult_add (vom fm k) 0.0 e
3504
end else begin
3505
max_mult fm e; mult_add (vom fm (nb_sign fm - 2)) 0.0 e
3506
end
3507
end
3508
end
3509
{qed}

The bounds, for a positive interval

No float of [lo, hi] is a multiple of 2^(g+1), and bg is one of them, a multiple of 2^g

3515
predicate
witness
(lo hi bg: t) (g: int) =
3516
le_dz lo bg /\ le_dz bg hi /\ mult (to_real bg) g /\ qmin lo.fmt <= g /\
3517
forall f. le_dz lo f -> le_dz f hi -> not mult (to_real f) (g + 1)
3518
Valid (1.4s) (cvc5)
3519
let ghost
round_fin_nonpos
(fm: format) (m: mode) (z: bool) (r: real) : unit
3520
requires { r <=. 0.0 }
3521
ensures { index (round_fin fm m z r) <= 0 }
3522
= {proof…}
3523
vom_zero fm; round_mag_exact fm m 0;
3524
round_fin_le fm m z z r 0.0
3525
{qed}
3526
Valid (867ms) (colibri2 44) (cvc5 2) (split_vc 2) (depth 2)
3527
let ghost
core_pos
(fm: format) (m: mode) (zn: bool) (x y lo hi bg: t) (g: int) : unit
3528
requires { is_finite x /\ is_finite y /\ x.fmt = fm /\ y.fmt = fm /\ lo.fmt = fm }
3529
requires { 0 < index lo /\ index hi < nb_sign fm - 1 /\ witness lo hi bg g }
3530
requires { le_dz lo (round_fin fm m zn (to_real x +. to_real y)) }
3531
requires { le_dz (round_fin fm m zn (to_real x +. to_real y)) hi }
3532
ensures { -. pow2r (g + fm.sb) <. to_real x }
3533
ensures { to_real x <=. pow2r (g + fm.sb) -. pow2r g +. to_real bg }
3534
= {proof…}
3535
let vx = to_real x in
3536
let vy = to_real y in
3537
let r = vx +. vy in
3538
let z = round_fin fm m zn r in
3539
round_fin_facts fm m zn r;
3540
assert { is_finite z };
3541
if pure { r <=. 0.0 } then begin round_fin_nonpos fm m zn r; absurd end;
3542
pow2r_pos (g + fm.sb);
3543
if pure { vx <=. -. pow2r (g + fm.sb) } then begin
3544
big_float x g; big_float y g;
3545
mult_add vx vy (g + 1);
3546
round_fin_mult fm m zn r (g + 1);
3547
absurd
3548
end;
3549
let vb = to_real bg in
3550
if pure { pow2r (g + fm.sb) -. pow2r g +. vb <. vx } then begin
3551
assert { is_finite bg /\ not is_zero bg /\ is_positive bg };
3552
finite_sign bg;
3553
mult_zero g; mult_gap 0.0 vb g;
3554
assert { pow2r (g + fm.sb) <. vx };
3555
big_float x g;
3556
mult_odd vb g;
3557
pow2r_add (g + 1) (fm.sb - 1); pow2r_int (fm.sb - 1);
3558
assert { pow2r (g + fm.sb) = from_int (power 2 (fm.sb - 1)) *. pow2r (g + 1) };
3559
mult_one (g + 1); pow2r_succ g;
3560
mult_add (pow2r (g + fm.sb)) (vb +. pow2r g) (g + 1);
3561
mult_zero (g + 1);
3562
mult_add (pow2r (g + 1)) 0.0 (g + 1);
3563
mult_add (pow2r (g + fm.sb) +. (vb +. pow2r g)) (-. pow2r (g + 1)) (g + 1);
3564
assert { pow2r (g + fm.sb) -. pow2r g +. vb
3565
= pow2r (g + fm.sb) +. (vb +. pow2r g) +. (-. pow2r (g + 1)) };
3566
mult_gap (pow2r (g + fm.sb) -. pow2r g +. vb) vx (g + 1);
3567
if pure { pow2r (g + fm.sb) <=. vy \/ vy <=. -. pow2r (g + fm.sb) } then begin
3568
big_float y g;
3569
mult_add vx vy (g + 1);
3570
round_fin_mult fm m zn r (g + 1);
3571
absurd
3572
end;
3573
let w = vb +. pow2r g in
3574
assert { w <. r };
3575
let w' = round_fin fm m zn w in
3576
round_fin_le fm m zn zn w r;
3577
round_f_exact m bg;
3578
assert { bg = round_fin fm m false vb };
3579
round_fin_le fm m false zn vb w;
3580
round_fin_facts fm m zn w;
3581
assert { is_finite w' };
3582
round_fin_mult fm m zn w (g + 1);
3583
assert { le_dz lo w' /\ le_dz w' hi };
3584
assert { not mult (to_real w') (g + 1) };
3585
absurd
3586
end
3587
{qed}

The bounds as floats

The least float above -2^(g+sb)

3592
function
lower
(fm: format) (g: int) : t =
3593
let k = (g + 2 - qmin fm) * binade fm - 1 in
3594
of_index fm (-1 - (if k < nb_sign fm - 2 then k else nb_sign fm - 2))

The greatest float below 2^(g+sb) - 2^g + bg

3597
function
upper
(fm: format) (g: int) (bg: t) : t =
3598
round_fin fm RTN false (pow2r (g + fm.sb) -. pow2r g +. to_real bg)
3599
Valid (341ms) (colibri2 13) (cvc5 2) (split_vc) (depth 1)
3600
let ghost
lower_ok
(fm: format) (g: int) (x: t) : unit
3601
requires { is_finite x /\ x.fmt = fm /\ qmin fm <= g }
3602
requires { -. pow2r (g + fm.sb) <. to_real x }
3603
ensures { le_dz (lower fm g) x }
3604
= {proof…}
3605
nb_sign_ge fm; binade_ge_2 fm;
3606
let bn = binade fm in
3607
let k0 = (g + 2 - qmin fm) * bn - 1 in
3608
let d = g + 2 - qmin fm in
3609
assert { 2 <= d /\ d * bn >= bn };
3610
assert { 0 <= k0 };
3611
vom_s fm (g + 1) bn;
3612
assert { (g + 1 - qmin fm) * bn + bn = k0 + 1 };
3613
pow2r_add (g + 1) (fm.sb - 1); pow2r_int (fm.sb - 1);
3614
assert { from_int bn *. pow2r (g + 1) = pow2r (g + fm.sb) };
3615
match x.value with
3616
| Finite ng k ->
3617
if ng then begin
3618
assert { to_real x = -. vom fm k };
3619
if k > k0 then begin vom_le fm (k0 + 1) k; absurd end
3620
end
3621
| _ -> absurd
3622
end;
3623
let j = if k0 < nb_sign fm - 2 then k0 else nb_sign fm - 2 in
3624
of_index_range fm (-1 - j);
3625
index_range x;
3626
assert { -1 - j <= index x }
3627
{qed}
3628
Valid (47ms) (colibri2)
3629
let ghost
upper_ok
(x: t) (r: real) : unit
3630
requires { is_finite x /\ to_real x <=. r }
3631
ensures { le_dz x (round_fin x.fmt RTN false r) }
3632
= {proof…}
3633
round_f_exact RTN x;
3634
assert { ext x = Fin (to_real x) };
3635
round_fin_le x.fmt RTN (if is_positive x then false else true) false (to_real x) r
3636
{qed}

A finite sum comes from finite floats

  Valid (821ms) (colibri2 3) (cvc5) (split_vc) (depth 1)
3639
let ghost
add_fin
(m: mode) (x y: t) : unit
3640
requires { x.fmt = y.fmt /\ not is_nan (fp_add m x y) }
3641
requires { - nb_sign x.fmt < index (fp_add m x y) < nb_sign x.fmt - 1 }
3642
ensures { is_finite x /\ is_finite y }
3643
ensures { fp_add m x y = round_fin x.fmt m (add_zneg m x y) (to_real x +. to_real y) }
3644
= {proof…}
3645
match x.value, y.value with
3646
| Finite _ _, Finite _ _ -> ()
3647
| _ -> absurd
3648
end
3649
{qed}
3650
3651
predicate
pos_iv
(lo hi: t) =
3652
lo.fmt = hi.fmt /\ not is_nan lo /\ not is_nan hi /\
3653
0 < index lo <= index hi < nb_sign lo.fmt - 1
3654
3655
predicate
neg_iv
(lo hi: t) =
3656
lo.fmt = hi.fmt /\ not is_nan lo /\ not is_nan hi /\
3657
- nb_sign lo.fmt < index lo <= index hi < -1
3658
Valid (335ms) (colibri2)
3659
let lemma
pos_sound
(lo hi bg: t) (g: int) (m: mode) (x y: t)
3660
requires { pos_iv lo hi /\ witness lo hi bg g /\ x.fmt = lo.fmt /\ y.fmt = lo.fmt }
3661
requires { le_dz lo (fp_add m x y) /\ le_dz (fp_add m x y) hi }
3662
ensures { le_dz (lower lo.fmt g) x /\ le_dz x (upper lo.fmt g bg) }
3663
= {proof…}
3664
let fm = lo.fmt in
3665
add_fin m x y;
3666
core_pos fm m (add_zneg m x y) x y lo hi bg g;
3667
lower_ok fm g x;
3668
upper_ok x (pow2r (g + fm.sb) -. pow2r g +. to_real bg)
3669
{qed}
3670
Valid (1.4s) (colibri2 4) (cvc5 2) (split_vc 2) (depth 2)
3671
let ghost
neg_le
(a b: t) : unit
3672
requires { le_dz a b }
3673
ensures { le_dz (neg b) (neg a) /\ neg (neg a) = a /\ neg (neg b) = b }
3674
= {proof…}
3675
index_neg a; index_neg b;
3676
t_ext (neg (neg a)) a; t_ext (neg (neg b)) b
3677
{qed}
3678
Valid (1.6s) (colibri2 32) (cvc4) (cvc5 15) (split_vc 18) (depth 3)
3679
let lemma
neg_sound
(lo hi bg: t) (g: int) (m: mode) (x y: t)
3680
requires { neg_iv lo hi /\ witness (neg hi) (neg lo) bg g }
3681
requires { x.fmt = lo.fmt /\ y.fmt = lo.fmt }
3682
requires { le_dz lo (fp_add m x y) /\ le_dz (fp_add m x y) hi }
3683
ensures { le_dz (neg (upper lo.fmt g bg)) x /\ le_dz x (neg (lower lo.fmt g)) }
3684
= {proof…}
3685
let fm = lo.fmt in
3686
add_fin m x y;
3687
let zn = add_zneg m x y in
3688
let r = to_real x +. to_real y in
3689
round_f_neg fm (mirror m) (not zn) (Fin r);
3690
assert { eneg (Fin r) = Fin (-. r) };
3691
assert { mirror (mirror m) = m };
3692
if zn then assert { round_f fm m (not (not zn)) (Fin r) = round_f fm m zn (Fin r) }
3693
else assert { round_f fm m (not (not zn)) (Fin r) = round_f fm m zn (Fin r) };
3694
assert { round_f fm (mirror m) (not zn) (Fin (-. r)) = neg (round_f fm m zn (Fin r)) };
3695
assert { round_fin fm (mirror m) (not zn) (-. r) = neg (round_fin fm m zn r) };
3696
assert { to_real (neg x) = -. to_real x /\ to_real (neg y) = -. to_real y };
3697
assert { to_real (neg x) +. to_real (neg y) = -. r };
3698
let z = fp_add m x y in
3699
assert { round_fin fm (mirror m) (not zn) (to_real (neg x) +. to_real (neg y)) = neg z };
3700
neg_le lo z; neg_le z hi;
3701
index_neg x; index_neg y; index_neg lo; index_neg hi;
3702
assert { 0 < index (neg hi) /\ index (neg lo) < nb_sign fm - 1 };
3703
core_pos fm (mirror m) (not zn) (neg x) (neg y) (neg hi) (neg lo) bg g;
3704
lower_ok fm g (neg x);
3705
upper_ok (neg x) (pow2r (g + fm.sb) -. pow2r g +. to_real bg);
3706
neg_le (lower fm g) (neg x);
3707
neg_le (neg x) (upper fm g bg);
3708
neg_le x x
3709
{qed}

The computation

  Valid (67ms) (colibri2)
3713
let
uexp_p
(fm: format) (k: int) : int
3714
requires { 0 <= k }
3715
ensures { result = uexp fm k }
3716
= let bn = binade_p fm in
3717
let e = Zarith.fdiv k bn in
3718
{proof…}
3719
binade_ge_2 fm;
3720
assert { k = div k bn * bn + mod k bn /\ 0 <= mod k bn < bn };
3721
if pure { e < div k bn } then assert { (e + 1) * bn <= div k bn * bn }
3722
else if pure { e > div k bn } then assert { (div k bn + 1) * bn <= e * bn };
3723
assert { e = div k bn };
3724
{qed}
3725
qmin_p fm + (if e = 0 then 0 else e - 1)
3726
Valid (45ms) (colibri2)
3727
let
sig_p
(fm: format) (k: int) : int
3728
requires { 0 <= k }
3729
ensures { result = sig fm k }
3730
= k - (uexp_p fm k - qmin_p fm) * binade_p fm

No multiple of q in [a, b]: f q < a <= b < (f+1) q

3733
predicate
gap
(a b q: int) = 0 < q /\ exists f. f * q < a /\ b < f * q + q
3734
Valid (59ms) (colibri2 5) (split_vc) (depth 1)
3735
let ghost
gap_at
(a b q s n: int) : unit
3736
requires { gap a b q /\ a <= s <= b }
3737
ensures { s <> n * q }
3738
= {proof…}
3739
let f = any int ensures { result * q < a /\ b < result * q + q } in
3740
if s = n * q then begin
3741
mul_lt_cancel n f q; assert { n * q <= f * q }; absurd
3742
end
3743
{qed}

The largest t such that [a, b] holds a multiple c of 2^t

  Valid (350ms) (colibri2 24) (split_vc 8) (depth 2)
3746
let
maxtz
(a b: int) : (int, int)
3747
requires { 0 < a <= b }
3748
returns { (t, c) -> 0 <= t /\ a <= c <= b /\ (exists n. c = n * power 2 t) /\
3749
gap a b (power 2 (t + 1)) }
3750
= let t = ref 0 in
3751
let q = ref 2 in
3752
let c = ref b in
3753
{proof…}
3754
assert { b = b * power 2 0 /\ power 2 1 = 2 };
3755
{qed}
3756
let f = ref (Zarith.fdiv b 2) in
3757
while !f * !q >= a do
3758
invariant { 0 <= !t /\ !q = power 2 (!t + 1) /\ a <= !c <= b }
3759
invariant { exists n. !c = n * power 2 !t }
3760
invariant { !f * !q <= b < !f * !q + !q }
3761
variant { b - !q }
3762
let fv = !f in
3763
{proof…}
3764
assert { 0 < !q };
3765
assert { 1 <= fv by fv <= 0 -> fv * !q <= 0 * !q };
3766
assert { !q <= fv * !q by 1 * !q <= fv * !q };
3767
assert { power 2 (!t + 2) = 2 * power 2 (!t + 1) };
3768
{qed}
3769
c := fv * !q;
3770
t := !t + 1;
3771
q := 2 * !q;
3772
{proof…}
3773
assert { !c = fv * power 2 !t };
3774
{qed}
3775
f := Zarith.fdiv b !q
3776
done;
3777
{proof…}
3778
assert { 0 < !q /\ !f * !q <= b < !f * !q + !q /\ !f * !q < a };
3779
assert { power 2 (!t + 1) = !q };
3780
{qed}
3781
(!t, !c)

No float of the positive [lo, hi] is a multiple of 2^(g+1)

3784
function
mag
(x: t) : int = match x.value with Finite _ k -> k | _ -> 0 end
3785
3786
function
sfirst
(lo hi: t) : int =
3787
if uexp lo.fmt (mag lo) < uexp lo.fmt (mag hi) then binade lo.fmt
3788
else sig lo.fmt (mag lo)
3789
Valid (1.5s) (colibri2 16) (cvc4) (cvc5 11) (split_vc 6) (depth 2)
3790
let lemma
nomult
(lo hi f: t) (g: int)
3791
requires { pos_iv lo hi /\ le_dz lo f /\ le_dz f hi }
3792
requires { uexp lo.fmt (mag hi) <= g }
3793
requires { gap (sfirst lo hi) (sig lo.fmt (mag hi)) (power 2 (g - uexp lo.fmt (mag hi) + 1)) }
3794
ensures { not mult (to_real f) (g + 1) }
3795
= {proof…}
3796
let fm = lo.fmt in
3797
let k1 = mag lo in
3798
let k2 = mag hi in
3799
let u2 = uexp fm k2 in
3800
let t = g - u2 in
3801
let s1 = sfirst lo hi in
3802
let s2 = sig fm k2 in
3803
let q = pure { power 2 (t + 1) } in
3804
binade_ge_2 fm;
3805
match f.value with
3806
| Finite _ k ->
3807
vom_dec fm k; vom_dec fm k1; vom_dec fm k2;
3808
uexp_mono fm k1 k; uexp_mono fm k k2;
3809
vom_mult fm k; vom_pos fm k;
3810
if pure { mult (to_real f) (g + 1) } then begin
3811
let m = any int ensures { vom fm k = from_int result *. pow2r (g + 1) } in
3812
if uexp fm k = u2 then begin
3813
assert { k1 <= k <= k2 };
3814
assert { sig fm k - sig fm k2 = k - k2 };
3815
assert { uexp fm k1 = u2 -> sig fm k - sig fm k1 = k - k1 };
3816
assert { s1 <= sig fm k <= s2 };
3817
pow2r_add u2 (t + 1); pow2r_int (t + 1); pow2r_pos u2;
3818
assert { vom fm k = from_int (m * q) *. pow2r u2 };
3819
scale_cmp (sig fm k) (m * q) (pow2r u2);
3820
gap_at s1 s2 q (sig fm k) m;
3821
absurd
3822
end else begin
3823
assert { uexp fm k1 < u2 /\ s1 = binade fm };
3824
if t + 1 <= fm.sb - 1 then begin
3825
let n0 = pure { power 2 (fm.sb - 2 - t) } in
3826
assert { binade fm = n0 * q };
3827
gap_at s1 s2 q (binade fm) n0;
3828
absurd
3829
end;
3830
pow2r_le (uexp fm k + fm.sb) (g + 1);
3831
mult_zero (g + 1); mult_gap 0.0 (vom fm k) (g + 1);
3832
absurd
3833
end
3834
end
3835
| _ -> absurd
3836
end
3837
{qed}

The bounds for a positive interval

  Valid (6.4s) (colibri2 33) (cvc4 2) (cvc5 6) (split_vc 9) (depth 5)
3840
let
pos_bounds
(lo hi: t) : (t, t)
3841
requires { pos_iv lo hi }
3842
returns { (a, b) -> a.fmt = lo.fmt /\ b.fmt = lo.fmt }
3843
returns { (a, b) -> exists g bg. witness lo hi bg g /\
3844
a = lower lo.fmt g /\ b = upper lo.fmt g bg }
3845
= let fm = lo.fmt in
3846
match lo.value, hi.value with
3847
| Finite _ k1, Finite _ k2 ->
3848
let bn = binade_p fm in
3849
let q = qmin_p fm in
3850
let u1 = uexp_p fm k1 in
3851
let u2 = uexp_p fm k2 in
3852
let s2 = sig_p fm k2 in
3853
let s1 = if u1 < u2 then bn else sig_p fm k1 in
3854
{proof…}
3855
assert { lo.value = Finite false k1 /\ hi.value = Finite false k2 };
3856
binade_ge_2 fm; nb_sign_ge fm;
3857
vom_dec fm k1; vom_dec fm k2; uexp_mono fm k1 k2;
3858
assert { 0 < s1 <= s2 };
3859
{qed}
3860
let (t, c) = maxtz s1 s2 in
3861
let g = u2 + t in
3862
let ghost kb = (u2 - q) * bn + c in
3863
{proof…}
3864
if u1 < u2 then
3865
assert { (u1 - q + 1) * bn <= (u2 - q) * bn
3866
by (u2 - q) * bn = (u1 - q + 1) * bn + (u2 - u1 - 1) * bn };
3867
assert { k1 <= kb <= k2 };
3868
{qed}
3869
let ghost bg = mk fm (Finite false kb) in
3870
let nb = nb_sign_p fm in
3871
let kl = (g + 2 - q) * bn - 1 in
3872
let kl = if kl < nb - 2 then kl else nb - 2 in
3873
let a = of_index_p fm (-1 - kl) in
3874
let d = { dm = pow2_int (t + fm.sb) - pow2_int t + c; de = u2 } in
3875
let b = round_d fm RTN false d in
3876
{proof…}
3877
vom_s fm u2 c;
3878
let ghost n = any int ensures { c = result * power 2 t } in
3879
pow2r_add u2 t; pow2r_int t; pow2r_add u2 (t + fm.sb); pow2r_int (t + fm.sb);
3880
assert { to_real bg = from_int c *. pow2r u2 };
3881
assert { to_real bg = from_int n *. pow2r g };
3882
assert { dval d = pow2r (g + fm.sb) -. pow2r g +. to_real bg };
3883
assert { mag lo = k1 /\ mag hi = k2 /\ sfirst lo hi = s1 /\ sig fm k2 = s2 };
3884
assert { g - uexp fm (mag hi) + 1 = t + 1 };
3885
assert { gap (sfirst lo hi) (sig lo.fmt (mag hi)) (power 2 (g - uexp lo.fmt (mag hi) + 1)) };
3886
assert { forall f. le_dz lo f -> le_dz f hi -> not mult (to_real f) (g + 1) };
3887
assert { witness lo hi bg g };
3888
assert { a = lower lo.fmt g };
3889
assert { b = upper lo.fmt g bg };
3890
{qed}
3891
(a, b)
3892
| _ -> absurd
3893
end
3894
3895
predicate
one_sign
(lo hi: t) = pos_iv lo hi \/ neg_iv lo hi
3896
Valid (86ms) (colibri2)
3897
let ghost
neg_fmt
(x: t) : unit
3898
ensures { (neg x).fmt = x.fmt }
3899
= ()

The bounds [a, b] of x when x + y rounds into [lo, hi] in any mode; None when [lo, hi] holds a zero, an infinity or a NaN, or is empty or of two formats

  Valid (1.2s) (colibri2 9) (cvc5 4) (split_vc 2) (depth 2)
3904
let
add_bounds
(lo hi: t) : option (t, t)
3905
ensures { match result with
3906
| None -> not one_sign lo hi
3907
| Some (a, b) -> one_sign lo hi /\ a.fmt = lo.fmt /\ b.fmt = lo.fmt /\
3908
forall m x y. x.fmt = lo.fmt -> y.fmt = lo.fmt ->
3909
le_dz lo (fp_add m x y) -> le_dz (fp_add m x y) hi -> le_dz a x /\ le_dz x b
3910
end }
3911
= if not (eq_format lo.fmt hi.fmt) || is_nan lo || is_nan hi then None
3912
else
3913
let nb = nb_sign_p lo.fmt in
3914
let il = index_p lo in
3915
let ih = index_p hi in
3916
if ih < il then None
3917
else if 0 < il && ih < nb - 1 then Some (pos_bounds lo hi)
3918
else if - nb < il && ih < -1 then begin
3919
{proof…}
3920
assert { pos_iv (neg hi) (neg lo) };
3921
{qed}
3922
let (a, b) = pos_bounds (neg hi) (neg lo) in
3923
{proof…}
3924
neg_fmt hi; neg_fmt a; neg_fmt b;
3925
let ghost g = any int ensures { exists bg. witness (neg hi) (neg lo) bg result /\
3926
a = lower lo.fmt result /\ b = upper lo.fmt result bg } in
3927
let ghost bg = any t ensures { witness (neg hi) (neg lo) result g /\
3928
a = lower lo.fmt g /\ b = upper lo.fmt g result } in
3929
let lemma pt (m: mode) (x y: t) : unit
3930
requires { x.fmt = lo.fmt /\ y.fmt = lo.fmt }
3931
requires { le_dz lo (fp_add m x y) /\ le_dz (fp_add m x y) hi }
3932
ensures { le_dz (neg b) x /\ le_dz x (neg a) }
3933
= neg_sound lo hi bg g m x y in
3934
{qed}
3935
Some (neg b, neg a)
3936
end else None
3937
end