Common — library colibrilib.fbin — module Nearest

Linear bounds of the rounding to nearest

For the simplex (Fp_to_real): when the rounding f of a real r to nearest (RNE or RNA, any sign of zero) is in the finite interval [lo, hi], a r + b <= f <= c r + d. With h half the least subnormal and c = 2^-mw: (1-c) r <= f <= (1+c) r on the positive normals, |f - r| <= h on the subnormals and zeros, and |f - r| <= h + M 2^-sb in general, M the largest magnitude.

2508
module Nearest
2509
use int.Int
2510
use int.Power
2511
use real.RealInfix
2512
use real.FromInt
2513
use real.Abs as RA
2514
use option.Option
2515
use colibrilib.fp.Widen
2516
use colibrilib.fp.Ereal
2517
use Pow2r
2518
use Format
2519
use Float
2520
use Round
2521
use Impl
2522
2523
predicate
nearest
(m: mode) = m = RNE \/ m = RNA

The rounding to nearest of r >= 0 is at most half a gap g from r; g is the least gap or at most the magnitude below r over the binade

  Valid (1.6s) (cvc5)
2528
let ghost
near_mag
(fm: format) (m: mode) (r: real) : unit
2529
requires { nearest m /\ 0.0 <=. r }
2530
ensures { let kd = kdn fm r in let k = round_mag fm m r in
2531
let g = pow2r (uexp fm kd) in
2532
0 <= kd <= k /\ 0.0 <=. vom fm kd <=. r /\ vom fm kd <=. vom fm k /\
2533
2.0 *. (vom fm k -. r) <=. g /\ 2.0 *. (r -. vom fm k) <=. g /\
2534
(uexp fm kd = qmin fm \/ from_int (binade fm) *. g <=. vom fm kd) }
2535
= {proof…}
2536
let kd = kdn fm r in
2537
vom_dec fm kd; vom_zero fm; vom_le fm 0 kd;
2538
round_mag_range fm m r;
2539
let u = uexp fm kd in
2540
pow2r_pos u;
2541
assert { vom fm (kd + 1) -. vom fm kd = pow2r u };
2542
if u <> qmin fm then scale_cmp (binade fm) (sig fm kd) (pow2r u);
2543
vom_le fm kd (round_mag fm m r)
2544
{qed}

The error of the rounding to nearest of r >= 0, finite, on the magnitude

  Valid (522ms) (colibri2 16) (cvc4) (cvc5 2) (split_vc) (depth 1)
2548
let ghost
near_pos
(fm: format) (m: mode) (r: real) : unit
2549
requires { nearest m /\ 0.0 <=. r /\ round_mag fm m r < nb_sign fm - 1 }
2550
ensures { let f = vom fm (round_mag fm m r) in
2551
let a = from_int (binade fm) in let h = pow2r (qmin fm - 1) in
2552
let e = RA.abs (f -. r) in
2553
0.0 <=. f /\
2554
2.0 *. a *. e <=. 2.0 *. a *. h +. f /\
2555
a *. e <=. a *. h +. r /\
2556
(f <. 2.0 *. a *. h -> e <=. h) /\
2557
(2.0 *. a *. h <=. f -> a *. e <=. r) /\
2558
(2.0 *. a *. h <=. f -> 2.0 *. a *. e <=. f) }
2559
= {proof…}
2560
near_mag fm m r;
2561
binade_ge_2 fm;
2562
let kd = kdn fm r in
2563
let k = round_mag fm m r in
2564
let a = from_int (binade fm) in
2565
let h = pow2r (qmin fm - 1) in
2566
let g = pow2r (uexp fm kd) in
2567
let f = vom fm k in
2568
let e = RA.abs (f -. r) in
2569
pow2r_succ (qmin fm - 1); pow2r_pos (qmin fm - 1);
2570
assert { 2.0 *. e <=. g };
2571
assert { 2.0 <=. a };
2572
if uexp fm kd = qmin fm then begin
2573
assert { g = 2.0 *. h };
2574
assert { e <=. h };
2575
assert { a *. e <=. a *. h };
2576
assert { 2.0 *. a *. e <=. 2.0 *. a *. h };
2577
if pure { 2.0 *. a *. h <=. f } then begin
2578
assert { r >=. f -. h };
2579
assert { a *. h <=. 2.0 *. a *. h -. h by h <=. a *. h };
2580
assert { a *. e <=. a *. h }
2581
end
2582
end else begin
2583
assert { a *. g <=. vom fm kd };
2584
assert { 2.0 *. a *. e <=. a *. g by a *. (2.0 *. e) <=. a *. g };
2585
assert { 2.0 *. a *. e <=. f };
2586
assert { 2.0 *. a *. e <=. r };
2587
assert { a *. e <=. r };
2588
if pure { f <. 2.0 *. a *. h } then begin
2589
assert { 2.0 *. a *. e <. 2.0 *. a *. h };
2590
assert { e <. h }
2591
end
2592
end
2593
{qed}

The error of the rounding to nearest, finite; f has the sign of r

  Valid (720ms) (colibri2 15) (cvc4 2) (cvc5 7) (split_vc 3) (depth 2)
2597
let ghost
near_err
(fm: format) (m: mode) (z: bool) (r: real) : unit
2598
requires { nearest m /\ is_finite (round_fin fm m z r) }
2599
ensures { let f = to_real (round_fin fm m z r) in
2600
let a = from_int (binade fm) in let h = pow2r (qmin fm - 1) in
2601
let e = RA.abs (f -. r) in
2602
(0.0 <=. r -> 0.0 <=. f) /\ (r <=. 0.0 -> f <=. 0.0) /\
2603
2.0 *. a *. e <=. 2.0 *. a *. h +. RA.abs f /\
2604
a *. e <=. a *. h +. RA.abs r /\
2605
(RA.abs f <. 2.0 *. a *. h -> e <=. h) /\
2606
(2.0 *. a *. h <=. RA.abs f -> a *. e <=. RA.abs r) /\
2607
(2.0 *. a *. h <=. RA.abs f -> 2.0 *. a *. e <=. RA.abs f) }
2608
= {proof…}
2609
vom_zero fm;
2610
if pure { 0.0 <=. r } then begin
2611
round_mag_range fm m r;
2612
let k = round_mag fm m r in
2613
if k >= 1 then of_mag_index fm m false k;
2614
assert { k < nb_sign fm - 1 };
2615
assert { to_real (round_fin fm m z r) = vom fm k };
2616
near_pos fm m r;
2617
let f = to_real (round_fin fm m z r) in
2618
assert { RA.abs f = vom fm k };
2619
assert { RA.abs r = r }
2620
end else begin
2621
let m' = mirror m in
2622
assert { m' = m };
2623
round_mag_range fm m (-. r);
2624
let k = round_mag fm m (-. r) in
2625
if k >= 1 then of_mag_index fm m true k;
2626
assert { k < nb_sign fm - 1 };
2627
assert { to_real (round_fin fm m z r) = -. vom fm k };
2628
near_pos fm m (-. r);
2629
let f = to_real (round_fin fm m z r) in
2630
assert { RA.abs f = vom fm k };
2631
assert { RA.abs r = -. r };
2632
assert { RA.abs (f -. r) = RA.abs (vom fm k -. (-. r)) }
2633
end
2634
{qed}

The value of a finite float by its index; mn is the least normal

  Valid (681ms) (cvc5)
2637
let ghost
fin_val
(x: t) : unit
2638
requires { is_finite x }
2639
ensures { let fm = x.fmt in let i = index x in
2640
let mn = from_int (binade fm) *. pow2r (qmin fm) in
2641
(0 <= i -> to_real x = vom fm i) /\
2642
(i < 0 -> to_real x = -. vom fm (-1 - i)) /\
2643
(-1 <= i -> 0.0 <=. to_real x) /\ (i <= 0 -> to_real x <=. 0.0) /\
2644
(binade fm <= i -> mn <=. to_real x) /\
2645
(i <= -1 - binade fm -> to_real x <=. -. mn) /\
2646
(-1 - binade fm < i < binade fm -> RA.abs (to_real x) <. mn) /\
2647
ext x = Fin (to_real x) }
2648
= {proof…}
2649
let fm = x.fmt in
2650
binade_ge_2 fm; vom_zero fm;
2651
vom_s fm (qmin fm) (binade fm);
2652
assert { (qmin fm - qmin fm) * binade fm + binade fm = binade fm };
2653
match x.value with
2654
| Finite neg k ->
2655
vom_le fm 0 k;
2656
if k >= binade fm then vom_le fm (binade fm) k
2657
else vom_lt fm k (binade fm);
2658
if neg then assert { index x = -1 - k }
2659
| _ -> absurd
2660
end
2661
{qed}

The cases of the bounds, on the reals: a = 2^mw, c = 1/a, h half the least subnormal, e = |f - r|

A normal f, A = 2^sb: A/(A+1) r <= f <= A/(A-1) r when f >= 0; tighter than the bounds (2^mw+2)/(2^mw+1) and (2^mw-2)/(2^mw-1) of Belaid, Michel, Rueher (2012, Table 1)

  Valid (134ms) (colibri2 6) (cvc4 2) (split_vc) (depth 1)
2669
let ghost
r_norm
(aa f r: real) : unit
2670
requires { 1.0 <. aa /\ aa *. RA.abs (f -. r) <=. RA.abs f }
2671
ensures { 0.0 <=. f -> aa *. r <=. (aa +. 1.0) *. f /\ (aa -. 1.0) *. f <=. aa *. r }
2672
ensures { f <=. 0.0 -> aa *. r <=. (aa -. 1.0) *. f /\ (aa +. 1.0) *. f <=. aa *. r }
2673
= {proof…}
2674
if pure { r <=. f } then begin
2675
assert { RA.abs (f -. r) = f -. r };
2676
assert { aa *. (r -. f) <=. 0.0 }
2677
end else begin
2678
assert { RA.abs (f -. r) = r -. f };
2679
assert { aa *. (f -. r) <=. 0.0 }
2680
end;
2681
if pure { 0.0 <=. f } then begin
2682
assert { aa *. (f -. r) <=. f /\ aa *. (r -. f) <=. f }
2683
end else begin
2684
assert { aa *. (f -. r) <=. -. f /\ aa *. (r -. f) <=. -. f }
2685
end
2686
{qed}
Valid (317ms) (colibri2 9) (cvc5 2) (split_vc 4) (depth 3)
2687
let ghost
r_nonneg
(a c h f r: real) : unit
2688
requires { a *. c = 1.0 /\ 2.0 <=. a /\ 0.0 <. h /\ 0.0 <=. f }
2689
requires { 0.0 <=. r -> a *. RA.abs (f -. r) <=. a *. h +. r }
2690
requires { r <. 0.0 -> f = 0.0 /\ RA.abs (f -. r) <=. h }
2691
ensures { (1.0 -. c) *. r -. h <=. f <=. (1.0 +. c) *. r +. h *. (1.0 +. c) }
2692
= {proof…}
2693
assert { 0.0 <. c <=. 1.0 by c *. 2.0 <=. c *. a };
2694
if pure { 0.0 <=. r } then begin
2695
assert { c *. (a *. RA.abs (f -. r)) <=. c *. (a *. h +. r) };
2696
assert { c *. (a *. RA.abs (f -. r)) = (c *. a) *. RA.abs (f -. r) };
2697
assert { c *. (a *. h +. r) = (c *. a) *. h +. c *. r };
2698
assert { RA.abs (f -. r) <=. h +. c *. r };
2699
assert { 0.0 <=. h *. c }
2700
end else begin
2701
assert { -. h <=. r };
2702
assert { 0.0 <=. (1.0 +. c) *. (r +. h) }
2703
end
2704
{qed}
2705
Valid (306ms) (colibri2 9) (cvc5 2) (split_vc 4) (depth 3)
2706
let ghost
r_nonpos
(a c h f r: real) : unit
2707
requires { a *. c = 1.0 /\ 2.0 <=. a /\ 0.0 <. h /\ f <=. 0.0 }
2708
requires { r <=. 0.0 -> a *. RA.abs (f -. r) <=. a *. h -. r }
2709
requires { 0.0 <. r -> f = 0.0 /\ RA.abs (f -. r) <=. h }
2710
ensures { (1.0 +. c) *. r -. h *. (1.0 +. c) <=. f <=. (1.0 -. c) *. r +. h }
2711
= {proof…}
2712
assert { 0.0 <. c <=. 1.0 by c *. 2.0 <=. c *. a };
2713
if pure { r <=. 0.0 } then begin
2714
assert { c *. (a *. RA.abs (f -. r)) <=. c *. (a *. h -. r) };
2715
assert { c *. (a *. RA.abs (f -. r)) = (c *. a) *. RA.abs (f -. r) };
2716
assert { c *. (a *. h -. r) = (c *. a) *. h -. c *. r };
2717
assert { RA.abs (f -. r) <=. h -. c *. r };
2718
assert { 0.0 <=. h *. c }
2719
end else begin
2720
assert { r <=. h };
2721
assert { (1.0 +. c) *. (r -. h) <=. 0.0 }
2722
end
2723
{qed}
2724
Valid (71ms) (colibri2 5) (cvc5) (split_vc) (depth 1)
2725
let ghost
r_gen
(a s h f r w: real) : unit
2726
requires { 2.0 *. a *. s = 1.0 /\ 0.0 <. a }
2727
requires { 2.0 *. a *. RA.abs (f -. r) <=. 2.0 *. a *. h +. w }
2728
ensures { r -. (h +. w *. s) <=. f <=. r +. (h +. w *. s) }
2729
= {proof…}
2730
assert { 0.0 <. s };
2731
assert { s *. (2.0 *. a *. RA.abs (f -. r)) <=. s *. (2.0 *. a *. h +. w) };
2732
assert { s *. (2.0 *. a *. RA.abs (f -. r)) = (2.0 *. a *. s) *. RA.abs (f -. r) };
2733
assert { s *. (2.0 *. a *. h +. w) = (2.0 *. a *. s) *. h +. w *. s };
2734
assert { RA.abs (f -. r) <=. h +. w *. s }
2735
{qed}

The bounds (a/a') r + b <= f <= (c/c') r + d, with the denominators a' = lo_den and c' = hi_den

2739
type
bounds
= {
lo_coef
: dyadic;
lo_den
: int;
lo_cst
: dyadic;
2740
hi_coef
: dyadic;
hi_den
: int;
hi_cst
: dyadic }
2741
2742
predicate
bounds_ok
(b: bounds) (lo hi: t) =
2743
0 < b.lo_den /\ 0 < b.hi_den /\
2744
forall m z r. nearest m -> le_dz lo (round_fin lo.fmt m z r) ->
2745
le_dz (round_fin lo.fmt m z r) hi ->
2746
dval b.lo_coef *. r +. from_int b.lo_den *. dval b.lo_cst
2747
<=. from_int b.lo_den *. to_real (round_fin lo.fmt m z r) /\
2748
from_int b.hi_den *. to_real (round_fin lo.fmt m z r)
2749
<=. dval b.hi_coef *. r +. from_int b.hi_den *. dval b.hi_cst
2750
Valid (41ms) (colibri2)
2751
let
is_fin
(x: t) : bool
2752
ensures { result <-> is_finite x }
2753
= match x.value with Finite _ _ -> true | _ -> false end
2754
Valid (100ms) (cvc5)
2755
let
dneg
(d: dyadic) : dyadic
2756
ensures { dval result = -. dval d }
2757
= { dm = - d.dm; de = d.de }

The bounds of the rounding to nearest in [lo, hi]; None when lo or hi is not finite or their formats differ

  Valid (1.7s) (colibri2 108) (cvc4 10) (cvc5 73) (split_vc 117) (depth 5)
2761
let
nearest_bounds
(lo hi: t) : option bounds
2762
ensures { match result with
2763
| None -> not (is_finite lo /\ is_finite hi /\ lo.fmt = hi.fmt)
2764
| Some b -> bounds_ok b lo hi
2765
end }
2766
= if not (is_fin lo && is_fin hi && eq_format lo.fmt hi.fmt) then None
2767
else begin
2768
let fm = lo.fmt in
2769
let p = binade_p fm in
2770
let q = qmin_p fm in
2771
let zero = { dm = 0; de = 0 } in
2772
let one = { dm = 1; de = 0 } in
2773
let h = { dm = 1; de = q - 1 } in
2774
let cm = { dm = p - 1; de = 1 - fm.sb } in
2775
let cp = { dm = p + 1; de = 1 - fm.sb } in
2776
let il = index_p lo in
2777
let ih = index_p hi in
2778
{proof…}
2779
let ghost a = from_int (binade fm) in
2780
let ghost c = pow2r (1 - fm.sb) in
2781
let ghost hr = pow2r (qmin fm - 1) in
2782
binade_ge_2 fm;
2783
pow2r_int (fm.sb - 1); pow2r_add (1 - fm.sb) (fm.sb - 1);
2784
pow2r_pos (1 - fm.sb); pow2r_pos (qmin fm - 1);
2785
pow2r_succ (qmin fm - 1);
2786
assert { pow2r 0 = 1.0 };
2787
assert { a *. c = 1.0 };
2788
assert { dval cm = 1.0 -. c /\ dval cp = 1.0 +. c };
2789
assert { dval h = hr /\ dval one = 1.0 /\ dval zero = 0.0 };
2790
assert { 2.0 *. a *. hr = a *. pow2r (qmin fm) };
2791
assert { c <=. 1.0 by c *. 2.0 <=. c *. a };
2792
fin_val lo; fin_val hi;
2793
{qed}
2794
let aa = { dm = 2 * p; de = 0 } in
2795
let res =
2796
if il >= p then
2797
(* positive normals, A = 2^sb: A/(A+1) r <= f <= A/(A-1) r *)
2798
{ lo_coef = aa; lo_den = 2 * p + 1; lo_cst = zero;
2799
hi_coef = aa; hi_den = 2 * p - 1; hi_cst = zero }
2800
else if ih <= -1 - p then
2801
{ lo_coef = aa; lo_den = 2 * p - 1; lo_cst = zero;
2802
hi_coef = aa; hi_den = 2 * p + 1; hi_cst = zero }
2803
else if -1 - p < il && ih < p then
2804
(* subnormals and zeros: |f - r| <= h *)
2805
{ lo_coef = one; lo_den = 1; lo_cst = dneg h;
2806
hi_coef = one; hi_den = 1; hi_cst = h }
2807
else if il >= -1 then
2808
{ lo_coef = cm; lo_den = 1; lo_cst = dneg h;
2809
hi_coef = cp; hi_den = 1; hi_cst = dmul h cp }
2810
else if ih <= 0 then
2811
{ lo_coef = cp; lo_den = 1; lo_cst = dneg (dmul h cp);
2812
hi_coef = cm; hi_den = 1; hi_cst = h }
2813
else begin
2814
(* |f - r| <= h + M 2^-sb *)
2815
let w = if -1 - il <= ih then hi else neg lo in
2816
{proof…} index_neg lo; {qed}
2817
let e = dadd h (dmul (to_dyadic w) { dm = 1; de = - fm.sb }) in
2818
{ lo_coef = one; lo_den = 1; lo_cst = dneg e;
2819
hi_coef = one; hi_den = 1; hi_cst = e }
2820
end in
2821
{proof…}
2822
let lemma pt (m: mode) (z: bool) (r: real) : unit
2823
requires { nearest m /\ le_dz lo (round_fin fm m z r) /\ le_dz (round_fin fm m z r) hi }
2824
ensures { dval res.lo_coef *. r +. from_int res.lo_den *. dval res.lo_cst
2825
<=. from_int res.lo_den *. to_real (round_fin fm m z r) }
2826
ensures { from_int res.hi_den *. to_real (round_fin fm m z r)
2827
<=. dval res.hi_coef *. r +. from_int res.hi_den *. dval res.hi_cst }
2828
= let x = round_fin fm m z r in
2829
round_fin_facts fm m z r;
2830
assert { from_int 1 = 1.0 };
2831
assert { res.lo_den = 1 -> res.hi_den = 1 ->
2832
from_int res.lo_den = 1.0 /\ from_int res.hi_den = 1.0 };
2833
assert { index lo <= index x <= index hi };
2834
assert { is_finite x };
2835
fin_val x;
2836
near_err fm m z r;
2837
let f = to_real x in
2838
if il >= p then begin
2839
assert { 2.0 *. a *. hr <=. RA.abs f };
2840
assert { dval aa = 2.0 *. a };
2841
assert { from_int res.lo_den = 2.0 *. a +. 1.0 };
2842
assert { from_int res.hi_den = 2.0 *. a -. 1.0 };
2843
r_norm (2.0 *. a) f r
2844
end else if ih <= -1 - p then begin
2845
assert { 2.0 *. a *. hr <=. RA.abs f };
2846
assert { dval aa = 2.0 *. a };
2847
assert { from_int res.lo_den = 2.0 *. a -. 1.0 };
2848
assert { from_int res.hi_den = 2.0 *. a +. 1.0 };
2849
r_norm (2.0 *. a) f r
2850
end else if -1 - p < il && ih < p then begin
2851
assert { RA.abs f <. 2.0 *. a *. hr };
2852
assert { RA.abs (f -. r) <=. hr };
2853
assert { dval res.lo_coef = 1.0 /\ dval res.lo_cst = -. hr };
2854
assert { dval res.hi_coef = 1.0 /\ dval res.hi_cst = hr };
2855
assert { from_int res.lo_den = 1.0 /\ from_int res.hi_den = 1.0 };
2856
assert { r -. hr <=. f <=. r +. hr }
2857
end else if il >= -1 then begin
2858
assert { 0.0 <=. f };
2859
assert { r <. 0.0 -> f = 0.0 };
2860
r_nonneg a c hr f r;
2861
assert { dval res.hi_cst = hr *. (1.0 +. c) }
2862
end else if ih <= 0 then begin
2863
assert { f <=. 0.0 };
2864
assert { 0.0 <. r -> f = 0.0 };
2865
r_nonpos a c hr f r;
2866
assert { dval res.lo_cst = -. (hr *. (1.0 +. c)) }
2867
end else begin
2868
let w = if -1 - il <= ih then hi else neg lo in
2869
fin_val w;
2870
ext_le lo x; ext_le x hi;
2871
assert { to_real lo <=. f <=. to_real hi };
2872
assert { is_finite w };
2873
if -1 - il <= ih then begin
2874
assert { w = hi };
2875
assert { 0.0 <=. to_real hi /\ to_real lo <=. 0.0 };
2876
assert { -. to_real lo = vom fm (-1 - il) /\ to_real hi = vom fm ih };
2877
vom_le fm (-1 - il) ih
2878
end else begin
2879
assert { to_real w = -. to_real lo };
2880
assert { 0.0 <=. to_real hi /\ to_real lo <=. 0.0 };
2881
assert { -. to_real lo = vom fm (-1 - il) /\ to_real hi = vom fm ih };
2882
vom_le fm ih (-1 - il)
2883
end;
2884
assert { RA.abs f <=. to_real w };
2885
pow2r_add (1 - fm.sb) (-1);
2886
assert { pow2r (- fm.sb) *. 2.0 = c };
2887
r_gen a (pow2r (- fm.sb)) hr f r (to_real w);
2888
assert { dval res.lo_coef = 1.0 /\ dval res.hi_coef = 1.0 };
2889
assert { from_int res.lo_den = 1.0 /\ from_int res.hi_den = 1.0 };
2890
assert { dval res.hi_cst = hr +. to_real w *. pow2r (- fm.sb) };
2891
assert { dval res.lo_cst = -. dval res.hi_cst }
2892
end in
2893
assert { 0 < res.lo_den /\ 0 < res.hi_den };
2894
assert { bounds_ok res lo hi };
2895
{qed}
2896
Some res
2897
end
2898
end