Common — library colibrilib.fbin — module Integral

The rounding of a rational to an integer, and the remainder

round_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.

3137
module Integral
3138
use int.Int
3139
use int.Power
3140
use int.EuclideanDivision
3141
use real.RealInfix
3142
use real.FromInt
3143
use real.Truncate
3144
use option.Option
3145
use colibrilib.fp.Widen
3146
use colibrilib.fp.Ereal
3147
use colibrilib.zarith.Z as Zarith
3148
use colibrilib.zarith.Zbit
3149
use colibrilib.zbit.ZbitInt
3150
use Pow2r
3151
use Format
3152
use Float
3153
use Round
3154
use Impl
3155
Valid (412ms) (cvc5)
3156
let
dneg
(d: dyadic) : dyadic
3157
ensures { dval result = -. dval d }
3158
= { dm = - d.dm; de = d.de }
3159
Valid (308ms) (colibri2)
3160
let ghost
half_cmp
(r d: int) (rd: real) : unit
3161
requires { 0 < d /\ from_int r = rd *. from_int d }
3162
ensures { rd <. 0.5 <-> 2 * r < d }
3163
ensures { 0.5 <. rd <-> d < 2 * r }
3164
= {proof…}
3165
assert { from_int (2 * r) = 2.0 *. rd *. from_int d };
3166
assert { 2 * r < d <-> (2.0 *. rd) *. from_int d <. 1.0 *. from_int d };
3167
assert { d < 2 * r <-> 1.0 *. from_int d <. (2.0 *. rd) *. from_int d }
3168
{qed}
3169
Valid (53ms) (colibri2 5) (split_vc) (depth 1)
3170
let ghost
div_scale
(a b c: real) : unit
3171
requires { b <> 0.0 /\ c <> 0.0 }
3172
ensures { (a *. c) /. (b *. c) = a /. b }
3173
ensures { (-. a) /. (-. b) = a /. b }
3174
= {proof…}
3175
assert { (a *. c) /. (b *. c) = a /. b };
3176
assert { (-. a) = a *. (-. 1.0) /\ (-. b) = b *. (-. 1.0) };
3177
assert { (a *. (-. 1.0)) /. (b *. (-. 1.0)) = a /. b }
3178
{qed}
3179
Valid (542ms) (colibri2 12) (cvc5) (split_vc) (depth 1)
3180
let
round_int_q
(m: mode) (n d: int) : int
3181
requires { 0 < d }
3182
ensures { result = round_int m (from_int n /. from_int d) }
3183
= let f = Zarith.fdiv n d in
3184
let r = n - f * d in
3185
{proof…}
3186
assert { 0 <= r < d /\ n = f * d + r };
3187
let ghost q = pure { from_int n /. from_int d } in
3188
let ghost rd = pure { from_int r /. from_int d } in
3189
assert { 0.0 <. from_int d };
3190
assert { from_int n = from_int f *. from_int d +. from_int r };
3191
assert { q = from_int f +. rd };
3192
assert { 0.0 <=. rd <. 1.0 by from_int r <. from_int d };
3193
floor_unique q f;
3194
assert { q -. from_int f = rd };
3195
assert { rd = 0.0 <-> r = 0 };
3196
assert { from_int r = rd *. from_int d };
3197
half_cmp r d rd;
3198
assert { 0.0 <=. q <-> 0 <= n };
3199
{qed}
3200
match m with
3201
| RTN -> f
3202
| RTP -> if r = 0 then f else f + 1
3203
| RTZ -> if n >= 0 || r = 0 then f else f + 1
3204
| RNE ->
3205
if 2 * r < d then f else if 2 * r > d then f + 1
3206
else if even f then f else f + 1
3207
| RNA ->
3208
if 2 * r < d then f else if 2 * r > d then f + 1
3209
else if n >= 0 then f + 1 else f
3210
end

The rounding of a finite float to an integer (fp.to_ubv, fp.to_sbv); None for NaN and the infinities

  Valid (46ms) (colibri2)
3214
let
to_integer
(m: mode) (x: t) : option int
3215
ensures { match result with
3216
| None -> not is_finite x
3217
| Some n -> is_finite x /\ n = round_int m (to_real x) end }
3218
= match x.value with
3219
| Finite _ _ -> Some (round_int_d m (to_dyadic x))
3220
| _ -> None
3221
end
3222
3223
function
fp_rem
(x y: t) : t =
3224
match x.value, y.value with
3225
| Finite _ _, Finite _ k ->
3226
if k = 0 then not_a_number x.fmt
3227
else round_f x.fmt RNE (not is_positive x)
3228
(Fin (to_real x -. to_real y *.
3229
from_int (round_int RNE (to_real x /. to_real y))))
3230
| Finite _ _, (PlusInf | MinusInf) -> x
3231
| _ -> not_a_number x.fmt
3232
end
3233
Valid (385ms) (colibri2 33) (split_vc) (depth 1)
3234
let
remainder
(x y: t) : t
3235
ensures { result = fp_rem x y }
3236
= match x.value, y.value with
3237
| Finite _ _, Finite _ k ->
3238
if k = 0 then mk x.fmt NaN
3239
else begin
3240
let dx = to_dyadic x in
3241
let dy = to_dyadic y in
3242
{proof…}
3243
finite_sign y;
3244
assert { dy.dm <> 0 by dval dy <> 0.0 /\ (dy.dm = 0 -> dval dy = 0.0) };
3245
pow2r_pos dx.de; pow2r_pos dy.de;
3246
{qed}
3247
(* x / y = (dx.dm / dy.dm) 2^(dx.de - dy.de) = n / d *)
3248
let (n, d) =
3249
if dx.de >= dy.de then (lsl_int dx.dm (dx.de - dy.de), dy.dm)
3250
else (dx.dm, lsl_int dy.dm (dy.de - dx.de)) in
3251
{proof…}
3252
let ghost n0 = n in
3253
let ghost d0 = d in
3254
if dx.de < dy.de then begin
3255
lsl_mul dy.dm (dy.de - dx.de);
3256
assert { 0 < power 2 (dy.de - dx.de) };
3257
assert { d0 <> 0 }
3258
end;
3259
{qed}
3260
let (n, d) = if d < 0 then (- n, - d) else (n, d) in
3261
{proof…}
3262
assert { 0 < d };
3263
if d0 < 0 then begin
3264
div_scale (from_int n0) (from_int d0) 1.0;
3265
assert { from_int n = -. from_int n0 /\ from_int d = -. from_int d0 }
3266
end;
3267
assert { from_int n /. from_int d = from_int n0 /. from_int d0 };
3268
let ghost qx = pure { to_real x /. to_real y } in
3269
if dx.de >= dy.de then begin
3270
lsl_mul dx.dm (dx.de - dy.de); pow2r_int (dx.de - dy.de);
3271
pow2r_add dy.de (dx.de - dy.de);
3272
assert { to_real x = from_int (dx.dm * power 2 (dx.de - dy.de)) *. pow2r dy.de };
3273
assert { to_real y = from_int dy.dm *. pow2r dy.de };
3274
div_scale (from_int n0) (from_int d0) (pow2r dy.de)
3275
end else begin
3276
lsl_mul dy.dm (dy.de - dx.de); pow2r_int (dy.de - dx.de);
3277
pow2r_add dx.de (dy.de - dx.de);
3278
assert { to_real y = from_int (dy.dm * power 2 (dy.de - dx.de)) *. pow2r dx.de };
3279
assert { to_real x = from_int dx.dm *. pow2r dx.de };
3280
div_scale (from_int n0) (from_int d0) (pow2r dx.de)
3281
end;
3282
assert { qx = from_int n0 /. from_int d0 };
3283
assert { qx = from_int n /. from_int d };
3284
{qed}
3285
let q = round_int_q RNE n d in
3286
let res = dadd dx (dneg (dmul dy { dm = q; de = 0 })) in
3287
{proof…}
3288
pow2r_int 0;
3289
assert { dval res = to_real x -. to_real y *. from_int q };
3290
{qed}
3291
round_d x.fmt RNE (not (is_positive x)) res
3292
end
3293
| Finite _ _, (PlusInf | MinusInf) -> x
3294
| _ -> mk x.fmt NaN
3295
end
3296
end