library colibrilib.product — module SolveThe solver of the equations between products, Dom_product.SolveAbs (Pivot.WithUnsolved): p1 = p2, where unk1 and unk2 contain the nodes of p1 and p2 that are not known to be different from zero
module Solve1134use int.Int1135use mach.int.Int631136use real.RealInfix1137use real.Abs1138use list.List1139use option.Option1140use colibrilib.ring.Atom1141use colibrilib.stdq.StdQ as Q1142use colibrilib.stda.StdA as A1143use Apow1144use QAssoc1145use PT1146use Prod11471148type solved =1149| AlreadyEqual1150| Contradiction1151| Subst Atom.t t1152
|x| = q
| Unsolved1153
The nodes of p outside unk are not zero
predicate hyp (env: Atom.t -> real) (unk:PT.t) (p:t) =1156valid env p /\ forall k. mem k p -> not has k (bindings unk) -> env k <> 0.01157
The result of the solving of e: a substitution is equivalent to e (the nodes with a negative exponent are not zero)
predicate solves (h: (Atom.t -> real) -> bool) (e: (Atom.t -> real) -> bool)1161(r:solved) =1162match r with1163| AlreadyEqual -> forall env. h env -> e env1164| Contradiction -> forall env. h env -> not (e env)1165| Subst x q -> not mem x q /\1166forall env. h env -> (e env <-> abs (env x) = eval env q /\ valid env q)1167| Unsolved -> true1168end1169
p = 0
Valid (610ms) (colibri2 7) (cvc4) (split_vc) (depth 1)let partial some_zero (unk:PT.t) (p:t) : solved1172ensures { solves (fun env -> hyp env unk p) (fun env -> eval env p = 0.0) result }1173= if is_zero p then AlreadyEqual1174else if PT.is_empty unk then begin1175let lemma ev (env: Atom.t -> real) : unit1176requires { hyp env unk p }1177ensures { eval env p <> 0.0 }1178= eval_zero env p in1179Contradiction1180end else if PT.cardinal unk = 1 then begin1181let x, _ = PT.choose unk in1182assert { forall k. has k (bindings unk) -> k = x1183by match bindings unk with Cons _ Nil -> true | _ -> false end };1184match PT.find_opt x p.poly with1185| None ->1186let lemma ev (env: Atom.t -> real) : unit1187requires { hyp env unk p }1188ensures { eval env p <> 0.0 }1189= eval_zero env p in1190Contradiction1191| Some _ ->1192let z = zero () in1193let lemma ev (env: Atom.t -> real) : unit1194requires { hyp env unk p }1195ensures { eval env p = 0.0 <-> abs (env x) = eval env z /\ valid env z }1196= eval_zero env p in1197Subst x z1198end1199end else Unsolved1200
A node n of l (the bindings of p1) with exp n p1 - exp n p2 = 1
Valid (52ms) (colibri2 8) (split_vc 2) (depth 2)let rec find_one (l:list binding) (p1 p2:t) : option Atom.t1204requires { sorted l }1205requires { forall k. has k l -> ex k l = exp k p1 /\ mem k p1 }1206ensures { match result with1207| None -> true1208| Some n -> mem n p1 /\ exp n p1 -. exp n p2 = 1.01209end }1210variant { l }1211= match l with1212| Nil -> None1213| Cons (k, q1) r ->1214assert { has k l };1215let q2 = match PT.find_opt k p2.poly with None -> Q.of_int 0 | Some q -> q end in1216if Q.equal (Q.sub q1 q2) (Q.of_int 1) then Some k1217else begin1218assert { forall k'. has k' r -> has k' l /\ ex k' r = ex k' l1219by k' = k \/ assoc k' l = assoc k' r };1220find_one r p1 p21221end1222end1223Valid (69ms) (colibri2)1224let ghost apow_root (x q e:real) : unit1225requires { q <> 0.0 /\ 0.0 <=. e }1226ensures { apow x q = e <-> abs x = apow e (1.0 /. q) }1227= {proof…} apow_apow x q (1.0 /. q);1228apow_apow e (1.0 /. q) q;1229assert { q *. (1.0 /. q) = 1.0 /\ (1.0 /. q) *. q = 1.0 };1230apow_one x; apow_one e;1231apow_abs x q;1232if pure { apow x q = e } then assert { abs x = apow e (1.0 /. q) }1233else if pure { abs x = apow e (1.0 /. q) } then1234assert { apow (abs x) q = e } {qed}1235
p1 = p2, p1 and p2 not zero
Valid (1.7s) (colibri2 39) (cvc4) (split_vc 4) (depth 2)let partial non_zero (unk1:PT.t) (p1:t) (unk2:PT.t) (p2:t) : solved1238requires { A.real p1.cst <> 0.0 /\ A.real p2.cst <> 0.0 }1239ensures { solves (fun env -> hyp env unk1 p1 /\ hyp env unk2 p2)1240(fun env -> eval env p1 = eval env p2) result }1241= if PT.is_empty unk1 then1242match find_one (PT.to_list p1.poly) p1 p2 with1243| None -> Unsolved1244| Some n ->1245let p = try div p2 p1 with DivZero -> absurd end in1246let r = remove n p in1247let lemma ev (env: Atom.t -> real) : unit1248requires { hyp env unk1 p1 /\ hyp env unk2 p2 }1249ensures { eval env p1 = eval env p2 <-> abs (env n) = eval env r /\ valid env r }1250= eval_zero env p1;1251assert { exp n p = -. 1.0 };1252assert { env n <> 0.0 };1253apow_inv (abs (env n)); apow_abs (env n) (-. 1.0);1254assert { ok_div p2 p1 env };1255assert { eval env p = eval env p2 /. eval env p1 };1256assert { eval env p = (1.0 /. abs (env n)) *. eval env r } in1257Subst n r1258end1259else if PT.cardinal unk1 = 1 then begin1260let n, _ = PT.choose unk1 in1261assert { forall k. has k (bindings unk1) -> k = n1262by match bindings unk1 with Cons _ Nil -> true | _ -> false end };1263match PT.find_opt n p1.poly, PT.find_opt n p2.poly with1264| Some q, None ->1265let r1 = remove n p1 in1266let p = try div p2 r1 with DivZero -> absurd end in1267let iq = Q.div (Q.of_int 1) q in1268let res = try power_cst iq p with DivZero -> absurd end in1269let lemma ev (env: Atom.t -> real) : unit1270requires { hyp env unk1 p1 /\ hyp env unk2 p2 }1271ensures { eval env p1 = eval env p2 <-> abs (env n) = eval env res /\ valid env res }1272= eval_zero env r1;1273assert { eval env r1 <> 0.0 };1274eval_nonneg env p;1275assert { ok_div p2 r1 env };1276assert { eval env p = eval env p2 /. eval env r1 };1277assert { eval env p1 = apow (env n) (Q.real q) *. eval env r1 };1278assert { eval env p2 = eval env p *. eval env r1 };1279assert { eval env p1 = eval env p2 <-> apow (env n) (Q.real q) = eval env p };1280apow_root (env n) (Q.real q) (eval env p);1281if pure { Q.real q <. 0.0 /\ eval env p = 0.0 } then begin1282assert { env n <> 0.0 };1283apow_nonneg (env n) (Q.real q);1284eval_zero env p;1285let ghost k = any Atom.t ensures { mem result p /\ env result = 0.0 } in1286assert { not mem k r1 };1287assert { exp k r1 = 0.0 };1288assert { exp k p = exp k p2 };1289assert { mem k p2 };1290assert { 0.0 <. exp k p2 };1291assert { 1.0 /. Q.real q <. 0.0 };1292assert { exp k res = Q.real iq *. exp k p };1293assert { exp k res <. 0.0 }1294end else begin1295assert { ok_pow iq p env };1296assert { eval env res = apow (eval env p) (Q.real iq) /\ valid env res }1297end in1298Subst n res1299| _ -> Unsolved1300end1301end else Unsolved1302
All the nodes of p are not zero
predicate all_nz (env: Atom.t -> real) (p:t) =1305valid env p /\ forall k. mem k p -> env k <> 0.01306
p1 = p2, all the nodes of p1 and p2 not zero. A substitution |n| = res has its nodes in p1 and p2, and a non–zero constant
Valid (1.6s) (colibri2 25) (cvc4) (split_vc 3) (depth 3)let all_non_zero (p1:t) (p2:t) : solved1310requires { A.real p1.cst <> 0.0 /\ A.real p2.cst <> 0.0 }1311ensures { solves (fun env -> all_nz env p1 /\ all_nz env p2)1312(fun env -> eval env p1 = eval env p2) result }1313ensures { match result with1314| Subst _ res -> A.real res.cst <> 0.0 /\1315forall k. mem k res -> mem k p1 \/ mem k p21316| _ -> true end }1317= let p = try div p1 p2 with DivZero -> absurd end in1318let lemma ev (env: Atom.t -> real) : unit1319requires { all_nz env p1 /\ all_nz env p2 }1320ensures { eval env p2 <> 0.0 /\ eval env p1 <> 0.0 }1321ensures { eval env p1 = eval env p2 <-> eval env p = 1.0 }1322= eval_zero env p1; eval_zero env p2 in1323match extract p with1324| One -> AlreadyEqual1325| Cst _ -> Contradiction1326| Var q n r ->1327let c = Q.div (Q.of_int (-1)) q in1328let res = try power_cst c r with DivZero -> absurd end in1329let lemma ev (env: Atom.t -> real) : unit1330requires { all_nz env p1 /\ all_nz env p2 }1331ensures { eval env p1 = eval env p2 <-> abs (env n) = eval env res /\ valid env res }1332= eval_zero env r;1333assert { ok_div p1 p2 env };1334assert { eval env p = eval env p1 /. eval env p2 };1335assert { ok1 p env };1336assert { valid env r };1337assert { env n <> 0.0 /\ eval env r <> 0.0 };1338eval_nonneg env r;1339assert { ok_pow c r env };1340assert { eval env res = apow (eval env r) (Q.real c) /\ valid env res };1341apow_root (env n) (Q.real q) (1.0 /. eval env r);1342apow_inv (eval env r);1343apow_apow (eval env r) (-. 1.0) (1.0 /. Q.real q);1344assert { Q.real c = -. 1.0 *. (1.0 /. Q.real q) };1345assert { eval env p = apow (env n) (Q.real q) *. eval env r };1346assert { apow (eval env r) (Q.real c) = apow (1.0 /. eval env r) (1.0 /. Q.real q) };1347assert { eval env p1 = eval env p2 <-> apow (env n) (Q.real q) = 1.0 /. eval env r } in1348Subst n res1349end1350
The nodes k <> n of l are in p2 or have a negative exponent in res
Valid (375ms) (colibri2)let rec covered (l:list binding) (n:Atom.t) (p2 res:t) : bool1354ensures { result -> forall k. has k l -> k <> n ->1355mem k p2 \/ exp k res <. 0.0 }1356variant { l }1357= match l with1358| Nil -> true1359| Cons (k, _) r ->1360let ok =1361if Atom.equal k n then true1362else match PT.find_opt k p2.poly with1363| Some _ -> true1364| None ->1365match PT.find_opt k res.poly with1366| None -> false1367| Some e -> Q.lt e (Q.of_int 0)1368end1369end in1370ok && covered r n p2 res1371end1372
p1 = p2 when the nodes of p2 are not zero: then the nodes of p1 are not zero either, if they are equal
Valid (442ms) (colibri2 5) (cvc4 2) (split_vc) (depth 1)let one_side_non_zero (unk1:PT.t) (p1:t) (p2:t) : solved1376requires { A.real p1.cst <> 0.0 /\ A.real p2.cst <> 0.0 }1377ensures { solves (fun env -> hyp env unk1 p1 /\ all_nz env p2)1378(fun env -> eval env p1 = eval env p2) result }1379= match all_non_zero p1 p2 with1380| Contradiction ->1381let lemma ev (env: Atom.t -> real) : unit1382requires { hyp env unk1 p1 /\ all_nz env p2 }1383ensures { eval env p1 <> eval env p2 }1384= eval_zero env p1; eval_zero env p2 in1385Contradiction1386| Subst n res ->1387if covered (PT.to_list unk1) n p2 res then begin1388let lemma ev (env: Atom.t -> real) : unit1389requires { hyp env unk1 p1 /\ all_nz env p2 }1390ensures { eval env p1 = eval env p2 <-> abs (env n) = eval env res /\ valid env res }1391= eval_zero env p1; eval_zero env p2;1392if pure { abs (env n) = eval env res /\ valid env res } then begin1393assert { forall k. mem k res -> env k <> 0.0 };1394eval_zero env res;1395assert { env n <> 0.0 };1396assert { all_nz env p1 }1397end in1398Subst n res1399end else Unsolved1400| _ -> Unsolved1401end1402Valid (5.7s) (colibri2 9) (cvc4 3) (split_vc 4) (depth 4)1403let partial solve (unk1:PT.t) (p1:t) (unk2:PT.t) (p2:t) : solved1404ensures { solves (fun env -> hyp env unk1 p1 /\ hyp env unk2 p2)1405(fun env -> eval env p1 = eval env p2) result }1406= if is_zero p1 then some_zero unk2 p21407else if is_zero p2 then some_zero unk1 p11408else if PT.is_empty unk1 && PT.is_empty unk2 then all_non_zero p1 p21409else1410let r =1411if PT.is_empty unk2 then one_side_non_zero unk1 p1 p21412else if PT.is_empty unk1 then one_side_non_zero unk2 p2 p11413else Unsolved in1414match r with1415| Unsolved -> non_zero unk1 p1 unk2 p21416| r -> r1417end1418end1419