library colibrilib.congruence — module ExportThe 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.
module Export1198use int.Int1199use real.RealInfix1200use real.FromInt1201use real.Abs1202use real.Truncate1203use option.Option1204use set.Set as S1205use colibrilib.dv.Dv1206use colibrilib.dv.RealSets1207use colibrilib.stdq.StdQ as Q1208use colibrilib.q.Real as Real1209use colibrilib.stda.StdA as A1210use colibrilib.known_bits.KnownBits as KB1211use Congruence1212use colibrilib.spec.Sound1213use colibrilib.spec.Value1214
Raised when the class has no element below (or above) a real: a class that is a single real
exception Singleton1218
The reals of a result of a forward propagation: every real for Top
predicate bmem (x: real) (r: backward t) =1222match r with Top -> true | R c -> S.mem x (gamma c) end1223
The largest element of da that is not above a. Singleton is raised exactly when da is a singleton.
Valid (44ms) (colibri2)let floor_a (a:A.t) (da:t) : A.t1227ensures { Q.real da.div <> 0.0 }1228ensures { value_floor A.real (fun z -> S.mem z (gamma da)) (A.real a) result }1229raises { Singleton -> Q.real da.div = 0.0 }1230= if Q.is_zero da.div then raise Singleton else floor_a_nz a da1231
The smallest element of da that is not below a. Singleton is raised exactly when da is a singleton.
Valid (47ms) (colibri2)let ceil_a (a:A.t) (da:t) : A.t1235ensures { Q.real da.div <> 0.0 }1236ensures { value_ceil A.real (fun z -> S.mem z (gamma da)) (A.real a) result }1237raises { Singleton -> Q.real da.div = 0.0 }1238= if Q.is_zero da.div then raise Singleton else ceil_a_nz a da1239
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)let mod_e_forward (a d:t) : backward t1244ensures { sound2_on bmem (fun _ y -> y <> 0.0) Real.mod_e (R a) (R d) result }1245ensures { match result with1246| R c -> A.rational d.rem1247/\ not (Q.real d.div = 0.0 /\ A.real d.rem = 0.0 /\ Q.real a.div = 0.0)1248/\ S.subset (map2nz (fun (x:real) (y:real) -> Real.mod_e x y) (gamma a) (gamma d)) (gamma c)1249| Top -> not (A.rational d.rem)1250\/ (Q.real d.div = 0.0 /\ A.real d.rem = 0.0 /\ Q.real a.div = 0.0)1251end }1252= match A.view d.rem with1253| A.Irr -> Top1254| A.Rat drem ->1255if Q.is_zero d.div && Q.is_zero drem && Q.is_zero a.div then Top1256else mod_e_forward_nz a d1257end1258
The operations without a defensive version: the contracts of Congruence
Valid (33ms) (colibri2)let integers () : t1262ensures { gamma result = ints }1263ensures { Q.real result.div = 1.0 /\ A.real result.rem = 0.0 }1264= Congruence.integers ()1265Valid (36ms) (colibri2)1266let norm (n:t) : t1267ensures { gamma result = gamma n }1268ensures { exists k:int. A.real result.rem = A.real n.rem +. from_int k *. Q.real n.div }1269= Congruence.norm n1270Valid (33ms) (colibri2)1271let a_divisible (a:A.t) (q:Q.t) : bool1272ensures { result <-> dv (A.real a) (Q.real q) }1273= Congruence.a_divisible a q1274Valid (32ms) (colibri2)1275let inter (x y:t) : option t1276ensures { match result with1277| Some c -> gamma c = S.inter (gamma x) (gamma y)1278| None -> S.is_empty (S.inter (gamma x) (gamma y))1279end }1280= Congruence.inter x y1281Valid (32ms) (colibri2)1282let union (x y:t) : backward t1283ensures { match result with1284| R c -> S.subset (gamma x) (gamma c) /\ S.subset (gamma y) (gamma c)1285/\ (forall c'. S.subset (gamma x) (gamma c') -> S.subset (gamma y) (gamma c')1286-> S.subset (gamma c) (gamma c'))1287/\ Q.is_rat (A.real x.rem -. A.real y.rem)1288| Top -> (forall c'. not (S.subset (gamma x) (gamma c') /\ S.subset (gamma y) (gamma c')))1289/\ not (Q.is_rat (A.real x.rem -. A.real y.rem))1290end }1291= Congruence.union x y1292Valid (19ms) (colibri2)1293let is_included (x y:t) : bool1294ensures { result <-> S.subset (gamma x) (gamma y) }1295= Congruence.is_included x y1296Valid (29ms) (colibri2)1297let is_singleton (c:t) : option A.t1298ensures { match result with1299| Some r -> gamma c = S.singleton (A.real r)1300| None -> Q.real c.div <> 0.01301end }1302= Congruence.is_singleton c1303Valid (35ms) (colibri2)1304let is_integer (c:t) : bool1305ensures { result <-> integral c }1306= Congruence.is_integer c1307Valid (35ms) (colibri2)1308let reduce_integers (c:t) : option t1309ensures { match result with1310| Some r -> gamma r = S.inter ints (gamma c)1311| None -> S.is_empty (S.inter ints (gamma c))1312end }1313= Congruence.reduce_integers c1314Valid (38ms) (colibri2)1315let singleton (v:A.t) : t1316ensures { gamma result = S.singleton (A.real v) }1317ensures { Q.real result.div = 0.0 /\ A.real result.rem = A.real v }1318= Congruence.singleton v1319Valid (35ms) (colibri2)1320let mem (x:A.t) (da:t) : bool1321ensures { result <-> S.mem (A.real x) (gamma da) }1322= Congruence.mem x da1323Valid (30ms) (colibri2)1324let add_cst (q:A.t) (da:t) : t1325ensures { gamma result = image (fun y -> y +. A.real q) (gamma da) }1326= Congruence.add_cst q da1327Valid (36ms) (colibri2)1328let add_forward (da db:t) : t1329ensures { S.subset (map2 (fun x y -> x +. y) (gamma da) (gamma db)) (gamma result) }1330= Congruence.add_forward da db1331Valid (27ms) (colibri2)1332let sub_forward (da db:t) : t1333ensures { S.subset (map2 (fun x y -> x -. y) (gamma da) (gamma db)) (gamma result) }1334= Congruence.sub_forward da db1335Valid (39ms) (colibri2)1336let neg_forward (da:t) : t1337ensures { gamma result = image (fun x -> -. x) (gamma da) }1338ensures { exists k:int. A.real result.rem = -. A.real da.rem +. from_int k *. Q.real da.div }1339= Congruence.neg_forward da1340Valid (38ms) (colibri2)1341let mul_cst (q:Q.t) (da:t) : t1342ensures { S.subset (image (fun x -> x *. Q.real q) (gamma da)) (gamma result) }1343= Congruence.mul_cst q da1344Valid (43ms) (colibri2)1345let mul_forward (da db:t) : backward t1346ensures { match result with1347| R c -> A.rational da.rem /\ A.rational db.rem1348/\ S.subset (map2 (fun x y -> x *. y) (gamma da) (gamma db)) (gamma c)1349| Top -> not (A.rational da.rem /\ A.rational db.rem)1350end }1351= Congruence.mul_forward da db1352Valid (43ms) (colibri2)1353let mul_backward (r:t) (into:option t) (b:t) : backward t1354ensures { match result with1355| R c -> A.rational b.rem /\ A.rational r.rem1356/\ (match into with Some d -> integral d | None -> false end)1357/\ not (dv (A.real b.rem) (Q.gcd_q b.div r.div))1358/\ S.subset (S.inter ints (pre_mul (gamma b) (gamma r))) (gamma c)1359| Top -> not (A.rational b.rem) \/ not (A.rational r.rem)1360\/ (match into with Some d -> not (integral d) | None -> true end)1361\/ dv (A.real b.rem) (Q.gcd_q b.div r.div)1362end }1363= Congruence.mul_backward r into b1364Valid (38ms) (colibri2)1365let mod_e_backward_num (den mod_:t) : backward t1366ensures { match result with1367| R c -> A.rational den.rem1368/\ S.subset (mod_num (gamma den) (gamma mod_)) (gamma c)1369| Top -> not (A.rational den.rem)1370end }1371= Congruence.mod_e_backward_num den mod_1372Valid (38ms) (colibri2)1373let ceil_forward (x:t) : t1374ensures { S.subset (image (fun v -> from_int (Truncate.ceil v)) (gamma x)) (gamma result) }1375= Congruence.ceil_forward x1376Valid (29ms) (colibri2)1377let floor_forward (x:t) : t1378ensures { S.subset (image (fun v -> from_int (Truncate.floor v)) (gamma x)) (gamma result) }1379= Congruence.floor_forward x1380Valid (35ms) (colibri2)1381let truncate_forward (x:t) : t1382ensures { S.subset (image (fun v -> from_int (Truncate.truncate v)) (gamma x)) (gamma result) }1383= Congruence.truncate_forward x1384Valid (35ms) (colibri2)1385let relu_forward (a:t) : backward t1386ensures { match result with1387| R c -> A.rational a.rem1388/\ S.subset (image (fun x -> if x <. 0.0 then 0.0 else x) (gamma a)) (gamma c)1389| Top -> not (A.rational a.rem)1390end }1391= Congruence.relu_forward a1392Valid (44ms) (colibri2)1393let abs_forward (a:t) : backward t1394ensures { match result with1395| R c -> A.rational a.rem1396/\ S.subset (image (fun x -> abs x) (gamma a)) (gamma c)1397| Top -> not (A.rational a.rem)1398end }1399= Congruence.abs_forward a1400Valid (36ms) (colibri2)1401let abs_backward (a:t) : backward t1402ensures { match result with1403| R c -> A.rational a.rem1404/\ S.subset (preimage (fun y -> abs y) (gamma a)) (gamma c)1405| Top -> not (A.rational a.rem)1406end }1407= Congruence.abs_backward a1408Valid (32ms) (colibri2)1409let div_e_forward (a b:t) : t1410ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_e x y)) (gamma a) (gamma b))1411(gamma result) }1412= Congruence.div_e_forward a b1413Valid (32ms) (colibri2)1414let div_f_forward (a b:t) : t1415ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_f x y)) (gamma a) (gamma b))1416(gamma result) }1417= Congruence.div_f_forward a b1418Valid (24ms) (colibri2)1419let div_t_forward (a b:t) : t1420ensures { S.subset (map2nz (fun (x:real) (y:real) -> from_int (Real.div_t x y)) (gamma a) (gamma b))1421(gamma result) }1422= Congruence.div_t_forward a b1423Valid (31ms) (colibri2)1424let to_knownbits (c:t) : KB.t1425ensures { forall n:int. S.mem (from_int n) (gamma c) -> KB.mem n result }1426ensures { result = KB.top <->1427(Q.real c.div = 0.0 \/ not (Real.is_integer (Q.real c.div))1428\/ not (Real.is_integer (A.real c.rem)) \/ odd_div c) }1429= Congruence.to_knownbits c1430Valid (39ms) (colibri2)1431let of_knownbits (k:KB.t) : t1432ensures { forall n:int. KB.mem n k -> S.mem (from_int n) (gamma result) }1433= Congruence.of_knownbits k1434end1435