library colibrilib.fbin — module Integralround_int_q m n d is round_int m (n/d), for F.toIntegral. fp_rem x y is the remainder of IEEE 754 (§5.3.1): x - y n with n the integer nearest to x / y, ties to even; it is exact, and a zero result has the sign of x. NaN when x is NaN or infinite or y is NaN or zero; x when y is infinite.
module Integral3137use int.Int3138use int.Power3139use int.EuclideanDivision3140use real.RealInfix3141use real.FromInt3142use real.Truncate3143use option.Option3144use colibrilib.fp.Widen3145use colibrilib.fp.Ereal3146use colibrilib.zarith.Z as Zarith3147use colibrilib.zarith.Zbit3148use colibrilib.zbit.ZbitInt3149use Pow2r3150use Format3151use Float3152use Round3153use Impl3154Valid (412ms) (cvc5)3155let dneg (d: dyadic) : dyadic3156ensures { dval result = -. dval d }3157= { dm = - d.dm; de = d.de }3158Valid (308ms) (colibri2)3159let ghost half_cmp (r d: int) (rd: real) : unit3160requires { 0 < d /\ from_int r = rd *. from_int d }3161ensures { rd <. 0.5 <-> 2 * r < d }3162ensures { 0.5 <. rd <-> d < 2 * r }3163= {proof…}3164assert { from_int (2 * r) = 2.0 *. rd *. from_int d };3165assert { 2 * r < d <-> (2.0 *. rd) *. from_int d <. 1.0 *. from_int d };3166assert { d < 2 * r <-> 1.0 *. from_int d <. (2.0 *. rd) *. from_int d }3167{qed}3168Valid (53ms) (colibri2 5) (split_vc) (depth 1)3169let ghost div_scale (a b c: real) : unit3170requires { b <> 0.0 /\ c <> 0.0 }3171ensures { (a *. c) /. (b *. c) = a /. b }3172ensures { (-. a) /. (-. b) = a /. b }3173= {proof…}3174assert { (a *. c) /. (b *. c) = a /. b };3175assert { (-. a) = a *. (-. 1.0) /\ (-. b) = b *. (-. 1.0) };3176assert { (a *. (-. 1.0)) /. (b *. (-. 1.0)) = a /. b }3177{qed}3178Valid (542ms) (colibri2 12) (cvc5) (split_vc) (depth 1)3179let round_int_q (m: mode) (n d: int) : int3180requires { 0 < d }3181ensures { result = round_int m (from_int n /. from_int d) }3182= let f = Zarith.fdiv n d in3183let r = n - f * d in3184{proof…}3185assert { 0 <= r < d /\ n = f * d + r };3186let ghost q = pure { from_int n /. from_int d } in3187let ghost rd = pure { from_int r /. from_int d } in3188assert { 0.0 <. from_int d };3189assert { from_int n = from_int f *. from_int d +. from_int r };3190assert { q = from_int f +. rd };3191assert { 0.0 <=. rd <. 1.0 by from_int r <. from_int d };3192floor_unique q f;3193assert { q -. from_int f = rd };3194assert { rd = 0.0 <-> r = 0 };3195assert { from_int r = rd *. from_int d };3196half_cmp r d rd;3197assert { 0.0 <=. q <-> 0 <= n };3198{qed}3199match m with3200| RTN -> f3201| RTP -> if r = 0 then f else f + 13202| RTZ -> if n >= 0 || r = 0 then f else f + 13203| RNE ->3204if 2 * r < d then f else if 2 * r > d then f + 13205else if even f then f else f + 13206| RNA ->3207if 2 * r < d then f else if 2 * r > d then f + 13208else if n >= 0 then f + 1 else f3209end3210
The rounding of a finite float to an integer (fp.to_ubv, fp.to_sbv); None for NaN and the infinities
Valid (46ms) (colibri2)let to_integer (m: mode) (x: t) : option int3214ensures { match result with3215| None -> not is_finite x3216| Some n -> is_finite x /\ n = round_int m (to_real x) end }3217= match x.value with3218| Finite _ _ -> Some (round_int_d m (to_dyadic x))3219| _ -> None3220end32213222function fp_rem (x y: t) : t =3223match x.value, y.value with3224| Finite _ _, Finite _ k ->3225if k = 0 then not_a_number x.fmt3226else round_f x.fmt RNE (not is_positive x)3227(Fin (to_real x -. to_real y *.3228from_int (round_int RNE (to_real x /. to_real y))))3229| Finite _ _, (PlusInf | MinusInf) -> x3230| _ -> not_a_number x.fmt3231end3232Valid (385ms) (colibri2 33) (split_vc) (depth 1)3233let remainder (x y: t) : t3234ensures { result = fp_rem x y }3235= match x.value, y.value with3236| Finite _ _, Finite _ k ->3237if k = 0 then mk x.fmt NaN3238else begin3239let dx = to_dyadic x in3240let dy = to_dyadic y in3241{proof…}3242finite_sign y;3243assert { dy.dm <> 0 by dval dy <> 0.0 /\ (dy.dm = 0 -> dval dy = 0.0) };3244pow2r_pos dx.de; pow2r_pos dy.de;3245{qed}3246(* x / y = (dx.dm / dy.dm) 2^(dx.de - dy.de) = n / d *)3247let (n, d) =3248if dx.de >= dy.de then (lsl_int dx.dm (dx.de - dy.de), dy.dm)3249else (dx.dm, lsl_int dy.dm (dy.de - dx.de)) in3250{proof…}3251let ghost n0 = n in3252let ghost d0 = d in3253if dx.de < dy.de then begin3254lsl_mul dy.dm (dy.de - dx.de);3255assert { 0 < power 2 (dy.de - dx.de) };3256assert { d0 <> 0 }3257end;3258{qed}3259let (n, d) = if d < 0 then (- n, - d) else (n, d) in3260{proof…}3261assert { 0 < d };3262if d0 < 0 then begin3263div_scale (from_int n0) (from_int d0) 1.0;3264assert { from_int n = -. from_int n0 /\ from_int d = -. from_int d0 }3265end;3266assert { from_int n /. from_int d = from_int n0 /. from_int d0 };3267let ghost qx = pure { to_real x /. to_real y } in3268if dx.de >= dy.de then begin3269lsl_mul dx.dm (dx.de - dy.de); pow2r_int (dx.de - dy.de);3270pow2r_add dy.de (dx.de - dy.de);3271assert { to_real x = from_int (dx.dm * power 2 (dx.de - dy.de)) *. pow2r dy.de };3272assert { to_real y = from_int dy.dm *. pow2r dy.de };3273div_scale (from_int n0) (from_int d0) (pow2r dy.de)3274end else begin3275lsl_mul dy.dm (dy.de - dx.de); pow2r_int (dy.de - dx.de);3276pow2r_add dx.de (dy.de - dx.de);3277assert { to_real y = from_int (dy.dm * power 2 (dy.de - dx.de)) *. pow2r dx.de };3278assert { to_real x = from_int dx.dm *. pow2r dx.de };3279div_scale (from_int n0) (from_int d0) (pow2r dx.de)3280end;3281assert { qx = from_int n0 /. from_int d0 };3282assert { qx = from_int n /. from_int d };3283{qed}3284let q = round_int_q RNE n d in3285let res = dadd dx (dneg (dmul dy { dm = q; de = 0 })) in3286{proof…}3287pow2r_int 0;3288assert { dval res = to_real x -. to_real y *. from_int q };3289{qed}3290round_d x.fmt RNE (not (is_positive x)) res3291end3292| Finite _ _, (PlusInf | MinusInf) -> x3293| _ -> mk x.fmt NaN3294end3295end3296