Common — library colibrilib.ring — module Poly

Polynomials: strictly sorted lists of (monomial, non zero coefficient)

141
module Poly
142
use int.Int
143
use mach.int.Int63
144
use real.RealInfix
145
use list.List
146
use list.Mem
147
use Atom
148
use Mono
149
use option.Option
150
use colibrilib.stda.StdA as A
151
152
type
term
= (mono, A.t)
153
type
poly
= list term

m is the monomial of a term of p

156
predicate
has
(m:mono) (p:poly) =
157
match p with
158
| Nil -> false
159
| Cons (m', _) r -> m = m' \/ has m r
160
end

every monomial of p is above m

163
predicate
above
(m:mono) (p:poly) = forall m'. has m' p -> mlt m m'
164
165
predicate
wf
(p:poly) =
166
match p with
167
| Nil -> true
168
| Cons (m, c) r -> A.real c <> 0.0 /\ sorted m /\ above m r /\ wf r
169
end
170
171
function
eval
(env: Atom.t -> real) (p:poly) : real =
172
match p with
173
| Nil -> 0.0
174
| Cons (m, c) r -> A.real c *. evalm env m +. eval env r
175
end
176
Valid (21ms) (colibri2)
177
let ghost
above_trans
(m1 m2:mono) (p:poly) : unit
178
requires { mlt m1 m2 }
179
requires { above m2 p }
180
ensures { above m1 p }
181
= let lemma pw (m:mono) : unit
182
requires { has m p }
183
ensures { mlt m1 m }
184
= mlt_trans m1 m2 m in
185
()
186
Valid (21ms) (colibri2)
187
let
zero
() : poly
188
ensures { wf result }
189
ensures { forall env. eval env result = 0.0 }
190
= Nil

The constant c

  Valid (36ms) (colibri2)
193
let
cst
(c:A.t) : poly
194
ensures { wf result }
195
ensures { forall env. eval env result = A.real c }
196
= if A.equal c (A.of_int 0) then Nil else Cons (Nil, c) Nil

The atom a

  Valid (36ms) (colibri2)
199
let
var
(a:Atom.t) : poly
200
ensures { wf result }
201
ensures { forall env. eval env result = env a }
202
= Cons (Cons a Nil, A.of_int 1) Nil

The sum. The monomials of the result are those of p or q

  Valid (1.4s) (colibri2 18) (cvc4) (cvc5) (split_vc 4) (depth 4)
205
let rec
add
(p q:poly) : poly
206
requires { wf p /\ wf q }
207
ensures { wf result }
208
ensures { forall m. has m result -> has m p \/ has m q }
209
ensures { forall env. eval env result = eval env p +. eval env q }
210
variant { p, q }
211
= match p, q with
212
| Nil, _ -> q
213
| _, Nil -> p
214
| Cons (m1, c1) r1, Cons (m2, c2) r2 ->
215
let c = Mono.compare m1 m2 in
216
if c < 0 then begin
217
let r = add r1 q in
218
mlt_irrefl m1;
219
let lemma ab (m:mono) : unit
220
requires { has m r }
221
ensures { mlt m1 m }
222
= if pure { has m q } then begin
223
if pure { m <> m2 } then mlt_trans m1 m2 m
224
end in
225
Cons (m1, c1) r
226
end else if c > 0 then begin
227
let r = add p r2 in
228
let lemma ab (m:mono) : unit
229
requires { has m r }
230
ensures { mlt m2 m }
231
= if pure { has m p } then begin
232
if pure { m <> m1 } then mlt_trans m2 m1 m
233
end in
234
Cons (m2, c2) r
235
end else begin
236
let r = add r1 r2 in
237
let s = A.add c1 c2 in
238
if A.equal s (A.of_int 0) then r else Cons (m1, s) r
239
end
240
end

The product by the non zero constant k

  Valid (341ms) (colibri2)
243
let rec
scale
(k:A.t) (p:poly) : poly
244
requires { A.real k <> 0.0 }
245
requires { wf p }
246
ensures { wf result }
247
ensures { forall m. has m result <-> has m p }
248
ensures { forall env. eval env result = A.real k *. eval env p }
249
variant { p }
250
= match p with
251
| Nil -> Nil
252
| Cons (m, c) r ->
253
let c' = A.mul k c in
254
assert { A.real c' <> 0.0 };
255
Cons (m, c') (scale k r)
256
end
257
Valid (43ms) (colibri2)
258
let
neg
(p:poly) : poly
259
requires { wf p }
260
ensures { wf result }
261
ensures { forall m. has m result <-> has m p }
262
ensures { forall env. eval env result = -. eval env p }
263
= scale (A.of_int (-1)) p
264
Valid (51ms) (colibri2)
265
let
sub
(p q:poly) : poly
266
requires { wf p /\ wf q }
267
ensures { wf result }
268
ensures { forall env. eval env result = eval env p -. eval env q }
269
= add p (neg q)

The product of the term c * m and p

  Valid (40ms) (colibri2 12) (split_vc) (depth 1)
272
let rec
mul_term
(m:mono) (c:A.t) (p:poly) : poly
273
requires { sorted m /\ A.real c <> 0.0 /\ wf p }
274
ensures { wf result }
275
ensures { forall env. eval env result = A.real c *. evalm env m *. eval env p }
276
variant { p }
277
= match p with
278
| Nil -> Nil
279
| Cons (m', c') r ->
280
let c'' = A.mul c c' in
281
assert { A.real c'' <> 0.0 };
282
let m'' = Mono.mul m m' in
283
let t = Cons (m'', c'') Nil in
284
let rest = mul_term m c r in
285
let res = add t rest in
286
let lemma ev (env: Atom.t -> real) : unit
287
ensures { eval env res = A.real c *. evalm env m *. eval env p }
288
= let x = A.real c in
289
let y = A.real c' in
290
let em = evalm env m in
291
let em' = evalm env m' in
292
let er = eval env r in
293
assert { eval env t = (x *. y) *. (em *. em') };
294
assert { eval env rest = x *. em *. er };
295
assert { eval env p = y *. em' +. er };
296
assert { x *. em *. (y *. em' +. er) = (x *. y) *. (em *. em') +. x *. em *. er } in
297
res
298
end
299
Valid (107ms) (colibri2)
300
let rec
mul
(p q:poly) : poly
301
requires { wf p /\ wf q }
302
ensures { wf result }
303
ensures { forall env. eval env result = eval env p *. eval env q }
304
variant { p }
305
= match p with
306
| Nil -> Nil
307
| Cons (m, c) r -> add (mul_term m c q) (mul r q)
308
end

The product of the polynomials f a for the atoms a of m

  Valid (58ms) (colibri2)
311
let rec
compose_mono
(f: Atom.t -> poly) (m:mono) : poly
312
requires { forall a. wf (f a) }
313
ensures { wf result }
314
ensures { forall env env'. (forall a. env' a = eval env (f a)) ->
315
eval env result = evalm env' m }
316
variant { m }
317
= match m with
318
| Nil -> cst (A.of_int 1)
319
| Cons a r -> mul (f a) (compose_mono f r)
320
end

Every atom a of p replaced by f a

  Valid (759ms) (colibri2)
323
let rec
compose
(f: Atom.t -> poly) (p:poly) : poly
324
requires { forall a. wf (f a) }
325
requires { wf p }
326
ensures { wf result }
327
ensures { forall env env'. (forall a. env' a = eval env (f a)) ->
328
eval env result = eval env' p }
329
variant { p }
330
= match p with
331
| Nil -> Nil
332
| Cons (m, c) r -> add (scale c (compose_mono f m)) (compose f r)
333
end

The number of monomials of p that contain a

335
function
occ
(a:Atom.t) (p:poly) : int =
336
match p with
337
| Nil -> 0
338
| Cons (m, _) r -> (if mem a m then 1 else 0) + occ a r
339
end

a is in a monomial of p

342
predicate
occurs
(a:Atom.t) (p:poly) =
343
match p with
344
| Nil -> false
345
| Cons (m, _) r -> mem a m \/ occurs a r
346
end
347
Valid (32ms) (colibri2)
348
let rec ghost
occ_nonneg
(a:Atom.t) (p:poly) : unit
349
ensures { 0 <= occ a p }
350
ensures { occurs a p <-> occ a p > 0 }
351
variant { p }
352
= match p with Nil -> () | Cons _ r -> occ_nonneg a r end
353
Valid (35ms) (colibri2)
354
let rec ghost
occurs_has
(a:Atom.t) (p:poly) : mono
355
requires { occurs a p }
356
ensures { has result p /\ mem a result }
357
variant { p }
358
= match p with
359
| Nil -> absurd
360
| Cons (m, _) r -> if pure { mem a m } then m else occurs_has a r
361
end
362
Valid (38ms) (colibri2)
363
let rec ghost
has_occurs
(a:Atom.t) (p:poly) (m:mono) : unit
364
requires { has m p /\ mem a m }
365
ensures { occurs a p }
366
variant { p }
367
= match p with
368
| Nil -> absurd
369
| Cons (m', _) r -> if pure { m <> m' } then has_occurs a r m
370
end

Where a occurs once, two monomials that contain a are the same

  Valid (38ms) (colibri2 11) (split_vc 3) (depth 3)
373
let rec ghost
occ_one
(a:Atom.t) (p:poly) (m1 m2:mono) : unit
374
requires { occ a p = 1 }
375
requires { has m1 p /\ mem a m1 }
376
requires { has m2 p /\ mem a m2 }
377
ensures { m1 = m2 }
378
variant { p }
379
= match p with
380
| Nil -> absurd
381
| Cons (m, _) r ->
382
occ_nonneg a r;
383
if pure { m1 <> m } then has_occurs a r m1;
384
if pure { m2 <> m } then has_occurs a r m2;
385
if pure { m1 <> m /\ m2 <> m } then begin
386
if pure { mem a m } then absurd else occ_one a r m1 m2
387
end
388
end
389
Valid (32ms) (colibri2)
390
let rec
mem_atom
(a:Atom.t) (m:mono) : bool
391
ensures { result <-> mem a m }
392
variant { m }
393
= match m with
394
| Nil -> false
395
| Cons b r -> Atom.equal a b || mem_atom a r
396
end
397
Valid (33ms) (colibri2)
398
let rec
occ_p
(a:Atom.t) (p:poly) : int
399
ensures { result = occ a p }
400
variant { p }
401
= match p with
402
| Nil -> 0
403
| Cons (m, _) r -> (if mem_atom a m then 1 else 0) + occ_p a r
404
end

The coefficient of m in p (zero if absent)

407
function
coef
(m:mono) (p:poly) : real =
408
match p with
409
| Nil -> 0.0
410
| Cons (m', c) r -> if m = m' then A.real c else coef m r
411
end

p without its term on m, and the coefficient of that term

  Valid (769ms) (colibri2)
414
let rec
remove
(m:mono) (p:poly) : (poly, A.t)
415
requires { wf p }
416
returns { (q, c) -> wf q
417
/\ (forall m'. has m' q <-> has m' p /\ m' <> m)
418
/\ (has m p -> A.real c <> 0.0)
419
/\ (forall env. eval env q = eval env p -. A.real c *. evalm env m) }
420
variant { p }
421
= match p with
422
| Nil -> Nil, A.of_int 0
423
| Cons (m', c') r ->
424
if Mono.compare m m' = 0 then begin
425
mlt_irrefl m;
426
r, c'
427
end else begin
428
let q, c = remove m r in
429
if pure { has m p } then assert { has m r };
430
Cons (m', c') q, c
431
end
432
end

Search in l an atom x that is a monomial and occurs once in p

  Valid (67ms) (colibri2)
435
let rec
find
(p l:poly) : option Atom.t
436
requires { wf p }
437
ensures { match result with
438
| Some x -> has (Cons x Nil) l /\ occ x p = 1
439
| None -> forall x. has (Cons x Nil) l -> occ x p <> 1
440
end }
441
variant { l }
442
= match l with
443
| Nil -> None
444
| Cons (Cons x Nil, _) r -> if occ_p x p = 1 then Some x else find p r
445
| Cons _ r -> find p r
446
end
447
448
type
solved
=
449
|
Zero
450
|
Contra
451
|
Solved
Atom.t poly
452
|
NotSolved

The non zero constants

455
predicate
is_cst
(p:poly) =
456
match p with
457
| Cons (Nil, _) Nil -> true
458
| _ -> false
459
end

Solve the equation p = 0. Solved x q: the equation is x = q, and x is not in q. NotSolved exactly when no atom x is a monomial of p and occurs once in p (and p is not a constant).

  Valid (1.1s) (colibri2 40) (cvc4 2) (cvc5) (split_vc 3) (depth 2)
464
let
solve
(p:poly) : solved
465
requires { wf p }
466
ensures { match result with
467
| Zero -> p = Nil
468
| Contra -> is_cst p /\ (forall env. eval env p <> 0.0)
469
| Solved x q ->
470
has (Cons x Nil) p /\ occ x p = 1 /\ wf q /\ not (occurs x q)
471
/\ (forall env. eval env p = 0.0 <-> env x = eval env q)
472
| NotSolved ->
473
p <> Nil /\ not (is_cst p) /\ (forall x. has (Cons x Nil) p -> occ x p <> 1)
474
end }
475
= match p with
476
| Nil -> Zero
477
| Cons (Nil, _) Nil -> Contra
478
| _ ->
479
match find p p with
480
| None -> NotSolved
481
| Some x ->
482
let mx = Cons x Nil in
483
let rest, c = remove mx p in
484
let k = A.div (A.of_int (-1)) c in
485
assert { A.real k *. A.real c = -1.0 };
486
let q = scale k rest in
487
let lemma no (m:mono) : unit
488
requires { has m q }
489
ensures { not (mem x m) }
490
= if pure { mem x m } then occ_one x p m mx in
491
if pure { occurs x q } then begin
492
let m = occurs_has x q in no m
493
end;
494
let lemma ev (env: Atom.t -> real) : unit
495
ensures { eval env p = 0.0 <-> env x = eval env q }
496
= let e = eval env p in
497
let r = eval env rest in
498
let vk = A.real k in
499
let vc = A.real c in
500
assert { evalm env mx = env x };
501
assert { r = e -. vc *. env x };
502
assert { eval env q = vk *. r };
503
assert { vk *. vc = -1.0 };
504
assert { vk *. (e -. vc *. env x) = vk *. e +. env x };
505
assert { vc <> 0.0 };
506
assert { e = 0.0 <-> vk *. e = 0.0 } in
507
Solved x q
508
end
509
end

p divided by the atom a, when a divides all the monomials

  Valid (63ms) (colibri2 11) (split_vc) (depth 1)
511
let rec
div_atom
(a:Atom.t) (p:poly) : option poly
512
requires { wf p }
513
ensures { match result with
514
| Some q -> wf q /\ (forall env. eval env p = env a *. eval env q)
515
| None -> exists m. has m p /\ not (mem a m)
516
end }
517
variant { p }
518
= match p with
519
| Nil -> Some Nil
520
| Cons (m, c) r ->
521
if mem_atom a m then
522
match div_atom a r with
523
| None -> None
524
| Some q ->
525
let m' = Mono.remove_one a m in
526
let t = Cons (m', c) Nil in
527
let res = add t q in
528
let lemma ev (env: Atom.t -> real) : unit
529
ensures { eval env p = env a *. eval env res }
530
= let x = A.real c in
531
assert { evalm env m = env a *. evalm env m' };
532
assert { eval env t = x *. evalm env m' };
533
assert { eval env r = env a *. eval env q };
534
assert { x *. (env a *. evalm env m') +. env a *. eval env q
535
= env a *. (x *. evalm env m' +. eval env q) } in
536
Some res
537
end
538
else None
539
end

Factor out of p the atoms of l that divide all its monomials: g * p = g' * q

  Valid (117ms) (colibri2 10) (split_vc) (depth 1)
543
let rec
factor_atoms
(l: list Atom.t) (g:mono) (p:poly) : (mono, poly)
544
requires { wf p /\ sorted g }
545
returns { (g', q) -> sorted g' /\ wf q
546
/\ (forall env. evalm env g *. eval env p = evalm env g' *. eval env q) }
547
variant { l }
548
= match l with
549
| Nil -> (g, p)
550
| Cons a l ->
551
match div_atom a p with
552
| None -> factor_atoms l g p
553
| Some q ->
554
let g1 = Mono.mul (Cons a Nil) g in
555
let lemma ev (env: Atom.t -> real) : unit
556
ensures { evalm env g *. eval env p = evalm env g1 *. eval env q }
557
= assert { evalm env g1 = env a *. evalm env g };
558
assert { eval env p = env a *. eval env q } in
559
factor_atoms l g1 q
560
end
561
end

The factorization p = k * g * q: g is the product of the common atoms of the monomials of p (with multiplicity), and q is divided by its first coefficient

  Valid (50ms) (colibri2 17) (split_vc 4) (depth 4)
566
let
factor
(p:poly) : (A.t, mono, poly)
567
requires { wf p }
568
returns { (k, g, q) -> A.real k <> 0.0 /\ sorted g /\ wf q
569
/\ (forall env. eval env p = A.real k *. evalm env g *. eval env q) }
570
= match p with
571
| Nil -> (A.of_int 1, Nil, Nil)
572
| Cons (m, _) _ ->
573
let g, q = factor_atoms m Nil p in
574
match q with
575
| Nil -> (A.of_int 1, g, Nil)
576
| Cons (_, c) _ ->
577
let k1 = A.div (A.of_int 1) c in
578
assert { A.real k1 *. A.real c = 1.0 };
579
let q1 = scale k1 q in
580
let lemma ev (env: Atom.t -> real) : unit
581
ensures { eval env p = A.real c *. evalm env g *. eval env q1 }
582
= let vk = A.real k1 in
583
let vc = A.real c in
584
assert { evalm env Nil = 1.0 };
585
assert { eval env p = evalm env g *. eval env q };
586
assert { eval env q1 = vk *. eval env q };
587
assert { vc *. vk = 1.0 };
588
assert { vc *. evalm env g *. (vk *. eval env q)
589
= (vc *. vk) *. (evalm env g *. eval env q) } in
590
(c, g, q1)
591
end
592
end
593
end