library colibrilib.fbin — module NearestFor 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.
module Nearest2508use int.Int2509use int.Power2510use real.RealInfix2511use real.FromInt2512use real.Abs as RA2513use option.Option2514use colibrilib.fp.Widen2515use colibrilib.fp.Ereal2516use Pow2r2517use Format2518use Float2519use Round2520use Impl25212522predicate nearest (m: mode) = m = RNE \/ m = RNA2523
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)let ghost near_mag (fm: format) (m: mode) (r: real) : unit2528requires { nearest m /\ 0.0 <=. r }2529ensures { let kd = kdn fm r in let k = round_mag fm m r in2530let g = pow2r (uexp fm kd) in25310 <= kd <= k /\ 0.0 <=. vom fm kd <=. r /\ vom fm kd <=. vom fm k /\25322.0 *. (vom fm k -. r) <=. g /\ 2.0 *. (r -. vom fm k) <=. g /\2533(uexp fm kd = qmin fm \/ from_int (binade fm) *. g <=. vom fm kd) }2534= {proof…}2535let kd = kdn fm r in2536vom_dec fm kd; vom_zero fm; vom_le fm 0 kd;2537round_mag_range fm m r;2538let u = uexp fm kd in2539pow2r_pos u;2540assert { vom fm (kd + 1) -. vom fm kd = pow2r u };2541if u <> qmin fm then scale_cmp (binade fm) (sig fm kd) (pow2r u);2542vom_le fm kd (round_mag fm m r)2543{qed}2544
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)let ghost near_pos (fm: format) (m: mode) (r: real) : unit2548requires { nearest m /\ 0.0 <=. r /\ round_mag fm m r < nb_sign fm - 1 }2549ensures { let f = vom fm (round_mag fm m r) in2550let a = from_int (binade fm) in let h = pow2r (qmin fm - 1) in2551let e = RA.abs (f -. r) in25520.0 <=. f /\25532.0 *. a *. e <=. 2.0 *. a *. h +. f /\2554a *. e <=. a *. h +. r /\2555(f <. 2.0 *. a *. h -> e <=. h) /\2556(2.0 *. a *. h <=. f -> a *. e <=. r) /\2557(2.0 *. a *. h <=. f -> 2.0 *. a *. e <=. f) }2558= {proof…}2559near_mag fm m r;2560binade_ge_2 fm;2561let kd = kdn fm r in2562let k = round_mag fm m r in2563let a = from_int (binade fm) in2564let h = pow2r (qmin fm - 1) in2565let g = pow2r (uexp fm kd) in2566let f = vom fm k in2567let e = RA.abs (f -. r) in2568pow2r_succ (qmin fm - 1); pow2r_pos (qmin fm - 1);2569assert { 2.0 *. e <=. g };2570assert { 2.0 <=. a };2571if uexp fm kd = qmin fm then begin2572assert { g = 2.0 *. h };2573assert { e <=. h };2574assert { a *. e <=. a *. h };2575assert { 2.0 *. a *. e <=. 2.0 *. a *. h };2576if pure { 2.0 *. a *. h <=. f } then begin2577assert { r >=. f -. h };2578assert { a *. h <=. 2.0 *. a *. h -. h by h <=. a *. h };2579assert { a *. e <=. a *. h }2580end2581end else begin2582assert { a *. g <=. vom fm kd };2583assert { 2.0 *. a *. e <=. a *. g by a *. (2.0 *. e) <=. a *. g };2584assert { 2.0 *. a *. e <=. f };2585assert { 2.0 *. a *. e <=. r };2586assert { a *. e <=. r };2587if pure { f <. 2.0 *. a *. h } then begin2588assert { 2.0 *. a *. e <. 2.0 *. a *. h };2589assert { e <. h }2590end2591end2592{qed}2593
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)let ghost near_err (fm: format) (m: mode) (z: bool) (r: real) : unit2597requires { nearest m /\ is_finite (round_fin fm m z r) }2598ensures { let f = to_real (round_fin fm m z r) in2599let a = from_int (binade fm) in let h = pow2r (qmin fm - 1) in2600let e = RA.abs (f -. r) in2601(0.0 <=. r -> 0.0 <=. f) /\ (r <=. 0.0 -> f <=. 0.0) /\26022.0 *. a *. e <=. 2.0 *. a *. h +. RA.abs f /\2603a *. e <=. a *. h +. RA.abs r /\2604(RA.abs f <. 2.0 *. a *. h -> e <=. h) /\2605(2.0 *. a *. h <=. RA.abs f -> a *. e <=. RA.abs r) /\2606(2.0 *. a *. h <=. RA.abs f -> 2.0 *. a *. e <=. RA.abs f) }2607= {proof…}2608vom_zero fm;2609if pure { 0.0 <=. r } then begin2610round_mag_range fm m r;2611let k = round_mag fm m r in2612if k >= 1 then of_mag_index fm m false k;2613assert { k < nb_sign fm - 1 };2614assert { to_real (round_fin fm m z r) = vom fm k };2615near_pos fm m r;2616let f = to_real (round_fin fm m z r) in2617assert { RA.abs f = vom fm k };2618assert { RA.abs r = r }2619end else begin2620let m' = mirror m in2621assert { m' = m };2622round_mag_range fm m (-. r);2623let k = round_mag fm m (-. r) in2624if k >= 1 then of_mag_index fm m true k;2625assert { k < nb_sign fm - 1 };2626assert { to_real (round_fin fm m z r) = -. vom fm k };2627near_pos fm m (-. r);2628let f = to_real (round_fin fm m z r) in2629assert { RA.abs f = vom fm k };2630assert { RA.abs r = -. r };2631assert { RA.abs (f -. r) = RA.abs (vom fm k -. (-. r)) }2632end2633{qed}2634
The value of a finite float by its index; mn is the least normal
Valid (681ms) (cvc5)let ghost fin_val (x: t) : unit2637requires { is_finite x }2638ensures { let fm = x.fmt in let i = index x in2639let mn = from_int (binade fm) *. pow2r (qmin fm) in2640(0 <= i -> to_real x = vom fm i) /\2641(i < 0 -> to_real x = -. vom fm (-1 - i)) /\2642(-1 <= i -> 0.0 <=. to_real x) /\ (i <= 0 -> to_real x <=. 0.0) /\2643(binade fm <= i -> mn <=. to_real x) /\2644(i <= -1 - binade fm -> to_real x <=. -. mn) /\2645(-1 - binade fm < i < binade fm -> RA.abs (to_real x) <. mn) /\2646ext x = Fin (to_real x) }2647= {proof…}2648let fm = x.fmt in2649binade_ge_2 fm; vom_zero fm;2650vom_s fm (qmin fm) (binade fm);2651assert { (qmin fm - qmin fm) * binade fm + binade fm = binade fm };2652match x.value with2653| Finite neg k ->2654vom_le fm 0 k;2655if k >= binade fm then vom_le fm (binade fm) k2656else vom_lt fm k (binade fm);2657if neg then assert { index x = -1 - k }2658| _ -> absurd2659end2660{qed}2661
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)let ghost r_norm (aa f r: real) : unit2669requires { 1.0 <. aa /\ aa *. RA.abs (f -. r) <=. RA.abs f }2670ensures { 0.0 <=. f -> aa *. r <=. (aa +. 1.0) *. f /\ (aa -. 1.0) *. f <=. aa *. r }2671ensures { f <=. 0.0 -> aa *. r <=. (aa -. 1.0) *. f /\ (aa +. 1.0) *. f <=. aa *. r }2672= {proof…}2673if pure { r <=. f } then begin2674assert { RA.abs (f -. r) = f -. r };2675assert { aa *. (r -. f) <=. 0.0 }2676end else begin2677assert { RA.abs (f -. r) = r -. f };2678assert { aa *. (f -. r) <=. 0.0 }2679end;2680if pure { 0.0 <=. f } then begin2681assert { aa *. (f -. r) <=. f /\ aa *. (r -. f) <=. f }2682end else begin2683assert { aa *. (f -. r) <=. -. f /\ aa *. (r -. f) <=. -. f }2684end2685{qed} Valid (317ms) (colibri2 9) (cvc5 2) (split_vc 4) (depth 3)2686let ghost r_nonneg (a c h f r: real) : unit2687requires { a *. c = 1.0 /\ 2.0 <=. a /\ 0.0 <. h /\ 0.0 <=. f }2688requires { 0.0 <=. r -> a *. RA.abs (f -. r) <=. a *. h +. r }2689requires { r <. 0.0 -> f = 0.0 /\ RA.abs (f -. r) <=. h }2690ensures { (1.0 -. c) *. r -. h <=. f <=. (1.0 +. c) *. r +. h *. (1.0 +. c) }2691= {proof…}2692assert { 0.0 <. c <=. 1.0 by c *. 2.0 <=. c *. a };2693if pure { 0.0 <=. r } then begin2694assert { c *. (a *. RA.abs (f -. r)) <=. c *. (a *. h +. r) };2695assert { c *. (a *. RA.abs (f -. r)) = (c *. a) *. RA.abs (f -. r) };2696assert { c *. (a *. h +. r) = (c *. a) *. h +. c *. r };2697assert { RA.abs (f -. r) <=. h +. c *. r };2698assert { 0.0 <=. h *. c }2699end else begin2700assert { -. h <=. r };2701assert { 0.0 <=. (1.0 +. c) *. (r +. h) }2702end2703{qed}2704Valid (306ms) (colibri2 9) (cvc5 2) (split_vc 4) (depth 3)2705let ghost r_nonpos (a c h f r: real) : unit2706requires { a *. c = 1.0 /\ 2.0 <=. a /\ 0.0 <. h /\ f <=. 0.0 }2707requires { r <=. 0.0 -> a *. RA.abs (f -. r) <=. a *. h -. r }2708requires { 0.0 <. r -> f = 0.0 /\ RA.abs (f -. r) <=. h }2709ensures { (1.0 +. c) *. r -. h *. (1.0 +. c) <=. f <=. (1.0 -. c) *. r +. h }2710= {proof…}2711assert { 0.0 <. c <=. 1.0 by c *. 2.0 <=. c *. a };2712if pure { r <=. 0.0 } then begin2713assert { c *. (a *. RA.abs (f -. r)) <=. c *. (a *. h -. r) };2714assert { c *. (a *. RA.abs (f -. r)) = (c *. a) *. RA.abs (f -. r) };2715assert { c *. (a *. h -. r) = (c *. a) *. h -. c *. r };2716assert { RA.abs (f -. r) <=. h -. c *. r };2717assert { 0.0 <=. h *. c }2718end else begin2719assert { r <=. h };2720assert { (1.0 +. c) *. (r -. h) <=. 0.0 }2721end2722{qed}2723Valid (71ms) (colibri2 5) (cvc5) (split_vc) (depth 1)2724let ghost r_gen (a s h f r w: real) : unit2725requires { 2.0 *. a *. s = 1.0 /\ 0.0 <. a }2726requires { 2.0 *. a *. RA.abs (f -. r) <=. 2.0 *. a *. h +. w }2727ensures { r -. (h +. w *. s) <=. f <=. r +. (h +. w *. s) }2728= {proof…}2729assert { 0.0 <. s };2730assert { s *. (2.0 *. a *. RA.abs (f -. r)) <=. s *. (2.0 *. a *. h +. w) };2731assert { s *. (2.0 *. a *. RA.abs (f -. r)) = (2.0 *. a *. s) *. RA.abs (f -. r) };2732assert { s *. (2.0 *. a *. h +. w) = (2.0 *. a *. s) *. h +. w *. s };2733assert { RA.abs (f -. r) <=. h +. w *. s }2734{qed}2735
The bounds (a/a') r + b <= f <= (c/c') r + d, with the denominators a' = lo_den and c' = hi_den
type bounds = { lo_coef: dyadic; lo_den: int; lo_cst: dyadic;2739hi_coef: dyadic; hi_den: int; hi_cst: dyadic }27402741predicate bounds_ok (b: bounds) (lo hi: t) =27420 < b.lo_den /\ 0 < b.hi_den /\2743forall m z r. nearest m -> le_dz lo (round_fin lo.fmt m z r) ->2744le_dz (round_fin lo.fmt m z r) hi ->2745dval b.lo_coef *. r +. from_int b.lo_den *. dval b.lo_cst2746<=. from_int b.lo_den *. to_real (round_fin lo.fmt m z r) /\2747from_int b.hi_den *. to_real (round_fin lo.fmt m z r)2748<=. dval b.hi_coef *. r +. from_int b.hi_den *. dval b.hi_cst2749Valid (41ms) (colibri2)2750let is_fin (x: t) : bool2751ensures { result <-> is_finite x }2752= match x.value with Finite _ _ -> true | _ -> false end2753Valid (100ms) (cvc5)2754let dneg (d: dyadic) : dyadic2755ensures { dval result = -. dval d }2756= { dm = - d.dm; de = d.de }2757
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)let nearest_bounds (lo hi: t) : option bounds2761ensures { match result with2762| None -> not (is_finite lo /\ is_finite hi /\ lo.fmt = hi.fmt)2763| Some b -> bounds_ok b lo hi2764end }2765= if not (is_fin lo && is_fin hi && eq_format lo.fmt hi.fmt) then None2766else begin2767let fm = lo.fmt in2768let p = binade_p fm in2769let q = qmin_p fm in2770let zero = { dm = 0; de = 0 } in2771let one = { dm = 1; de = 0 } in2772let h = { dm = 1; de = q - 1 } in2773let cm = { dm = p - 1; de = 1 - fm.sb } in2774let cp = { dm = p + 1; de = 1 - fm.sb } in2775let il = index_p lo in2776let ih = index_p hi in2777{proof…}2778let ghost a = from_int (binade fm) in2779let ghost c = pow2r (1 - fm.sb) in2780let ghost hr = pow2r (qmin fm - 1) in2781binade_ge_2 fm;2782pow2r_int (fm.sb - 1); pow2r_add (1 - fm.sb) (fm.sb - 1);2783pow2r_pos (1 - fm.sb); pow2r_pos (qmin fm - 1);2784pow2r_succ (qmin fm - 1);2785assert { pow2r 0 = 1.0 };2786assert { a *. c = 1.0 };2787assert { dval cm = 1.0 -. c /\ dval cp = 1.0 +. c };2788assert { dval h = hr /\ dval one = 1.0 /\ dval zero = 0.0 };2789assert { 2.0 *. a *. hr = a *. pow2r (qmin fm) };2790assert { c <=. 1.0 by c *. 2.0 <=. c *. a };2791fin_val lo; fin_val hi;2792{qed}2793let aa = { dm = 2 * p; de = 0 } in2794let res =2795if il >= p then2796(* positive normals, A = 2^sb: A/(A+1) r <= f <= A/(A-1) r *)2797{ lo_coef = aa; lo_den = 2 * p + 1; lo_cst = zero;2798hi_coef = aa; hi_den = 2 * p - 1; hi_cst = zero }2799else if ih <= -1 - p then2800{ lo_coef = aa; lo_den = 2 * p - 1; lo_cst = zero;2801hi_coef = aa; hi_den = 2 * p + 1; hi_cst = zero }2802else if -1 - p < il && ih < p then2803(* subnormals and zeros: |f - r| <= h *)2804{ lo_coef = one; lo_den = 1; lo_cst = dneg h;2805hi_coef = one; hi_den = 1; hi_cst = h }2806else if il >= -1 then2807{ lo_coef = cm; lo_den = 1; lo_cst = dneg h;2808hi_coef = cp; hi_den = 1; hi_cst = dmul h cp }2809else if ih <= 0 then2810{ lo_coef = cp; lo_den = 1; lo_cst = dneg (dmul h cp);2811hi_coef = cm; hi_den = 1; hi_cst = h }2812else begin2813(* |f - r| <= h + M 2^-sb *)2814let w = if -1 - il <= ih then hi else neg lo in2815{proof…} index_neg lo; {qed}2816let e = dadd h (dmul (to_dyadic w) { dm = 1; de = - fm.sb }) in2817{ lo_coef = one; lo_den = 1; lo_cst = dneg e;2818hi_coef = one; hi_den = 1; hi_cst = e }2819end in2820{proof…}2821let lemma pt (m: mode) (z: bool) (r: real) : unit2822requires { nearest m /\ le_dz lo (round_fin fm m z r) /\ le_dz (round_fin fm m z r) hi }2823ensures { dval res.lo_coef *. r +. from_int res.lo_den *. dval res.lo_cst2824<=. from_int res.lo_den *. to_real (round_fin fm m z r) }2825ensures { from_int res.hi_den *. to_real (round_fin fm m z r)2826<=. dval res.hi_coef *. r +. from_int res.hi_den *. dval res.hi_cst }2827= let x = round_fin fm m z r in2828round_fin_facts fm m z r;2829assert { from_int 1 = 1.0 };2830assert { res.lo_den = 1 -> res.hi_den = 1 ->2831from_int res.lo_den = 1.0 /\ from_int res.hi_den = 1.0 };2832assert { index lo <= index x <= index hi };2833assert { is_finite x };2834fin_val x;2835near_err fm m z r;2836let f = to_real x in2837if il >= p then begin2838assert { 2.0 *. a *. hr <=. RA.abs f };2839assert { dval aa = 2.0 *. a };2840assert { from_int res.lo_den = 2.0 *. a +. 1.0 };2841assert { from_int res.hi_den = 2.0 *. a -. 1.0 };2842r_norm (2.0 *. a) f r2843end else if ih <= -1 - p then begin2844assert { 2.0 *. a *. hr <=. RA.abs f };2845assert { dval aa = 2.0 *. a };2846assert { from_int res.lo_den = 2.0 *. a -. 1.0 };2847assert { from_int res.hi_den = 2.0 *. a +. 1.0 };2848r_norm (2.0 *. a) f r2849end else if -1 - p < il && ih < p then begin2850assert { RA.abs f <. 2.0 *. a *. hr };2851assert { RA.abs (f -. r) <=. hr };2852assert { dval res.lo_coef = 1.0 /\ dval res.lo_cst = -. hr };2853assert { dval res.hi_coef = 1.0 /\ dval res.hi_cst = hr };2854assert { from_int res.lo_den = 1.0 /\ from_int res.hi_den = 1.0 };2855assert { r -. hr <=. f <=. r +. hr }2856end else if il >= -1 then begin2857assert { 0.0 <=. f };2858assert { r <. 0.0 -> f = 0.0 };2859r_nonneg a c hr f r;2860assert { dval res.hi_cst = hr *. (1.0 +. c) }2861end else if ih <= 0 then begin2862assert { f <=. 0.0 };2863assert { 0.0 <. r -> f = 0.0 };2864r_nonpos a c hr f r;2865assert { dval res.lo_cst = -. (hr *. (1.0 +. c)) }2866end else begin2867let w = if -1 - il <= ih then hi else neg lo in2868fin_val w;2869ext_le lo x; ext_le x hi;2870assert { to_real lo <=. f <=. to_real hi };2871assert { is_finite w };2872if -1 - il <= ih then begin2873assert { w = hi };2874assert { 0.0 <=. to_real hi /\ to_real lo <=. 0.0 };2875assert { -. to_real lo = vom fm (-1 - il) /\ to_real hi = vom fm ih };2876vom_le fm (-1 - il) ih2877end else begin2878assert { to_real w = -. to_real lo };2879assert { 0.0 <=. to_real hi /\ to_real lo <=. 0.0 };2880assert { -. to_real lo = vom fm (-1 - il) /\ to_real hi = vom fm ih };2881vom_le fm ih (-1 - il)2882end;2883assert { RA.abs f <=. to_real w };2884pow2r_add (1 - fm.sb) (-1);2885assert { pow2r (- fm.sb) *. 2.0 = c };2886r_gen a (pow2r (- fm.sb)) hr f r (to_real w);2887assert { dval res.lo_coef = 1.0 /\ dval res.hi_coef = 1.0 };2888assert { from_int res.lo_den = 1.0 /\ from_int res.hi_den = 1.0 };2889assert { dval res.hi_cst = hr +. to_real w *. pow2r (- fm.sb) };2890assert { dval res.lo_cst = -. dval res.hi_cst }2891end in2892assert { 0 < res.lo_den /\ 0 < res.hi_den };2893assert { bounds_ok res lo hi };2894{qed}2895Some res2896end2897end2898