library colibrilib.fbin — module AddBoundB. 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.
module AddBound3310use int.Int3311use int.Power3312use int.EuclideanDivision3313use real.RealInfix3314use real.FromInt3315use option.Option3316use ref.Ref3317use colibrilib.fp.Widen3318use colibrilib.fp.Ereal3319use colibrilib.zarith.Z as Zarith3320use Pow2r3321use Format3322use Float3323use Round3324use Impl3325
r is a multiple of 2^e
predicate mult (r: real) (e: int) = exists n: int. r = from_int n *. pow2r e3328Valid (42ms) (colibri2)3329let ghost mult_le (r: real) (e e': int) : unit3330requires { e <= e' /\ mult r e' }3331ensures { mult r e }3332= {proof…}3333let n = any int ensures { r = from_int result *. pow2r e' } in3334pow2r_add e (e' - e); pow2r_int (e' - e);3335assert { r = from_int (n * power 2 (e' - e)) *. pow2r e }3336{qed}3337Valid (44ms) (colibri2 4) (cvc5) (split_vc) (depth 1)3338let ghost mult_add (a b: real) (e: int) : unit3339requires { mult a e /\ mult b e }3340ensures { mult (a +. b) e /\ mult (-. a) e }3341= {proof…}3342let n = any int ensures { a = from_int result *. pow2r e } in3343let k = any int ensures { b = from_int result *. pow2r e } in3344assert { a +. b = from_int (n + k) *. pow2r e };3345assert { -. a = from_int (- n) *. pow2r e }3346{qed}3347Valid (36ms) (colibri2)3348let ghost mult_zero (e: int) : unit3349ensures { mult 0.0 e }3350= {proof…} assert { 0.0 = from_int 0 *. pow2r e } {qed}3351Valid (37ms) (colibri2)3352let ghost mult_one (e: int) : unit3353ensures { mult (pow2r e) e }3354= {proof…} assert { pow2r e = from_int 1 *. pow2r e } {qed}3355
Two multiples of 2^e differ by at least 2^e
Valid (51ms) (colibri2)let ghost mult_gap (a b: real) (e: int) : unit3358requires { mult a e /\ mult b e /\ a <. b }3359ensures { a +. pow2r e <=. b }3360= {proof…}3361let n = any int ensures { a = from_int result *. pow2r e } in3362let k = any int ensures { b = from_int result *. pow2r e } in3363pow2r_pos e; scale_cmp n k (pow2r e);3364assert { a +. pow2r e = from_int (n + 1) *. pow2r e };3365scale_cmp (n + 1) k (pow2r e)3366{qed}3367
r = n 2^e with n odd: r + 2^e is a multiple of 2^(e+1)
Valid (62ms) (colibri2)let ghost mult_odd (r: real) (e: int) : unit3370requires { mult r e /\ not mult r (e + 1) }3371ensures { mult (r +. pow2r e) (e + 1) }3372= {proof…}3373let n = any int ensures { r = from_int result *. pow2r e } in3374pow2r_succ e;3375if mod n 2 = 0 then begin3376assert { n = 2 * div n 2 };3377assert { r = from_int (div n 2) *. pow2r (e + 1) };3378absurd3379end else begin3380assert { n + 1 = 2 * div (n + 1) 2 };3381assert { r +. pow2r e = from_int (n + 1) *. pow2r e };3382assert { r +. pow2r e = from_int (div (n + 1) 2) *. pow2r (e + 1) }3383end3384{qed}3385
A magnitude is a multiple of its ulp and below 2^(u+sb)
Valid (53ms) (colibri2)let ghost vom_mult (fm: format) (k: int) : unit3390requires { 0 <= k }3391ensures { mult (vom fm k) (uexp fm k) /\ qmin fm <= uexp fm k }3392ensures { vom fm k <. pow2r (uexp fm k + fm.sb) }3393= {proof…}3394vom_dec fm k; binade_ge_2 fm;3395let u = uexp fm k in3396pow2r_add u fm.sb; pow2r_int fm.sb; pow2r_pos u;3397assert { power 2 fm.sb = 2 * binade fm };3398scale_cmp (sig fm k) (2 * binade fm) (pow2r u)3399{qed}3400Valid (316ms) (colibri2 4) (cvc5) (split_vc) (depth 1)3401let ghost uexp_mono (fm: format) (k l: int) : unit3402requires { 0 <= k <= l }3403ensures { uexp fm k <= uexp fm l }3404= {proof…}3405binade_ge_2 fm;3406let bn = binade fm in3407assert { k = div k bn * bn + mod k bn /\ 0 <= mod k bn < bn };3408assert { l = div l bn * bn + mod l bn /\ 0 <= mod l bn < bn };3409if pure { div l bn < div k bn } then begin3410assert { (div l bn + 1) * bn <= div k bn * bn };3411absurd3412end3413{qed}3414
The ulp of the largest finite float
function umax (fm: format) : int = uexp fm (nb_sign fm - 2)3417
A float of magnitude at least 2^(e+sb) is a multiple of 2^(e+1)
Valid (427ms) (cvc5)let ghost big_mag (fm: format) (k e: int) : unit3421requires { 0 <= k <= nb_sign fm - 2 /\ pow2r (e + fm.sb) <=. vom fm k }3422ensures { mult (vom fm k) (e + 1) /\ e + 1 <= umax fm }3423= {proof…}3424vom_mult fm k; nb_sign_ge fm; uexp_mono fm k (nb_sign fm - 2);3425if uexp fm k <= e then begin3426pow2r_le (uexp fm k + fm.sb) (e + fm.sb); absurd3427end;3428mult_le (vom fm k) (e + 1) (uexp fm k)3429{qed}3430Valid (809ms) (colibri2 3) (cvc4) (cvc5 2) (split_vc 2) (depth 2)3431let ghost big_float (f: t) (e: int) : unit3432requires { is_finite f }3433requires { pow2r (e + f.fmt.sb) <=. to_real f \/ to_real f <=. -. pow2r (e + f.fmt.sb) }3434ensures { mult (to_real f) (e + 1) /\ e + 1 <= umax f.fmt }3435= {proof…}3436let fm = f.fmt in3437nb_sign_ge fm; pow2r_pos (e + fm.sb);3438match f.value with3439| Finite ng k ->3440vom_zero fm; vom_le fm 0 k;3441big_mag fm k e;3442if ng then mult_add (vom fm k) 0.0 (e + 1)3443| _ -> absurd3444end3445{qed}3446
The rounding keeps the multiples of 2^e
Valid (393ms) (colibri2 14) (cvc5) (split_vc) (depth 1)let ghost round_mag_mult (fm: format) (m: mode) (r: real) (e: int) : unit3449requires { 0.0 <=. r /\ mult r e }3450ensures { mult (vom fm (round_mag fm m r)) e }3451= {proof…}3452let k = kdn fm r in3453round_mag_range fm m r;3454vom_dec fm k;3455let u = uexp fm k in3456if e <= u then begin3457vom_mult fm k;3458assert { mult (vom fm (k + 1)) u };3459mult_le (vom fm k) e u; mult_le (vom fm (k + 1)) e u3460end else begin3461let n = any int ensures { r = from_int result *. pow2r e } in3462pow2r_add u (e - u); pow2r_int (e - u); pow2r_pos u;3463let c = n * power 2 (e - u) in3464assert { r = from_int c *. pow2r u };3465scale_cmp (sig fm k) c (pow2r u);3466scale_cmp c (sig fm k + 1) (pow2r u);3467assert { c = sig fm k };3468assert { vom fm k = r }3469end3470{qed}3471Valid (49ms) (colibri2)3472let ghost max_mult (fm: format) (e: int) : unit3473requires { e <= umax fm }3474ensures { mult (vom fm (nb_sign fm - 2)) e }3475= {proof…}3476nb_sign_ge fm; vom_mult fm (nb_sign fm - 2);3477mult_le (vom fm (nb_sign fm - 2)) e (umax fm)3478{qed}3479Valid (1.9s) (colibri2 16) (split_vc 5) (depth 4)3480let ghost round_fin_mult (fm: format) (m: mode) (z: bool) (r: real) (e: int) : unit3481requires { mult r e /\ e <= umax fm }3482requires { is_finite (round_fin fm m z r) }3483ensures { mult (to_real (round_fin fm m z r)) e }3484= {proof…}3485nb_sign_ge fm; vom_zero fm; mult_zero e;3486if pure { 0.0 <=. r } then begin3487round_mag_range fm m r;3488let k = round_mag fm m r in3489if k <> 0 then begin3490of_mag_index fm m false k;3491if k < nb_sign fm - 1 then round_mag_mult fm m r e3492else max_mult fm e3493end3494end else begin3495mult_add r 0.0 e;3496round_mag_range fm (mirror m) (-. r);3497let k = round_mag fm (mirror m) (-. r) in3498if k <> 0 then begin3499of_mag_index fm (mirror m) true k;3500if k < nb_sign fm - 1 then begin3501round_mag_mult fm (mirror m) (-. r) e;3502mult_add (vom fm k) 0.0 e3503end else begin3504max_mult fm e; mult_add (vom fm (nb_sign fm - 2)) 0.0 e3505end3506end3507end3508{qed}3509
No float of [lo, hi] is a multiple of 2^(g+1), and bg is one of them, a multiple of 2^g
predicate witness (lo hi bg: t) (g: int) =3515le_dz lo bg /\ le_dz bg hi /\ mult (to_real bg) g /\ qmin lo.fmt <= g /\3516forall f. le_dz lo f -> le_dz f hi -> not mult (to_real f) (g + 1)3517Valid (1.4s) (cvc5)3518let ghost round_fin_nonpos (fm: format) (m: mode) (z: bool) (r: real) : unit3519requires { r <=. 0.0 }3520ensures { index (round_fin fm m z r) <= 0 }3521= {proof…}3522vom_zero fm; round_mag_exact fm m 0;3523round_fin_le fm m z z r 0.03524{qed}3525Valid (867ms) (colibri2 44) (cvc5 2) (split_vc 2) (depth 2)3526let ghost core_pos (fm: format) (m: mode) (zn: bool) (x y lo hi bg: t) (g: int) : unit3527requires { is_finite x /\ is_finite y /\ x.fmt = fm /\ y.fmt = fm /\ lo.fmt = fm }3528requires { 0 < index lo /\ index hi < nb_sign fm - 1 /\ witness lo hi bg g }3529requires { le_dz lo (round_fin fm m zn (to_real x +. to_real y)) }3530requires { le_dz (round_fin fm m zn (to_real x +. to_real y)) hi }3531ensures { -. pow2r (g + fm.sb) <. to_real x }3532ensures { to_real x <=. pow2r (g + fm.sb) -. pow2r g +. to_real bg }3533= {proof…}3534let vx = to_real x in3535let vy = to_real y in3536let r = vx +. vy in3537let z = round_fin fm m zn r in3538round_fin_facts fm m zn r;3539assert { is_finite z };3540if pure { r <=. 0.0 } then begin round_fin_nonpos fm m zn r; absurd end;3541pow2r_pos (g + fm.sb);3542if pure { vx <=. -. pow2r (g + fm.sb) } then begin3543big_float x g; big_float y g;3544mult_add vx vy (g + 1);3545round_fin_mult fm m zn r (g + 1);3546absurd3547end;3548let vb = to_real bg in3549if pure { pow2r (g + fm.sb) -. pow2r g +. vb <. vx } then begin3550assert { is_finite bg /\ not is_zero bg /\ is_positive bg };3551finite_sign bg;3552mult_zero g; mult_gap 0.0 vb g;3553assert { pow2r (g + fm.sb) <. vx };3554big_float x g;3555mult_odd vb g;3556pow2r_add (g + 1) (fm.sb - 1); pow2r_int (fm.sb - 1);3557assert { pow2r (g + fm.sb) = from_int (power 2 (fm.sb - 1)) *. pow2r (g + 1) };3558mult_one (g + 1); pow2r_succ g;3559mult_add (pow2r (g + fm.sb)) (vb +. pow2r g) (g + 1);3560mult_zero (g + 1);3561mult_add (pow2r (g + 1)) 0.0 (g + 1);3562mult_add (pow2r (g + fm.sb) +. (vb +. pow2r g)) (-. pow2r (g + 1)) (g + 1);3563assert { pow2r (g + fm.sb) -. pow2r g +. vb3564= pow2r (g + fm.sb) +. (vb +. pow2r g) +. (-. pow2r (g + 1)) };3565mult_gap (pow2r (g + fm.sb) -. pow2r g +. vb) vx (g + 1);3566if pure { pow2r (g + fm.sb) <=. vy \/ vy <=. -. pow2r (g + fm.sb) } then begin3567big_float y g;3568mult_add vx vy (g + 1);3569round_fin_mult fm m zn r (g + 1);3570absurd3571end;3572let w = vb +. pow2r g in3573assert { w <. r };3574let w' = round_fin fm m zn w in3575round_fin_le fm m zn zn w r;3576round_f_exact m bg;3577assert { bg = round_fin fm m false vb };3578round_fin_le fm m false zn vb w;3579round_fin_facts fm m zn w;3580assert { is_finite w' };3581round_fin_mult fm m zn w (g + 1);3582assert { le_dz lo w' /\ le_dz w' hi };3583assert { not mult (to_real w') (g + 1) };3584absurd3585end3586{qed}3587
The least float above -2^(g+sb)
function lower (fm: format) (g: int) : t =3592let k = (g + 2 - qmin fm) * binade fm - 1 in3593of_index fm (-1 - (if k < nb_sign fm - 2 then k else nb_sign fm - 2))3594
The greatest float below 2^(g+sb) - 2^g + bg
function upper (fm: format) (g: int) (bg: t) : t =3597round_fin fm RTN false (pow2r (g + fm.sb) -. pow2r g +. to_real bg)3598Valid (341ms) (colibri2 13) (cvc5 2) (split_vc) (depth 1)3599let ghost lower_ok (fm: format) (g: int) (x: t) : unit3600requires { is_finite x /\ x.fmt = fm /\ qmin fm <= g }3601requires { -. pow2r (g + fm.sb) <. to_real x }3602ensures { le_dz (lower fm g) x }3603= {proof…}3604nb_sign_ge fm; binade_ge_2 fm;3605let bn = binade fm in3606let k0 = (g + 2 - qmin fm) * bn - 1 in3607let d = g + 2 - qmin fm in3608assert { 2 <= d /\ d * bn >= bn };3609assert { 0 <= k0 };3610vom_s fm (g + 1) bn;3611assert { (g + 1 - qmin fm) * bn + bn = k0 + 1 };3612pow2r_add (g + 1) (fm.sb - 1); pow2r_int (fm.sb - 1);3613assert { from_int bn *. pow2r (g + 1) = pow2r (g + fm.sb) };3614match x.value with3615| Finite ng k ->3616if ng then begin3617assert { to_real x = -. vom fm k };3618if k > k0 then begin vom_le fm (k0 + 1) k; absurd end3619end3620| _ -> absurd3621end;3622let j = if k0 < nb_sign fm - 2 then k0 else nb_sign fm - 2 in3623of_index_range fm (-1 - j);3624index_range x;3625assert { -1 - j <= index x }3626{qed}3627Valid (47ms) (colibri2)3628let ghost upper_ok (x: t) (r: real) : unit3629requires { is_finite x /\ to_real x <=. r }3630ensures { le_dz x (round_fin x.fmt RTN false r) }3631= {proof…}3632round_f_exact RTN x;3633assert { ext x = Fin (to_real x) };3634round_fin_le x.fmt RTN (if is_positive x then false else true) false (to_real x) r3635{qed}3636
A finite sum comes from finite floats
Valid (821ms) (colibri2 3) (cvc5) (split_vc) (depth 1)let ghost add_fin (m: mode) (x y: t) : unit3639requires { x.fmt = y.fmt /\ not is_nan (fp_add m x y) }3640requires { - nb_sign x.fmt < index (fp_add m x y) < nb_sign x.fmt - 1 }3641ensures { is_finite x /\ is_finite y }3642ensures { fp_add m x y = round_fin x.fmt m (add_zneg m x y) (to_real x +. to_real y) }3643= {proof…}3644match x.value, y.value with3645| Finite _ _, Finite _ _ -> ()3646| _ -> absurd3647end3648{qed}36493650predicate pos_iv (lo hi: t) =3651lo.fmt = hi.fmt /\ not is_nan lo /\ not is_nan hi /\36520 < index lo <= index hi < nb_sign lo.fmt - 136533654predicate neg_iv (lo hi: t) =3655lo.fmt = hi.fmt /\ not is_nan lo /\ not is_nan hi /\3656- nb_sign lo.fmt < index lo <= index hi < -13657Valid (335ms) (colibri2)3658let lemma pos_sound (lo hi bg: t) (g: int) (m: mode) (x y: t)3659requires { pos_iv lo hi /\ witness lo hi bg g /\ x.fmt = lo.fmt /\ y.fmt = lo.fmt }3660requires { le_dz lo (fp_add m x y) /\ le_dz (fp_add m x y) hi }3661ensures { le_dz (lower lo.fmt g) x /\ le_dz x (upper lo.fmt g bg) }3662= {proof…}3663let fm = lo.fmt in3664add_fin m x y;3665core_pos fm m (add_zneg m x y) x y lo hi bg g;3666lower_ok fm g x;3667upper_ok x (pow2r (g + fm.sb) -. pow2r g +. to_real bg)3668{qed}3669Valid (1.4s) (colibri2 4) (cvc5 2) (split_vc 2) (depth 2)3670let ghost neg_le (a b: t) : unit3671requires { le_dz a b }3672ensures { le_dz (neg b) (neg a) /\ neg (neg a) = a /\ neg (neg b) = b }3673= {proof…}3674index_neg a; index_neg b;3675t_ext (neg (neg a)) a; t_ext (neg (neg b)) b3676{qed}3677Valid (1.6s) (colibri2 32) (cvc4) (cvc5 15) (split_vc 18) (depth 3)3678let lemma neg_sound (lo hi bg: t) (g: int) (m: mode) (x y: t)3679requires { neg_iv lo hi /\ witness (neg hi) (neg lo) bg g }3680requires { x.fmt = lo.fmt /\ y.fmt = lo.fmt }3681requires { le_dz lo (fp_add m x y) /\ le_dz (fp_add m x y) hi }3682ensures { le_dz (neg (upper lo.fmt g bg)) x /\ le_dz x (neg (lower lo.fmt g)) }3683= {proof…}3684let fm = lo.fmt in3685add_fin m x y;3686let zn = add_zneg m x y in3687let r = to_real x +. to_real y in3688round_f_neg fm (mirror m) (not zn) (Fin r);3689assert { eneg (Fin r) = Fin (-. r) };3690assert { mirror (mirror m) = m };3691if zn then assert { round_f fm m (not (not zn)) (Fin r) = round_f fm m zn (Fin r) }3692else assert { round_f fm m (not (not zn)) (Fin r) = round_f fm m zn (Fin r) };3693assert { round_f fm (mirror m) (not zn) (Fin (-. r)) = neg (round_f fm m zn (Fin r)) };3694assert { round_fin fm (mirror m) (not zn) (-. r) = neg (round_fin fm m zn r) };3695assert { to_real (neg x) = -. to_real x /\ to_real (neg y) = -. to_real y };3696assert { to_real (neg x) +. to_real (neg y) = -. r };3697let z = fp_add m x y in3698assert { round_fin fm (mirror m) (not zn) (to_real (neg x) +. to_real (neg y)) = neg z };3699neg_le lo z; neg_le z hi;3700index_neg x; index_neg y; index_neg lo; index_neg hi;3701assert { 0 < index (neg hi) /\ index (neg lo) < nb_sign fm - 1 };3702core_pos fm (mirror m) (not zn) (neg x) (neg y) (neg hi) (neg lo) bg g;3703lower_ok fm g (neg x);3704upper_ok (neg x) (pow2r (g + fm.sb) -. pow2r g +. to_real bg);3705neg_le (lower fm g) (neg x);3706neg_le (neg x) (upper fm g bg);3707neg_le x x3708{qed}3709
Valid (67ms) (colibri2)let uexp_p (fm: format) (k: int) : int3713requires { 0 <= k }3714ensures { result = uexp fm k }3715= let bn = binade_p fm in3716let e = Zarith.fdiv k bn in3717{proof…}3718binade_ge_2 fm;3719assert { k = div k bn * bn + mod k bn /\ 0 <= mod k bn < bn };3720if pure { e < div k bn } then assert { (e + 1) * bn <= div k bn * bn }3721else if pure { e > div k bn } then assert { (div k bn + 1) * bn <= e * bn };3722assert { e = div k bn };3723{qed}3724qmin_p fm + (if e = 0 then 0 else e - 1)3725Valid (45ms) (colibri2)3726let sig_p (fm: format) (k: int) : int3727requires { 0 <= k }3728ensures { result = sig fm k }3729= k - (uexp_p fm k - qmin_p fm) * binade_p fm3730
No multiple of q in [a, b]: f q < a <= b < (f+1) q
predicate gap (a b q: int) = 0 < q /\ exists f. f * q < a /\ b < f * q + q3733Valid (59ms) (colibri2 5) (split_vc) (depth 1)3734let ghost gap_at (a b q s n: int) : unit3735requires { gap a b q /\ a <= s <= b }3736ensures { s <> n * q }3737= {proof…}3738let f = any int ensures { result * q < a /\ b < result * q + q } in3739if s = n * q then begin3740mul_lt_cancel n f q; assert { n * q <= f * q }; absurd3741end3742{qed}3743
The largest t such that [a, b] holds a multiple c of 2^t
Valid (350ms) (colibri2 24) (split_vc 8) (depth 2)let maxtz (a b: int) : (int, int)3746requires { 0 < a <= b }3747returns { (t, c) -> 0 <= t /\ a <= c <= b /\ (exists n. c = n * power 2 t) /\3748gap a b (power 2 (t + 1)) }3749= let t = ref 0 in3750let q = ref 2 in3751let c = ref b in3752{proof…}3753assert { b = b * power 2 0 /\ power 2 1 = 2 };3754{qed}3755let f = ref (Zarith.fdiv b 2) in3756while !f * !q >= a do3757invariant { 0 <= !t /\ !q = power 2 (!t + 1) /\ a <= !c <= b }3758invariant { exists n. !c = n * power 2 !t }3759invariant { !f * !q <= b < !f * !q + !q }3760variant { b - !q }3761let fv = !f in3762{proof…}3763assert { 0 < !q };3764assert { 1 <= fv by fv <= 0 -> fv * !q <= 0 * !q };3765assert { !q <= fv * !q by 1 * !q <= fv * !q };3766assert { power 2 (!t + 2) = 2 * power 2 (!t + 1) };3767{qed}3768c := fv * !q;3769t := !t + 1;3770q := 2 * !q;3771{proof…}3772assert { !c = fv * power 2 !t };3773{qed}3774f := Zarith.fdiv b !q3775done;3776{proof…}3777assert { 0 < !q /\ !f * !q <= b < !f * !q + !q /\ !f * !q < a };3778assert { power 2 (!t + 1) = !q };3779{qed}3780(!t, !c)3781
No float of the positive [lo, hi] is a multiple of 2^(g+1)
function mag (x: t) : int = match x.value with Finite _ k -> k | _ -> 0 end37843785function sfirst (lo hi: t) : int =3786if uexp lo.fmt (mag lo) < uexp lo.fmt (mag hi) then binade lo.fmt3787else sig lo.fmt (mag lo)3788Valid (1.5s) (colibri2 16) (cvc4) (cvc5 11) (split_vc 6) (depth 2)3789let lemma nomult (lo hi f: t) (g: int)3790requires { pos_iv lo hi /\ le_dz lo f /\ le_dz f hi }3791requires { uexp lo.fmt (mag hi) <= g }3792requires { gap (sfirst lo hi) (sig lo.fmt (mag hi)) (power 2 (g - uexp lo.fmt (mag hi) + 1)) }3793ensures { not mult (to_real f) (g + 1) }3794= {proof…}3795let fm = lo.fmt in3796let k1 = mag lo in3797let k2 = mag hi in3798let u2 = uexp fm k2 in3799let t = g - u2 in3800let s1 = sfirst lo hi in3801let s2 = sig fm k2 in3802let q = pure { power 2 (t + 1) } in3803binade_ge_2 fm;3804match f.value with3805| Finite _ k ->3806vom_dec fm k; vom_dec fm k1; vom_dec fm k2;3807uexp_mono fm k1 k; uexp_mono fm k k2;3808vom_mult fm k; vom_pos fm k;3809if pure { mult (to_real f) (g + 1) } then begin3810let m = any int ensures { vom fm k = from_int result *. pow2r (g + 1) } in3811if uexp fm k = u2 then begin3812assert { k1 <= k <= k2 };3813assert { sig fm k - sig fm k2 = k - k2 };3814assert { uexp fm k1 = u2 -> sig fm k - sig fm k1 = k - k1 };3815assert { s1 <= sig fm k <= s2 };3816pow2r_add u2 (t + 1); pow2r_int (t + 1); pow2r_pos u2;3817assert { vom fm k = from_int (m * q) *. pow2r u2 };3818scale_cmp (sig fm k) (m * q) (pow2r u2);3819gap_at s1 s2 q (sig fm k) m;3820absurd3821end else begin3822assert { uexp fm k1 < u2 /\ s1 = binade fm };3823if t + 1 <= fm.sb - 1 then begin3824let n0 = pure { power 2 (fm.sb - 2 - t) } in3825assert { binade fm = n0 * q };3826gap_at s1 s2 q (binade fm) n0;3827absurd3828end;3829pow2r_le (uexp fm k + fm.sb) (g + 1);3830mult_zero (g + 1); mult_gap 0.0 (vom fm k) (g + 1);3831absurd3832end3833end3834| _ -> absurd3835end3836{qed}3837
The bounds for a positive interval
Valid (6.4s) (colibri2 33) (cvc4 2) (cvc5 6) (split_vc 9) (depth 5)let pos_bounds (lo hi: t) : (t, t)3840requires { pos_iv lo hi }3841returns { (a, b) -> a.fmt = lo.fmt /\ b.fmt = lo.fmt }3842returns { (a, b) -> exists g bg. witness lo hi bg g /\3843a = lower lo.fmt g /\ b = upper lo.fmt g bg }3844= let fm = lo.fmt in3845match lo.value, hi.value with3846| Finite _ k1, Finite _ k2 ->3847let bn = binade_p fm in3848let q = qmin_p fm in3849let u1 = uexp_p fm k1 in3850let u2 = uexp_p fm k2 in3851let s2 = sig_p fm k2 in3852let s1 = if u1 < u2 then bn else sig_p fm k1 in3853{proof…}3854assert { lo.value = Finite false k1 /\ hi.value = Finite false k2 };3855binade_ge_2 fm; nb_sign_ge fm;3856vom_dec fm k1; vom_dec fm k2; uexp_mono fm k1 k2;3857assert { 0 < s1 <= s2 };3858{qed}3859let (t, c) = maxtz s1 s2 in3860let g = u2 + t in3861let ghost kb = (u2 - q) * bn + c in3862{proof…}3863if u1 < u2 then3864assert { (u1 - q + 1) * bn <= (u2 - q) * bn3865by (u2 - q) * bn = (u1 - q + 1) * bn + (u2 - u1 - 1) * bn };3866assert { k1 <= kb <= k2 };3867{qed}3868let ghost bg = mk fm (Finite false kb) in3869let nb = nb_sign_p fm in3870let kl = (g + 2 - q) * bn - 1 in3871let kl = if kl < nb - 2 then kl else nb - 2 in3872let a = of_index_p fm (-1 - kl) in3873let d = { dm = pow2_int (t + fm.sb) - pow2_int t + c; de = u2 } in3874let b = round_d fm RTN false d in3875{proof…}3876vom_s fm u2 c;3877let ghost n = any int ensures { c = result * power 2 t } in3878pow2r_add u2 t; pow2r_int t; pow2r_add u2 (t + fm.sb); pow2r_int (t + fm.sb);3879assert { to_real bg = from_int c *. pow2r u2 };3880assert { to_real bg = from_int n *. pow2r g };3881assert { dval d = pow2r (g + fm.sb) -. pow2r g +. to_real bg };3882assert { mag lo = k1 /\ mag hi = k2 /\ sfirst lo hi = s1 /\ sig fm k2 = s2 };3883assert { g - uexp fm (mag hi) + 1 = t + 1 };3884assert { gap (sfirst lo hi) (sig lo.fmt (mag hi)) (power 2 (g - uexp lo.fmt (mag hi) + 1)) };3885assert { forall f. le_dz lo f -> le_dz f hi -> not mult (to_real f) (g + 1) };3886assert { witness lo hi bg g };3887assert { a = lower lo.fmt g };3888assert { b = upper lo.fmt g bg };3889{qed}3890(a, b)3891| _ -> absurd3892end38933894predicate one_sign (lo hi: t) = pos_iv lo hi \/ neg_iv lo hi3895Valid (86ms) (colibri2)3896let ghost neg_fmt (x: t) : unit3897ensures { (neg x).fmt = x.fmt }3898= ()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)let add_bounds (lo hi: t) : option (t, t)3904ensures { match result with3905| None -> not one_sign lo hi3906| Some (a, b) -> one_sign lo hi /\ a.fmt = lo.fmt /\ b.fmt = lo.fmt /\3907forall m x y. x.fmt = lo.fmt -> y.fmt = lo.fmt ->3908le_dz lo (fp_add m x y) -> le_dz (fp_add m x y) hi -> le_dz a x /\ le_dz x b3909end }3910= if not (eq_format lo.fmt hi.fmt) || is_nan lo || is_nan hi then None3911else3912let nb = nb_sign_p lo.fmt in3913let il = index_p lo in3914let ih = index_p hi in3915if ih < il then None3916else if 0 < il && ih < nb - 1 then Some (pos_bounds lo hi)3917else if - nb < il && ih < -1 then begin3918{proof…}3919assert { pos_iv (neg hi) (neg lo) };3920{qed}3921let (a, b) = pos_bounds (neg hi) (neg lo) in3922{proof…}3923neg_fmt hi; neg_fmt a; neg_fmt b;3924let ghost g = any int ensures { exists bg. witness (neg hi) (neg lo) bg result /\3925a = lower lo.fmt result /\ b = upper lo.fmt result bg } in3926let ghost bg = any t ensures { witness (neg hi) (neg lo) result g /\3927a = lower lo.fmt g /\ b = upper lo.fmt g result } in3928let lemma pt (m: mode) (x y: t) : unit3929requires { x.fmt = lo.fmt /\ y.fmt = lo.fmt }3930requires { le_dz lo (fp_add m x y) /\ le_dz (fp_add m x y) hi }3931ensures { le_dz (neg b) x /\ le_dz x (neg a) }3932= neg_sound lo hi bg g m x y in3933{qed}3934Some (neg b, neg a)3935end else None3936end3937