1 (* rationals, i.e. fractions of multivariate polynomials over the real field
4 Use is subject to license terms.
5 1234567890123456789012345678901234567890123456789012345678901234567890123456789012345678901234567890
6 10 20 30 40 50 60 70 80 90 100
9 theory GCD_Poly imports Complex_Main begin
13 F. Winkler, Polynomial algorithyms in computer algebra. Springer 1996.
14 by page 93 and 95. This is the final version of the Isabelle theory,
15 which conforms with Isabelle's coding standards and with requirements
16 in terms of logics appropriate for a theorem prover.
19 section {* Predicates for the specifications *}
21 This thesis provides program code to be integrated into the Isabelle
22 distribution. Thus the code will be verified against specifications, and
23 consequently the code, as \emph{explicit} specification of how to calculate
24 results, is accompanied by \emph{implicit} specifications describing the
25 properties of the program code.
27 For describing the properties of code the format of Haskell will be used.
28 Haskell \cite{TODO} is front-of-the-wave in research on functional
29 programming and as such advances beyond SML. The advancement relevant for
30 this thesis is the concise combination of explicit and implicit specification
31 of a function. The final result of the code developed within this thesis is
32 described as follows in Haskell format:
34 \begin{verbatim} % TODO: find respective Isabelle/LaTeX features
35 gcd_poly :: int poly \<Rightarrow> int poly \<Rightarrow> int poly
37 assumes and p1 \<noteq> [:0:] and p2 \<noteq> [:0:]
38 yields d dvd p1 \<and> d dvd p2 \<and> \<forall>d'. (d' dvd p1 \<and> d' dvd p2) \<longrightarrow> d' \<le> d
41 The above specification combines Haskell format with the term language of
42 Isabelle\HOL. The latter provides a large and ever growing library of
43 mechanised mathematics knowledge, which this thesis re-uses in order to
44 prepare for integration of the code.
46 In the sequel there is a brief account of the notions required for the
47 specification of the functions implemented within this thesis. *}
49 subsection {* The Isabelle types required *}
51 bool, nat, int, option, THE, list, 'a poly
54 subsection {* The connectives required *}
56 logic ~~/doc/tutorial.pdf p.203
57 arithmetic < \<le> + - * ^ div \<bar>_\<bar>
60 subsection {* The Isabelle functions required *}
65 Primes.next_prime_bound
69 List.length, List.member
71 List.nth, List.take, List.drop
78 section {* gcd for univariate polynomials *}
80 type unipoly = int list;
81 val a = [~18, ~15, ~20, 12, 20, ~13, 2];
82 val b = [8, 28, 22, ~11, ~14, 1, 2];
85 subsection {* auxiliary functions *}
88 5 div 2 = 2; ~5 div 2 = ~3; BUT WEE NEED ~5 div2 2 = ~2; *)
91 if a div b < 0 then (abs a) div (abs b) * ~1 else a div b
93 (* why has this been removed since 2002 ? *)
94 fun last_elem ls = (hd o rev) ls
96 (* drop tail elements equal 0 *)
97 fun drop_hd_zeros (0 :: ps) = drop_hd_zeros ps
99 fun drop_tl_zeros p = (rev o drop_hd_zeros o rev) p;
102 subsection {* modulo calculations for integers *}
104 (* mod_inv :: int \<Rightarrow> nat
107 yields r * s mod m = 1 *)
110 fun modi (r, rold, m, rinv) =
111 if m <= rinv then 0 else
114 else modi (rold * (rinv + 1), rold, m, rinv + 1)
115 in modi (r, r, m, 1) end
117 (* mod_div :: int \<Rightarrow> int \<Rightarrow> nat \<Rightarrow> nat
120 yields a * b ^(-1) mod m = c <\<Longrightarrow> a mod m = *)
121 fun mod_div a b m = a * (mod_inv b m) mod m
123 (* required just for one approximation:
124 approx_root :: nat \<Rightarrow> nat
127 yields r * r \<ge> a *)
130 fun root1 a n = if n * n < a then root1 a (n + 1) else n
133 (* chinese_remainder :: int * nat \<Rightarrow> int * nat \<Rightarrow> nat
134 chinese_remainder (r1, m1) (r2, m2) = r
136 yields r = r1 mod m1 \<and> r = r2 mod m2 *)
137 fun chinese_remainder (r1, m1) (r2, m2) =
139 (((r2 - (r1 mod m1)) * (mod_inv m1 m2)) mod m2) * m1;
142 subsection {* creation of lists of primes for efficiency *}
144 (* is_prime :: int list \<Rightarrow> int \<Rightarrow> bool
146 assumes max ps < n \<and> n \<le> (max ps)^2 \<and>
147 (* FIXME: really ^^^^^^^^^^^^^^^? *)
148 (\<forall>p. List.member ps p \<longrightarrow> Primes.prime p) \<and> (\<forall>p. p < n \<and> Primes.prime p \<longrightarrow> List.member ps p)
149 yields Primes.prime n *)
150 fun is_prime [] _ = true
152 if n mod (List.hd prs) <> 0 then is_prime (List.tl prs) n else false
154 (* make_primes is just local to primes_upto only:
155 make_primes :: int list \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int list
156 make_primes ps last_p n = pps
157 assumes last_p = maxs ps \<and> (\<forall>p. List.member ps p \<longrightarrow> Primes.prime p) \<and>
158 (\<forall>p. p < last_p \<and> Primes.prime p \<longrightarrow> List.member ps p)
159 yields n \<le> maxs pps \<and> (\<forall>p. List.member pps p \<longrightarrow> Primes.prime p) \<and>
160 (\<forall>p. (p < maxs pps \<and> Primes.prime p) \<longrightarrow> List.member pps p)*)
161 fun make_primes ps last_p n =
162 if n <= last_elem ps then ps else
163 if is_prime ps (last_p + 2)
164 then make_primes (ps @ [(last_p + 2)]) (last_p + 2) n
165 else make_primes ps (last_p + 2) n
167 (* primes_upto :: nat \<Rightarrow> nat list
170 yields (\<forall>p. List.member ps p \<longrightarrow> Primes.prime p) \<and>
171 n \<le> maxs ps \<and> maxs ps \<le> Fact.fact n + 1 \<and>
172 (\<forall>p. p \<le> maxs ps \<and> Primes.prime p \<longrightarrow> List.member ps p) *)
173 fun primes_upto n = if n < 3 then [2] else make_primes [2, 3] 3 n
175 (* find the next prime greater p not dividing the number n:
176 next_prime_not_dvd :: int \<Rightarrow> int \<Rightarrow> int (infix)
177 n1 next_prime_not_dvd n2 = p
179 yields p is_prime \<and> n1 < p \<and> \<not> p dvd n2 \<and> (* smallest with these properties... *)
180 (\<forall> p'. (p' is_prime \<and> n1 < p' \<and> \<not> p' dvd n2) \<longrightarrow> p \<le> p') *)
181 infix next_prime_not_dvd;
182 fun n1 next_prime_not_dvd n2 =
184 val ps = primes_upto (n1 + 1)
185 val nxt = nth ps (List.length ps - 1);
187 if n2 mod nxt <> 0 then nxt else nxt next_prime_not_dvd n2
191 subsection {* basic notions for univariate polynomials *}
193 (* leading coefficient, includes drop_lc0_up ?FIXME130507 *)
194 fun lcoeff_up (p: unipoly) = (last_elem o drop_tl_zeros) p
196 (* drop leading coefficients equal 0 *)
197 fun drop_lc0_up (p: unipoly) = drop_tl_zeros p : unipoly;
199 (* degree, includes drop_lc0_up ?FIXME130507 *)
200 fun deg_up (p: unipoly) = ((Integer.add ~1) o length o drop_lc0_up) p;
202 (* normalise a unipoly such that lcoeff_up mod m = 1.
203 normalise :: unipoly \<Rightarrow> nat \<Rightarrow> unipoly
204 normalise [p_0, .., p_k] m = [q_0, .., q_k]
206 yields \<exists> t. 0 \<le> i \<le> k \<Rightarrow> (p_i * t) mod m = q_i \<and> (p_k * t) mod m = 1 *)
207 fun normalise (p: unipoly) (m: int) =
209 val p = drop_lc0_up p
210 val lcp = lcoeff_up p;
213 then [mod_div (nth p i) lcp m] @ nrm
214 else norm ([mod_div (nth p i) lcp m] @ nrm) (i - 1) ;
216 if List.length p = 0 then p else norm [] (List.length p - 1)
220 subsection {* addition, multiplication, division *}
222 (* scalar multiplication *)
224 fun (p: unipoly) %* n = map (Integer.mult n) p : unipoly
228 fun (p: unipoly) %/ n =
229 let fun swapf f a b = f b a (* swaps the arguments of a function *)
230 in map (swapf (curry op div2) n) p : unipoly end;
234 fun (p1: unipoly) %-% (p2: unipoly) =
235 map2 (curry op -) p1 (p2 @ replicate (List.length p1 - List.length p2) 0) : unipoly
237 (* dvd for univariate polynomials *)
240 fun [d] %|% [p] = (p mod d = 0)
241 | (ds: unipoly) %|% (ps: unipoly) =
243 val ds = drop_lc0_up ds;
244 val ps = drop_lc0_up ps;
245 val d000 = (replicate (List.length ps - List.length ds) 0) @ ds ;
246 val quot = (lcoeff_up ps) div2 (lcoeff_up d000);
247 val rest = drop_lc0_up (ps %-% (d000 %* quot));
249 if rest = [] then true else
250 if rest <> [] andalso quot <> 0 andalso List.length ds <= List.length rest
256 subsection {* normalisation and Landau-Mignotte bound *}
258 (* normalise :: centr_up \<Rightarrow> unipoly => int \<Rightarrow> unipoly
259 normalise [p_0, .., p_k] m = [q_0, .., q_k]
261 yields 0 \<le> i \<le> k \<Rightarrow> |^ ~m/2 ^| <= q_i <=|^ m/2 ^|
262 (where |^ x ^| means round x up to the next greater integer) *)
263 fun centr_up (p: unipoly) (m: int) =
266 val mid = if m mod mi = 0 then mi else mi + 1;
267 fun centr m mid p_i = if mid < p_i then p_i - m else p_i;
268 in map (centr m mid) p : unipoly end;
270 (*** landau mignotte bound (Winkler p91)
271 every coefficient of the gcd of a and b in Z[x] is bounded in absolute value by
272 2^{min(m,n)} * gcd(a_m,b_n) * min(1/|a_m|
273 * root(sum_{i=0}^{m}a_i^2) ,1/|b_n| * root( sum_{i=0}^{n}b_i^2 ) ***)
275 (* sum_lmb :: centr_up \<Rightarrow> unipoly \<Rightarrow> int \<Rightarrow> int
276 sum_lmb [p_0, .., p_k] e = s
278 yields. p_0^e + p_1^e + ... + p_k^e *)
279 fun sum_lmb (p: unipoly) exp = fold ((curry op +) o (Integer.pow exp)) p 0;
281 (* LANDAU_MIGNOTTE_bound :: centr_up \<Rightarrow> unipoly \<Rightarrow> unipoly \<Rightarrow> int
282 LANDAU_MIGNOTTE_bound [a_0, ..., a_m] [b_0, .., b_n] = lmb
284 yields lmb = 2^min(m,n) * gcd(a_m,b_n) *
285 min( 1/|a_m| * root(sum_lmb [a_0,...a_m] 2 , 1/|b_n| * root(sum_lmb [b_0,...b_n] 2)*)
286 fun LANDAU_MIGNOTTE_bound (p1: unipoly) (p2: unipoly) =
287 (Integer.pow (Integer.min (deg_up p1) (deg_up p2)) 2) * (abs (Integer.gcd (lcoeff_up p1) (lcoeff_up p2))) *
288 (Int.min (abs((approx_root (sum_lmb p1 2)) div2 ~(lcoeff_up p1)),
289 abs((approx_root (sum_lmb p2 2)) div2 ~(lcoeff_up p2))));
292 subsection {* modulo calculations on polynomials *}
294 (* chinese_remainder_up :: int * int \<Rightarrow> unipoly * unipoly \<Rightarrow> unipoly
295 chinese_remainder_up (m1, m2) (p1, p2) = p
296 assume m1, m2 relatively prime
297 yields p1 = p mod m1 \<and> p2 = p mod m2 *)
298 fun chinese_remainder_up (m1, m2) (p1: unipoly, p2: unipoly) =
300 fun chinese_rem (m1, m2) (p_1i, p_2i) = chinese_remainder (p_1i, m1) (p_2i, m2)
301 in map (chinese_rem (m1, m2)) (p1 ~~ p2): unipoly end
303 (* mod_up :: unipoly \<Rightarrow> int \<Rightarrow> unipoly
304 mod_up [p1, p2, ..., pk] m = up
306 yields up = [p1 mod m, p2 mod m, ..., pk mod m]*)
308 fun (p : unipoly) mod_up m =
310 fun mod' m p = (curry op mod) p m
311 in map (mod' m) p : unipoly end
313 (* euclidean algoritm in Z_p[x].
314 mod_up_gcd :: unipoly \<Rightarrow> unipoly \<Rightarrow> int \<Rightarrow> unipoly
315 mod_up_gcd p1 p2 m = g
317 yields gcd ((p1 mod m), (p2 mod m)) = g *)
318 fun mod_up_gcd (p1: unipoly) (p2: unipoly) (m: int) =
320 val p1m = p1 mod_up m;
321 val p2m = drop_lc0_up (p2 mod_up m);
322 val p2n = (replicate (List.length p1 - List.length p2m) 0) @ p2m;
323 val quot = mod_div (lcoeff_up p1m) (lcoeff_up p2n) m;
324 val rest = drop_lc0_up ((p1m %-% (p2n %* quot)) mod_up m)
326 if rest = [] then p2 else
327 if length rest < List.length p2
328 then mod_up_gcd p2 rest m
329 else mod_up_gcd rest p2 m
332 (* primitive_up :: unipoly \<Rightarrow> unipoly
335 yields \<forall>p1, p2. (List.member pp p1 \<and> List.member pp p2 \<and> p1 \<noteq> p2) \<longrightarrow> gcd p1 p2 = 1 *)
336 fun primitive_up ([c] : unipoly) =
337 if c = 0 then ([0] : unipoly) else ([1] : unipoly)
340 val d = abs (Integer.gcds p)
342 if d = 1 then p else p %/ d
346 subsection {* gcd_up, code from [1] p.93 *}
348 (* try_new_prime_up :: unipoly \<Rightarrow> unipoly \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> unipoly \<Rightarrow> int \<Rightarrow> unipoly
349 try_new_prime_up p1 p2 d M P g p = new_g
350 assumes d = gcd (lcoeff_up p1, lcoeff_up p2) \<and>
351 M = LANDAU_MIGNOTTE_bound \<and> p = prime \<and> p ~| d \<and> P \<ge> p \<and>
352 p1 is primitive \<and> p2 is primitive
353 yields new_g = [1] \<or> (new_g \<ge> g \<and> P > M)
355 argumentns "a b d M P g p" named according to [1] p.93 *)
356 fun try_new_prime_up a b d M P g p =
359 val p' = p next_prime_not_dvd d
360 val g_p = centr_up (( (normalise (mod_up_gcd a b p') p')
365 if deg_up g_p < deg_up g
367 if (deg_up g_p) = 0 then [1]: unipoly else try_new_prime_up a b d M p g_p p'
369 if deg_up g_p <> deg_up g then try_new_prime_up a b d M P g p' else
372 val g = centr_up ((chinese_remainder_up (P, p') (g, g_p)) mod_up P) P
373 in try_new_prime_up a b d M P g p' end
376 (* HENSEL_lifting_up :: unipoly \<Rightarrow> unipoly \<Rightarrow> int \<Rightarrow> int \<Rightarrow> int \<Rightarrow> unipoly
377 HENSEL_lifting_up p1 p2 d M p = gcd
378 assumes d = gcd (lcoeff_up p1, lcoeff_up p2) \<and>
379 M = LANDAU_MIGNOTTE_bound \<and> p = prime \<and> p ~| d \<and>
380 p1 is primitive \<and> p2 is primitive
381 yields gcd | p1 \<and> gcd | p2 \<and> gcd is primitive
383 argumentns "a b d M p" named according to [1] p.93 *)
384 fun HENSEL_lifting_up a b d M p =
386 val p = p next_prime_not_dvd d
387 val g_p = centr_up (((normalise (mod_up_gcd a b p) p) %* (d mod p)) mod_up p) p
389 if deg_up g_p = 0 then [1] else
391 val g = primitive_up (try_new_prime_up a b d M p g_p p)
393 if (g %|% a) andalso (g %|% b) then g:unipoly else HENSEL_lifting_up a b d M p
397 (* gcd_up :: unipoly \<Rightarrow> unipoly \<Rightarrow> unipoly
399 assumes not (a = [] \<or> a = [0]) \<and> not (b = []\<or> b = [0]) \<and>
400 a is primitive \<and> b is primitive
401 yields c dvd a \<and> c dvd b \<and> (\<forall>c'. (c' dvd a \<and> c' dvd b) \<longrightarrow> c' \<le> c) *)
403 let val d = abs (Integer.gcd (lcoeff_up a) (lcoeff_up b))
406 HENSEL_lifting_up a b d (2 * d * LANDAU_MIGNOTTE_bound a b) 1
410 section {* gcd for multivariate polynomials *}
412 type monom = (int * int list);
413 type poly = monom list;
416 subsection {* auxiliary functions *}
418 fun land a b = a andalso b
419 fun all_geq a b = fold land (map2 (curry op >=) a b) true
420 fun all_geq' i es = fold land (map ((curry op <=) i) es) true
421 fun maxs is = fold Integer.max is (hd is);
422 fun div2_swapped d i = i div2 d
423 fun nth_swapped i ls = nth ls i;
424 fun drop_last ls = (rev o tl o rev) ls
425 fun nth_ins n i xs = (*analogous to nth_drop: why not in library.ML?*)
426 List.take (xs, n) @ [i] @ List.drop (xs, n);
429 subsection {* basic notions for multivariate polynomials *}
431 fun lcoeff (p: poly) = (fst o hd o rev) p
432 fun lexp (p: poly) = (snd o hd o rev) p
433 fun lmonom (p: poly) = (hd o rev) p
435 fun cero_poly (nro_vars: int) = [(0, replicate nro_vars 0)] : poly;
437 (* drop leading coefficients equal 0 TODO: signature?*)
438 fun drop_lc0 (p: poly as [(c, es)]) = if c = 0 then cero_poly (length es) else p
439 | drop_lc0 p = if lcoeff p = 0 then drop_lc0 (drop_last p) else p
441 (* gcd of coefficients WN find right location in file *)
442 fun gcd_coeff (up: unipoly) = abs (Integer.gcds up)
444 (* given p = 3x+4z = [(3,[1,0]),(4,[0,1])] with x<z
445 add_variable p 2 => [(3,[1,0,0]),(4,[0,0,1])] with x<y<z *)
446 fun add_variable (p: poly) var = map (apsnd (nth_ins var 0)) p : poly
449 subsection {* ordering and other auxiliary funcions *}
451 (* monomial order: lexicographic order on exponents *)
452 fun lex_ord ((_, a): monom) ((_, b): monom) =
453 let val d = drop_tl_zeros (a %-% b)
455 if d = [] then false else last_elem d > 0
457 fun lex_ord' ((_, a): monom, (_, b): monom) =
458 let val d = drop_tl_zeros (a %-% b)
461 else if last_elem d > 0 then GREATER else LESS
464 (* add monomials in ordered polynomal *)
465 fun add_monoms (p: poly) =
467 fun add [(0, es)] [] = cero_poly (length es)
468 | add [(0, _)] (new: poly) = new
469 | add [m] (new: poly) = new @ [m]
470 | add ((c1, es1) :: (c2, es2) :: ms) (new: poly) =
472 then add ([(c1 + c2, es1)] @ ms) new
475 then add ((c2, es2) :: ms) new
476 else add ((c2, es2) :: ms) (new @ [(c1, es1)])
477 in add p [] : poly end
479 (* brings the polynom in correct order and adds monomials *)
480 fun order (p: poly) = (add_monoms o (sort lex_ord')) p;
482 (* largest exponent of variable at location var *)
483 fun max_deg_var (p: poly) var = (maxs o (map ((nth_swapped var) o snd))) p;
486 subsection {* evaluation, translation uni--multivariate, etc *}
488 (* evaluate a polynomial in a certain variable and remove this from the exp-list *)
489 fun eval (p: poly) var value =
491 fun eval [] _ _ new = order new
492 | eval ((c, es)::ps) var value new =
493 eval ps var value (new @ [((Integer.pow (nth es var) value) * c, nth_drop var es)]);
494 in eval p var value [] end
496 (* transform a multivariate to a univariate polynomial *)
497 fun multi_to_uni (p as (_, es)::_ : poly) =
500 let fun transfer ([]: poly) (up: unipoly) = up
501 | transfer (mp as (c, es)::ps) up =
503 then transfer ps (up @ [c])
504 else transfer mp (up @ [0])
505 in transfer (order p) [] end
506 else error "Polynom has more than one variable!";
508 (* transform a univariate to a multivariate polynomial *)
509 fun uni_to_multi (up: unipoly) =
510 let fun transfer ([]: unipoly) (mp: poly) (_: int) = add_monoms mp
511 | transfer up mp var =
512 transfer (tl up) (mp @ [(hd up, [var])]) (var + 1)
513 in transfer up [] 0 end
515 (* multiply a poly with a variable represented by a unipoly (at position var)
516 e.g new z: (3x + 2y)*(z - 4) TODO fold / map ? *)
517 fun mult_with_new_var ([]: poly) (_: unipoly) (_: int) = []
518 | mult_with_new_var mp up var =
520 fun mult ([]: poly) (_: unipoly) (_: int) (new: poly) (_: int) = add_monoms new
521 | mult mp up var new _ =
524 fun mult' (_: poly) ([]: unipoly) (_) (new': poly) (_: int) = order new'
525 | mult' (mp' as (c, es)::ps) up' var new' c2' =
526 let val (first, last) = chop var es
527 in mult' mp' (tl up') var
528 (new' @ [(c * hd up', first @ [c2'] @ last)]) (c2' + 1)
530 in mult (tl mp) up var (new @ (mult' mp up var [] 0)) (0) end
531 in mult mp up var [] 0 : poly end
533 fun greater_deg (es1: int list) (es2: int list) =
534 if es1 = [] andalso es2 =[] then 0
535 else if (nth es1 (length es1 -1)) = (nth es2 (length es1 -1) )
536 then greater_deg (nth_drop (length es1 -1) es1) (nth_drop (length es1 -1) es2)
537 else if (nth es1 (length es1 -1)) > (nth es2 (length es1 -1))
541 fun find_new_r (p1 as (_, es1)::_ : poly) (p2 as (_, es2)::_ : poly) old =
542 let val p1' as (_, es1')::_ = eval p1 (length es1 - 2) (old + 1)
543 val p2' as (_, es2')::_ = eval p2 (length es2 - 2) (old + 1);
545 if max_deg_var p1' (length es1' - 1) = max_deg_var p1 (length es1 - 1) orelse
546 max_deg_var p2' (length es2' - 1) = max_deg_var p2 (length es1 - 1)
548 else find_new_r p1 p2 (old + 1)
552 subsection {* addition, multiplication, division *}
554 (* resulting 0 coefficients are removed by add_monoms *)
556 fun (p: poly) %%/ d = (add_monoms o (map (apfst (div2_swapped d)))) p;
559 fun (p: poly) %%* i = (add_monoms o (map (apfst (Integer.mult i)))) p;
562 (* the same algorithms as done by hand
563 fun ([]: poly) %%+%% (mvp2: poly) = mvp2
567 fun plus [] p2 new = order (new @ p2)
568 | plus p1 [] new = order (new @ p1)
569 | plus (p1 as (c1, es1)::ps1) (p2 as (c2, es2)::ps2) new =
570 if greater_deg es1 es2 = 0
571 then plus ps1 ps2 (new @ [((c1 + c2), es1)])
573 if greater_deg es1 es2 = 1
574 then plus p1 ps2 (new @ [(c2, es2)])
575 else plus ps1 p2 (new @ [(c1, es1)])
578 fun (p1 : poly) %%+%% (p2 : poly) = order (p1 @ p2)
581 fun p1 %%-%% (p2: poly) = p1 %%+%% (map (apfst (Integer.mult ~1)) p2)
584 (* the same algorithms as done by hand
585 fun (p1: poly) %%*%% (p2: poly) =
587 fun mult ([]: poly) (_: poly) (_: poly) (new: poly) = order new
588 | mult p1 [] regular_p2 new = mult (tl p1) regular_p2 regular_p2 new
589 | mult (p1 as (c1, es1)::_) ((c2, es2)::ps2) regular_p2 (new: poly) =
590 mult p1 ps2 regular_p2 (new @ [(c1 * c2, map2 Integer.add es1 es2)])
592 if length p1 > length p2
593 then mult p1 p2 p2 []
594 else mult p2 p1 p1 []
597 fun mult_monom ((c1, es1): monom) ((c2, es2): monom) =
598 (c1 * c2, map2 Integer.add es1 es2): monom;
599 fun mult_monoms (ms: poly) m = map (mult_monom m) ms : poly
600 fun p1 %%*%% (p2 : poly) = order (fold (curry op @) (map (mult_monoms p1) p2) [])
603 (* the same algorithms as done by hand; TODO fold / map ? *)
604 fun ([(c1, es1)]: poly) %%|%% ([(c2, es2)]: poly) = all_geq es2 es1 andalso c2 mod c1 = 0
605 | _ %%|%% [(0,_)] = true
607 if [lmonom p1] %%|%% [lmonom p2]
611 ([((lcoeff p2) div2 (lcoeff p1), (lexp p2) %-% (lexp p1))]
615 (* %%/%% :: poly \<Rightarrow> poly \<Rightarrow> (poly \<times> poly)
617 assumes b \<noteq> [] \<and>
618 yields THE c r. c *\<^isub>p b +\<^isub>p r = a *)
620 fun (p1: poly) %%/%% (p2: poly) =
622 fun div_up p1 p2 quot_old =
624 val p1 as (c, es)::_ = drop_lc0 (order p1);
625 val p2 = drop_lc0 (order p2);
626 val [c] = cero_poly (length es);
627 val d = (replicate (List.length p1 - List.length p2) c) @ p2 ;
628 val quot = [(lcoeff p1 div2 lcoeff d, lexp p1 %-% lexp p2)];
629 val rest = drop_lc0 (p1 %%-%% (d %%*%% quot));
631 if rest <> [c] andalso all_geq' 0 (lexp rest %-% lexp p2)
632 then div_up rest p2 (quot @ quot_old)
633 else (quot @ quot_old : poly, rest)
635 in div_up p1 p2 [] end
638 subsection {* Newton interpolation *}
639 ML{* (* first step *)
640 fun newton_first (x: int list) (f: poly list) (ord: int) =
642 val new_vals = [(hd x) * ~1, 1];
643 val p = (add_variable (hd f) ord) %%+%%
645 (((nth f 1) %%-%% (hd f)) %%/ (nth x 1) - (hd x))) new_vals ord);
646 val steps = [((nth f 1) %%-%% (hd f)) %%/ ((nth x 1) - (hd x))]
647 in (p, new_vals, steps) end
649 fun next_step ([]: poly list) (new_steps: poly list) (_: int list) = new_steps
650 | next_step steps new_steps x =
653 [((last_elem new_steps) %%-%% (hd steps)) %%/ ((last_elem x) - (nth x (length x - 3)))])
654 (nth_drop (length x -2) x)
656 fun NEWTON x f (steps: poly list) (up: unipoly) (p: poly) ord =
659 let val (p', new_vals, steps) = newton_first x [(hd f), (nth f 1)] ord
660 in (p', new_vals, steps) end
664 multi_to_uni ((uni_to_multi up) %%*%% (uni_to_multi [(nth x (length x -2) ) * ~1, 1]));
665 val new_steps = [((nth f (length f - 1)) %%-%% (nth f (length f - 2))) %%/
666 ((last_elem x) - (nth x (length x - 2)))];
667 val steps = next_step steps new_steps x;
668 val p' = p %%+%% (mult_with_new_var (last_elem steps) new_vals ord);
669 in (order p', new_vals, steps) end
672 subsection {* gcd_poly algorithm, code for [1] p.95 *}
674 (* naming of n, M, m, r, ... follows Winkler p. 95 *)
675 fun gcd_poly' (a as (c1, es1)::ps1 : poly) (b as (c2, es2)::ps2 : poly) n r =
676 if lex_ord (lmonom b) (lmonom a) then gcd_poly' b a n r else
679 let val (a', b') = (multi_to_uni a, multi_to_uni b)
681 (* a b are made primitive and this is compensated by multiplying with gcd of divisors *)
682 uni_to_multi ((gcd_up (primitive_up a') (primitive_up b')) %*
683 (abs (Integer.gcd (gcd_coeff a') (gcd_coeff b'))))
686 let val M = 1 + Int.min (max_deg_var a (length es1 - 2), max_deg_var b (length es2 - 2));
687 in try_new_r a b n M r [] [] end
689 and try_new_r a b n M r r_list steps =
691 val r = find_new_r a b r;
692 val r_list = r_list @ [r];
693 val g_r = gcd_poly' (order (eval a (n - 2) r))
694 (order (eval b (n - 2) r)) (n - 1) 0
695 val steps = steps @ [g_r];
696 in HENSEL_lifting a b n M 1 r r_list steps g_r ( cero_poly n ) [1] end
698 and HENSEL_lifting a b n M m r r_list steps g g_n mult =
699 if m > M then if g_n %%|%% a andalso g_n %%|%% b then g_n else
700 try_new_r a b n M r r_list steps
703 val r = find_new_r a b r;
704 val r_list = r_list @ [r];
705 val g_r = gcd_poly' (order (eval a (n - 2) r))
706 (order (eval b (n - 2) r)) (n - 1) 0
708 if lex_ord (lmonom g) (lmonom g_r)
709 then HENSEL_lifting a b n M 1 r r_list steps g g_n mult
710 else if (lexp g) = (lexp g_r)
712 val (g_n, new, steps) = NEWTON r_list [g, g_r] steps mult g_n (n - 2)
714 if (nth steps (length steps - 1)) = (cero_poly (n - 1))
715 then HENSEL_lifting a b n M (M + 1) r r_list steps g_r g_n new
716 else HENSEL_lifting a b n M (m + 1) r r_list steps g_r g_n new
718 else HENSEL_lifting a b n M (m + 1) r r_list steps g g_n mult
721 (* gcd_poly :: poly \<Rightarrow> poly \<Rightarrow> poly
722 gcd_poly a b = ((a', b'), c)
723 assumes a \<noteq> [] \<and> b \<noteq> [] \<and>
724 yields a = a' *\<^isub>p c \<and> b = b' *\<^isub>p c \<and>
725 (\<forall>c'. (c' dvd\<^isub>p a \<and> c' dvd\<^isub>p b) \<longrightarrow> c' \<le>\<^isub>p c) *)
726 fun gcd_poly (a as (_, es)::_ : poly) b =
727 let val c = gcd_poly' a b (length es) 0
728 val (a': poly, _) = a %%/%% c
729 val (b': poly, _) = b %%/%% c
733 section {* example from the last mail *}
734 ML {* (* test, see text below *)
735 val a = [(1,[2, 0]), (~1,[0, 2])];
736 val b = [(1,[2, 0]), (~1,[1, 1])] ;
737 val ((a', b'), c) = gcd_poly a b;
739 a = (a' %%*%% c) andalso b = (b' %%*%% c); (* where "%%*%%" is "*\<^isub>p" *)
740 c = [(~1, [1, 0]), (1, [0, 1])];
741 a' = [(~1, [1, 0]), (~1, [0, 1])];
745 text {* last mail to Tobias Nipkow:
746 Eine erste Idee, wie die Integration der Diplomarbeit für einen Benutzer
747 von Isabelle aussehen könnte, wäre zum Beispiel im
750 assumes asm3: "x^2 - x*y \<noteq> 0" and asm4: "x \<noteq> 0"
751 shows "(x^2 - y^2) / (x^2 - x*y) = (x + y) / (x::real)"
752 apply (insert asm3 asm4)
758 asm1: "(x^2 - y^2) = (x + y) * (x - y)" and asm2: "x^2 - x*y = x * (x - y)"
760 im Hintergrund automatisch zu erzeugen (mit der Garantie, dass "(x - y)" der GCD ist)
761 und sie dem Simplifier (für die Rule nonzero_mult_divide_mult_cancel_right) zur
762 Verfügung zu stellen, sodass anstelle von "sorry" einfach "done" stehen kann.
763 Und weiters wäre eventuell asm3 zu "x - y \<noteq> 0" zu vereinfachen, eine
764 Rewriteorder zum Herstellen einer Normalform festzulegen, etc.