Common — library colibrilib.congruence — module Export

The functions of Congruence that have a precondition (_nz), made total for the extraction: they test the precondition and raise an exception, or return Top, exactly when it does not hold. The proofs use the functions of Congruence, not these ones.

1198
module Export
1199
use int.Int
1200
use real.RealInfix
1201
use real.FromInt
1202
use real.Abs
1203
use real.Truncate
1204
use option.Option
1205
use set.Set as S
1206
use colibrilib.dv.Dv
1207
use colibrilib.dv.RealSets
1208
use colibrilib.stdq.StdQ as Q
1209
use colibrilib.q.Real as Real
1210
use colibrilib.stda.StdA as A
1211
use colibrilib.known_bits.KnownBits as KB
1212
use Congruence
1213
use colibrilib.spec.Sound
1214
use colibrilib.spec.Value

Raised when the class has no element below (or above) a real: a class that is a single real

1218
exception
Singleton

The reals of a result of a forward propagation: every real for Top

1222
predicate
bmem
(x: real) (r: backward t) =
1223
match r with Top -> true | R c -> S.mem x (gamma c) end

The largest element of da that is not above a. Singleton is raised exactly when da is a singleton.

  Valid (44ms) (colibri2)
1227
let
floor_a
(a:A.t) (da:t) : A.t
1228
ensures { Q.real da.div <> 0.0 }
1229
ensures { value_floor A.real (fun z -> S.mem z (gamma da)) (A.real a) result }
1230
raises { Singleton -> Q.real da.div = 0.0 }
1231
= if Q.is_zero da.div then raise Singleton else floor_a_nz a da

The smallest element of da that is not below a. Singleton is raised exactly when da is a singleton.

  Valid (47ms) (colibri2)
1235
let
ceil_a
(a:A.t) (da:t) : A.t
1236
ensures { Q.real da.div <> 0.0 }
1237
ensures { value_ceil A.real (fun z -> S.mem z (gamma da)) (A.real a) result }
1238
raises { Singleton -> Q.real da.div = 0.0 }
1239
= if Q.is_zero da.div then raise Singleton else ceil_a_nz a da

The remainders mod_e x y of the x of a by the non zero y of d. Top exactly when the representative of d is not rational, or d is the single real zero and a a single real.

  Valid (1.0s) (colibri2)
1244
let
mod_e_forward
(a d:t) : backward t
1245
ensures { sound2_on bmem (fun _ y -> y <> 0.0) Real.mod_e (R a) (R d) result }
1246
ensures { match result with
1247
| R c -> A.rational d.rem
1248
/\ not (Q.real d.div = 0.0 /\ A.real d.rem = 0.0 /\ Q.real a.div = 0.0)
1249
/\ S.subset (map2nz (fun (x:real) (y:real) -> Real.mod_e x y) (gamma a) (gamma d)) (gamma c)
1250
| Top -> not (A.rational d.rem)
1251
\/ (Q.real d.div = 0.0 /\ A.real d.rem = 0.0 /\ Q.real a.div = 0.0)
1252
end }
1253
= match A.view d.rem with
1254
| A.Irr -> Top
1255
| A.Rat drem ->
1256
if Q.is_zero d.div && Q.is_zero drem && Q.is_zero a.div then Top
1257
else mod_e_forward_nz a d
1258
end

The operations without a defensive version: the contracts of Congruence

  Valid (33ms) (colibri2)
1262
let
integers
() : t
1263
ensures { gamma result = ints }
1264
ensures { Q.real result.div = 1.0 /\ A.real result.rem = 0.0 }
1265
= Congruence.integers ()
1266
Valid (36ms) (colibri2)
1267
let
norm
(n:t) : t
1268
ensures { gamma result = gamma n }
1269
ensures { exists k:int. A.real result.rem = A.real n.rem +. from_int k *. Q.real n.div }
1270
= Congruence.norm n
1271
Valid (33ms) (colibri2)
1272
let
a_divisible
(a:A.t) (q:Q.t) : bool
1273
ensures { result <-> dv (A.real a) (Q.real q) }
1274
= Congruence.a_divisible a q
1275
Valid (32ms) (colibri2)
1276
let
inter
(x y:t) : option t
1277
ensures { match result with
1278
| Some c -> gamma c = S.inter (gamma x) (gamma y)
1279
| None -> S.is_empty (S.inter (gamma x) (gamma y))
1280
end }
1281
= Congruence.inter x y
1282
Valid (32ms) (colibri2)
1283
let
union
(x y:t) : backward t
1284
ensures { match result with
1285
| R c -> S.subset (gamma x) (gamma c) /\ S.subset (gamma y) (gamma c)
1286
/\ (forall c'. S.subset (gamma x) (gamma c') -> S.subset (gamma y) (gamma c')
1287
-> S.subset (gamma c) (gamma c'))
1288
/\ Q.is_rat (A.real x.rem -. A.real y.rem)
1289
| Top -> (forall c'. not (S.subset (gamma x) (gamma c') /\ S.subset (gamma y) (gamma c')))
1290
/\ not (Q.is_rat (A.real x.rem -. A.real y.rem))
1291
end }
1292
= Congruence.union x y
1293
Valid (19ms) (colibri2)
1294
let
is_included
(x y:t) : bool
1295
ensures { result <-> S.subset (gamma x) (gamma y) }
1296
= Congruence.is_included x y
1297
Valid (29ms) (colibri2)
1298
let
is_singleton
(c:t) : option A.t
1299
ensures { match result with
1300
| Some r -> gamma c = S.singleton (A.real r)
1301
| None -> Q.real c.div <> 0.0
1302
end }
1303
= Congruence.is_singleton c
1304
Valid (35ms) (colibri2)
1305
let
is_integer
(c:t) : bool
1306
ensures { result <-> integral c }
1307
= Congruence.is_integer c
1308
Valid (35ms) (colibri2)
1309
let
reduce_integers
(c:t) : option t
1310
ensures { match result with
1311
| Some r -> gamma r = S.inter ints (gamma c)
1312
| None -> S.is_empty (S.inter ints (gamma c))
1313
end }
1314
= Congruence.reduce_integers c
1315
Valid (38ms) (colibri2)
1316
let
singleton
(v:A.t) : t
1317
ensures { gamma result = S.singleton (A.real v) }
1318
ensures { Q.real result.div = 0.0 /\ A.real result.rem = A.real v }
1319
= Congruence.singleton v
1320
Valid (35ms) (colibri2)
1321
let
mem
(x:A.t) (da:t) : bool
1322
ensures { result <-> S.mem (A.real x) (gamma da) }
1323
= Congruence.mem x da
1324
Valid (30ms) (colibri2)
1325
let
add_cst
(q:A.t) (da:t) : t
1326
ensures { gamma result = image (fun y -> y +. A.real q) (gamma da) }
1327
= Congruence.add_cst q da
1328
Valid (36ms) (colibri2)
1329
let
add_forward
(da db:t) : t
1330
ensures { S.subset (map2 (fun x y -> x +. y) (gamma da) (gamma db)) (gamma result) }
1331
= Congruence.add_forward da db
1332
Valid (27ms) (colibri2)
1333
let
sub_forward
(da db:t) : t
1334
ensures { S.subset (map2 (fun x y -> x -. y) (gamma da) (gamma db)) (gamma result) }
1335
= Congruence.sub_forward da db
1336
Valid (39ms) (colibri2)
1337
let
neg_forward
(da:t) : t
1338
ensures { gamma result = image (fun x -> -. x) (gamma da) }
1339
ensures { exists k:int. A.real result.rem = -. A.real da.rem +. from_int k *. Q.real da.div }
1340
= Congruence.neg_forward da
1341
Valid (38ms) (colibri2)
1342
let
mul_cst
(q:Q.t) (da:t) : t
1343
ensures { S.subset (image (fun x -> x *. Q.real q) (gamma da)) (gamma result) }
1344
= Congruence.mul_cst q da
1345
Valid (43ms) (colibri2)
1346
let
mul_forward
(da db:t) : backward t
1347
ensures { match result with
1348
| R c -> A.rational da.rem /\ A.rational db.rem
1349
/\ S.subset (map2 (fun x y -> x *. y) (gamma da) (gamma db)) (gamma c)
1350
| Top -> not (A.rational da.rem /\ A.rational db.rem)
1351
end }
1352
= Congruence.mul_forward da db
1353
Valid (43ms) (colibri2)
1354
let
mul_backward
(r:t) (into:option t) (b:t) : backward t
1355
ensures { match result with
1356
| R c -> A.rational b.rem /\ A.rational r.rem
1357
/\ (match into with Some d -> integral d | None -> false end)
1358
/\ not (dv (A.real b.rem) (Q.gcd_q b.div r.div))
1359
/\ S.subset (S.inter ints (pre_mul (gamma b) (gamma r))) (gamma c)
1360
| Top -> not (A.rational b.rem) \/ not (A.rational r.rem)
1361
\/ (match into with Some d -> not (integral d) | None -> true end)
1362
\/ dv (A.real b.rem) (Q.gcd_q b.div r.div)
1363
end }
1364
= Congruence.mul_backward r into b
1365
Valid (38ms) (colibri2)
1366
let
mod_e_backward_num
(den mod_:t) : backward t
1367
ensures { match result with
1368
| R c -> A.rational den.rem
1369
/\ S.subset (mod_num (gamma den) (gamma mod_)) (gamma c)
1370
| Top -> not (A.rational den.rem)
1371
end }
1372
= Congruence.mod_e_backward_num den mod_
1373
Valid (38ms) (colibri2)
1374
let
ceil_forward
(x:t) : t
1375
ensures { S.subset (image (fun v -> from_int (Truncate.ceil v)) (gamma x)) (gamma result) }
1376
= Congruence.ceil_forward x
1377
Valid (29ms) (colibri2)
1378
let
floor_forward
(x:t) : t
1379
ensures { S.subset (image (fun v -> from_int (Truncate.floor v)) (gamma x)) (gamma result) }
1380
= Congruence.floor_forward x
1381
Valid (35ms) (colibri2)
1382
let
truncate_forward
(x:t) : t
1383
ensures { S.subset (image (fun v -> from_int (Truncate.truncate v)) (gamma x)) (gamma result) }
1384
= Congruence.truncate_forward x
1385
Valid (35ms) (colibri2)
1386
let
relu_forward
(a:t) : backward t
1387
ensures { match result with
1388
| R c -> A.rational a.rem
1389
/\ S.subset (image (fun x -> if x <. 0.0 then 0.0 else x) (gamma a)) (gamma c)
1390
| Top -> not (A.rational a.rem)
1391
end }
1392
= Congruence.relu_forward a
1393
Valid (44ms) (colibri2)
1394
let
abs_forward
(a:t) : backward t
1395
ensures { match result with
1396
| R c -> A.rational a.rem
1397
/\ S.subset (image (fun x -> abs x) (gamma a)) (gamma c)
1398
| Top -> not (A.rational a.rem)
1399
end }
1400
= Congruence.abs_forward a
1401
Valid (36ms) (colibri2)
1402
let
abs_backward
(a:t) : backward t
1403
ensures { match result with
1404
| R c -> A.rational a.rem
1405
/\ S.subset (preimage (fun y -> abs y) (gamma a)) (gamma c)
1406
| Top -> not (A.rational a.rem)
1407
end }
1408
= Congruence.abs_backward a
1409
Valid (32ms) (colibri2)
1410
let
div_e_forward
(a b:t) : t
1411
ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_e x y)) (gamma a) (gamma b))
1412
(gamma result) }
1413
= Congruence.div_e_forward a b
1414
Valid (32ms) (colibri2)
1415
let
div_f_forward
(a b:t) : t
1416
ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_f x y)) (gamma a) (gamma b))
1417
(gamma result) }
1418
= Congruence.div_f_forward a b
1419
Valid (24ms) (colibri2)
1420
let
div_t_forward
(a b:t) : t
1421
ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_t x y)) (gamma a) (gamma b))
1422
(gamma result) }
1423
= Congruence.div_t_forward a b
1424
Valid (31ms) (colibri2)
1425
let
to_knownbits
(c:t) : KB.t
1426
ensures { forall n:int. S.mem (from_int n) (gamma c) -> KB.mem n result }
1427
ensures { result = KB.top <->
1428
(Q.real c.div = 0.0 \/ not (Real.is_integer (Q.real c.div))
1429
\/ not (Real.is_integer (A.real c.rem)) \/ odd_div c) }
1430
= Congruence.to_knownbits c
1431
Valid (39ms) (colibri2)
1432
let
of_knownbits
(k:KB.t) : t
1433
ensures { forall n:int. KB.mem n k -> S.mem (from_int n) (gamma result) }
1434
= Congruence.of_knownbits k
1435
end