Common — library colibrilib.product — module Solve

The 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

1134
module Solve
1135
use int.Int
1136
use mach.int.Int63
1137
use real.RealInfix
1138
use real.Abs
1139
use list.List
1140
use option.Option
1141
use colibrilib.ring.Atom
1142
use colibrilib.stdq.StdQ as Q
1143
use colibrilib.stda.StdA as A
1144
use Apow
1145
use QAssoc
1146
use PT
1147
use Prod
1148
1149
type
solved
=
1150
|
AlreadyEqual
1151
|
Contradiction
1152
|
Subst
Atom.t t

|x| = q

1153
|
Unsolved

The nodes of p outside unk are not zero

1156
predicate
hyp
(env: Atom.t -> real) (unk:PT.t) (p:t) =
1157
valid env p /\ forall k. mem k p -> not has k (bindings unk) -> env k <> 0.0

The result of the solving of e: a substitution is equivalent to e (the nodes with a negative exponent are not zero)

1161
predicate
solves
(h: (Atom.t -> real) -> bool) (e: (Atom.t -> real) -> bool)
1162
(r:solved) =
1163
match r with
1164
| AlreadyEqual -> forall env. h env -> e env
1165
| Contradiction -> forall env. h env -> not (e env)
1166
| Subst x q -> not mem x q /\
1167
forall env. h env -> (e env <-> abs (env x) = eval env q /\ valid env q)
1168
| Unsolved -> true
1169
end

p = 0

  Valid (610ms) (colibri2 7) (cvc4) (split_vc) (depth 1)
1172
let partial
some_zero
(unk:PT.t) (p:t) : solved
1173
ensures { solves (fun env -> hyp env unk p) (fun env -> eval env p = 0.0) result }
1174
= if is_zero p then AlreadyEqual
1175
else if PT.is_empty unk then begin
1176
let lemma ev (env: Atom.t -> real) : unit
1177
requires { hyp env unk p }
1178
ensures { eval env p <> 0.0 }
1179
= eval_zero env p in
1180
Contradiction
1181
end else if PT.cardinal unk = 1 then begin
1182
let x, _ = PT.choose unk in
1183
assert { forall k. has k (bindings unk) -> k = x
1184
by match bindings unk with Cons _ Nil -> true | _ -> false end };
1185
match PT.find_opt x p.poly with
1186
| None ->
1187
let lemma ev (env: Atom.t -> real) : unit
1188
requires { hyp env unk p }
1189
ensures { eval env p <> 0.0 }
1190
= eval_zero env p in
1191
Contradiction
1192
| Some _ ->
1193
let z = zero () in
1194
let lemma ev (env: Atom.t -> real) : unit
1195
requires { hyp env unk p }
1196
ensures { eval env p = 0.0 <-> abs (env x) = eval env z /\ valid env z }
1197
= eval_zero env p in
1198
Subst x z
1199
end
1200
end else Unsolved

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)
1204
let rec
find_one
(l:list binding) (p1 p2:t) : option Atom.t
1205
requires { sorted l }
1206
requires { forall k. has k l -> ex k l = exp k p1 /\ mem k p1 }
1207
ensures { match result with
1208
| None -> true
1209
| Some n -> mem n p1 /\ exp n p1 -. exp n p2 = 1.0
1210
end }
1211
variant { l }
1212
= match l with
1213
| Nil -> None
1214
| Cons (k, q1) r ->
1215
assert { has k l };
1216
let q2 = match PT.find_opt k p2.poly with None -> Q.of_int 0 | Some q -> q end in
1217
if Q.equal (Q.sub q1 q2) (Q.of_int 1) then Some k
1218
else begin
1219
assert { forall k'. has k' r -> has k' l /\ ex k' r = ex k' l
1220
by k' = k \/ assoc k' l = assoc k' r };
1221
find_one r p1 p2
1222
end
1223
end
1224
Valid (69ms) (colibri2)
1225
let ghost
apow_root
(x q e:real) : unit
1226
requires { q <> 0.0 /\ 0.0 <=. e }
1227
ensures { apow x q = e <-> abs x = apow e (1.0 /. q) }
1228
= {proof…} apow_apow x q (1.0 /. q);
1229
apow_apow e (1.0 /. q) q;
1230
assert { q *. (1.0 /. q) = 1.0 /\ (1.0 /. q) *. q = 1.0 };
1231
apow_one x; apow_one e;
1232
apow_abs x q;
1233
if pure { apow x q = e } then assert { abs x = apow e (1.0 /. q) }
1234
else if pure { abs x = apow e (1.0 /. q) } then
1235
assert { apow (abs x) q = e } {qed}

p1 = p2, p1 and p2 not zero

  Valid (1.7s) (colibri2 39) (cvc4) (split_vc 4) (depth 2)
1238
let partial
non_zero
(unk1:PT.t) (p1:t) (unk2:PT.t) (p2:t) : solved
1239
requires { A.real p1.cst <> 0.0 /\ A.real p2.cst <> 0.0 }
1240
ensures { solves (fun env -> hyp env unk1 p1 /\ hyp env unk2 p2)
1241
(fun env -> eval env p1 = eval env p2) result }
1242
= if PT.is_empty unk1 then
1243
match find_one (PT.to_list p1.poly) p1 p2 with
1244
| None -> Unsolved
1245
| Some n ->
1246
let p = try div p2 p1 with DivZero -> absurd end in
1247
let r = remove n p in
1248
let lemma ev (env: Atom.t -> real) : unit
1249
requires { hyp env unk1 p1 /\ hyp env unk2 p2 }
1250
ensures { eval env p1 = eval env p2 <-> abs (env n) = eval env r /\ valid env r }
1251
= eval_zero env p1;
1252
assert { exp n p = -. 1.0 };
1253
assert { env n <> 0.0 };
1254
apow_inv (abs (env n)); apow_abs (env n) (-. 1.0);
1255
assert { ok_div p2 p1 env };
1256
assert { eval env p = eval env p2 /. eval env p1 };
1257
assert { eval env p = (1.0 /. abs (env n)) *. eval env r } in
1258
Subst n r
1259
end
1260
else if PT.cardinal unk1 = 1 then begin
1261
let n, _ = PT.choose unk1 in
1262
assert { forall k. has k (bindings unk1) -> k = n
1263
by match bindings unk1 with Cons _ Nil -> true | _ -> false end };
1264
match PT.find_opt n p1.poly, PT.find_opt n p2.poly with
1265
| Some q, None ->
1266
let r1 = remove n p1 in
1267
let p = try div p2 r1 with DivZero -> absurd end in
1268
let iq = Q.div (Q.of_int 1) q in
1269
let res = try power_cst iq p with DivZero -> absurd end in
1270
let lemma ev (env: Atom.t -> real) : unit
1271
requires { hyp env unk1 p1 /\ hyp env unk2 p2 }
1272
ensures { eval env p1 = eval env p2 <-> abs (env n) = eval env res /\ valid env res }
1273
= eval_zero env r1;
1274
assert { eval env r1 <> 0.0 };
1275
eval_nonneg env p;
1276
assert { ok_div p2 r1 env };
1277
assert { eval env p = eval env p2 /. eval env r1 };
1278
assert { eval env p1 = apow (env n) (Q.real q) *. eval env r1 };
1279
assert { eval env p2 = eval env p *. eval env r1 };
1280
assert { eval env p1 = eval env p2 <-> apow (env n) (Q.real q) = eval env p };
1281
apow_root (env n) (Q.real q) (eval env p);
1282
if pure { Q.real q <. 0.0 /\ eval env p = 0.0 } then begin
1283
assert { env n <> 0.0 };
1284
apow_nonneg (env n) (Q.real q);
1285
eval_zero env p;
1286
let ghost k = any Atom.t ensures { mem result p /\ env result = 0.0 } in
1287
assert { not mem k r1 };
1288
assert { exp k r1 = 0.0 };
1289
assert { exp k p = exp k p2 };
1290
assert { mem k p2 };
1291
assert { 0.0 <. exp k p2 };
1292
assert { 1.0 /. Q.real q <. 0.0 };
1293
assert { exp k res = Q.real iq *. exp k p };
1294
assert { exp k res <. 0.0 }
1295
end else begin
1296
assert { ok_pow iq p env };
1297
assert { eval env res = apow (eval env p) (Q.real iq) /\ valid env res }
1298
end in
1299
Subst n res
1300
| _ -> Unsolved
1301
end
1302
end else Unsolved

All the nodes of p are not zero

1305
predicate
all_nz
(env: Atom.t -> real) (p:t) =
1306
valid env p /\ forall k. mem k p -> env k <> 0.0

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)
1310
let
all_non_zero
(p1:t) (p2:t) : solved
1311
requires { A.real p1.cst <> 0.0 /\ A.real p2.cst <> 0.0 }
1312
ensures { solves (fun env -> all_nz env p1 /\ all_nz env p2)
1313
(fun env -> eval env p1 = eval env p2) result }
1314
ensures { match result with
1315
| Subst _ res -> A.real res.cst <> 0.0 /\
1316
forall k. mem k res -> mem k p1 \/ mem k p2
1317
| _ -> true end }
1318
= let p = try div p1 p2 with DivZero -> absurd end in
1319
let lemma ev (env: Atom.t -> real) : unit
1320
requires { all_nz env p1 /\ all_nz env p2 }
1321
ensures { eval env p2 <> 0.0 /\ eval env p1 <> 0.0 }
1322
ensures { eval env p1 = eval env p2 <-> eval env p = 1.0 }
1323
= eval_zero env p1; eval_zero env p2 in
1324
match extract p with
1325
| One -> AlreadyEqual
1326
| Cst _ -> Contradiction
1327
| Var q n r ->
1328
let c = Q.div (Q.of_int (-1)) q in
1329
let res = try power_cst c r with DivZero -> absurd end in
1330
let lemma ev (env: Atom.t -> real) : unit
1331
requires { all_nz env p1 /\ all_nz env p2 }
1332
ensures { eval env p1 = eval env p2 <-> abs (env n) = eval env res /\ valid env res }
1333
= eval_zero env r;
1334
assert { ok_div p1 p2 env };
1335
assert { eval env p = eval env p1 /. eval env p2 };
1336
assert { ok1 p env };
1337
assert { valid env r };
1338
assert { env n <> 0.0 /\ eval env r <> 0.0 };
1339
eval_nonneg env r;
1340
assert { ok_pow c r env };
1341
assert { eval env res = apow (eval env r) (Q.real c) /\ valid env res };
1342
apow_root (env n) (Q.real q) (1.0 /. eval env r);
1343
apow_inv (eval env r);
1344
apow_apow (eval env r) (-. 1.0) (1.0 /. Q.real q);
1345
assert { Q.real c = -. 1.0 *. (1.0 /. Q.real q) };
1346
assert { eval env p = apow (env n) (Q.real q) *. eval env r };
1347
assert { apow (eval env r) (Q.real c) = apow (1.0 /. eval env r) (1.0 /. Q.real q) };
1348
assert { eval env p1 = eval env p2 <-> apow (env n) (Q.real q) = 1.0 /. eval env r } in
1349
Subst n res
1350
end

The nodes k <> n of l are in p2 or have a negative exponent in res

  Valid (375ms) (colibri2)
1354
let rec
covered
(l:list binding) (n:Atom.t) (p2 res:t) : bool
1355
ensures { result -> forall k. has k l -> k <> n ->
1356
mem k p2 \/ exp k res <. 0.0 }
1357
variant { l }
1358
= match l with
1359
| Nil -> true
1360
| Cons (k, _) r ->
1361
let ok =
1362
if Atom.equal k n then true
1363
else match PT.find_opt k p2.poly with
1364
| Some _ -> true
1365
| None ->
1366
match PT.find_opt k res.poly with
1367
| None -> false
1368
| Some e -> Q.lt e (Q.of_int 0)
1369
end
1370
end in
1371
ok && covered r n p2 res
1372
end

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)
1376
let
one_side_non_zero
(unk1:PT.t) (p1:t) (p2:t) : solved
1377
requires { A.real p1.cst <> 0.0 /\ A.real p2.cst <> 0.0 }
1378
ensures { solves (fun env -> hyp env unk1 p1 /\ all_nz env p2)
1379
(fun env -> eval env p1 = eval env p2) result }
1380
= match all_non_zero p1 p2 with
1381
| Contradiction ->
1382
let lemma ev (env: Atom.t -> real) : unit
1383
requires { hyp env unk1 p1 /\ all_nz env p2 }
1384
ensures { eval env p1 <> eval env p2 }
1385
= eval_zero env p1; eval_zero env p2 in
1386
Contradiction
1387
| Subst n res ->
1388
if covered (PT.to_list unk1) n p2 res then begin
1389
let lemma ev (env: Atom.t -> real) : unit
1390
requires { hyp env unk1 p1 /\ all_nz env p2 }
1391
ensures { eval env p1 = eval env p2 <-> abs (env n) = eval env res /\ valid env res }
1392
= eval_zero env p1; eval_zero env p2;
1393
if pure { abs (env n) = eval env res /\ valid env res } then begin
1394
assert { forall k. mem k res -> env k <> 0.0 };
1395
eval_zero env res;
1396
assert { env n <> 0.0 };
1397
assert { all_nz env p1 }
1398
end in
1399
Subst n res
1400
end else Unsolved
1401
| _ -> Unsolved
1402
end
1403
Valid (5.7s) (colibri2 9) (cvc4 3) (split_vc 4) (depth 4)
1404
let partial
solve
(unk1:PT.t) (p1:t) (unk2:PT.t) (p2:t) : solved
1405
ensures { solves (fun env -> hyp env unk1 p1 /\ hyp env unk2 p2)
1406
(fun env -> eval env p1 = eval env p2) result }
1407
= if is_zero p1 then some_zero unk2 p2
1408
else if is_zero p2 then some_zero unk1 p1
1409
else if PT.is_empty unk1 && PT.is_empty unk2 then all_non_zero p1 p2
1410
else
1411
let r =
1412
if PT.is_empty unk2 then one_side_non_zero unk1 p1 p2
1413
else if PT.is_empty unk1 then one_side_non_zero unk2 p2 p1
1414
else Unsolved in
1415
match r with
1416
| Unsolved -> non_zero unk1 p1 unk2 p2
1417
| r -> r
1418
end
1419
end