multiplication de deux polynômes

[n0-sheep]

Bonjour à tous,
Aujourd'hui je me suis attelé à un exercice en caml et impossible d'en trouver une correction sur internet. Je fais appel à vous pour savoir ce que vous pensez de cette fonction, ou pour m'indiquer où je pourrai trouver une réponse toute faite, car google ne me fut pas très utile.
Je sais que ça doit être un exercice très classique pour des prépa maths sup/spe, mais je ne suis pas en prépa

Je voudrais avant tout des conseils sur les cas de bases, je pense qu'il y en a trop mais je n'arrive pas à en supprimer sans que le programme ne boucle à l'infini.
J'ai déclaré une fonction utilitaire mul' qui est appelée par mul, peut-être y-a-t-il plus propre de procéder ?
Merce d'avance pour tous vos précieux conseils

Voici l'énoncé :
- On représente un polynôme par une liste de ses coefficients [a0; a1 ...]
- Ecrire une fonction (récursive) qui effectue la multiplication de deux polynômes.

Voici le principe que j'ai utilisé :

Code :

1
2
3
4
5
6
7
8
Algorithme de Karatsuba [1]
Si P et Q deux polynomes de degré inférieur à 2n
alors soient P1, p2, Q1, Q2 polynomes de degré inférieurs à n dans :
P=P1 +P2 ·Xn
Q=Q1 +Q2 ·Xn
donc : PQ = p1.q1 + (p1.q2 + p2.q1)X^n + p2.q2 x^(2n)
Et on écrit : P1 ·Q2 +P2 ·Q1 =(P1 +P2)·(Q1 +Q2)−P1Q1 −P2Q2

voici mon programme :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
(* mul multiplie deux polynomes en partant du constat suivant : *)
(* si deg(P) et deg(Q) < 2n alors il existe p1, p2, q1, q2 de deg < n tq *)
(* P*Q = (p1+p2*X^n) * (q1+q2*X^n) *)
(* Avec de plus : P1*Q2 +P2*Q1 =(P1 +P2)*(Q1 +Q2)−P1Q1 −P2Q2 *)
        let rec mul' p q n = match p,q with
                [],_  -> []
                |_,[] -> []
                |[a],(b::q') ->(a*.b)::mul' [a] q' n
                |p,[a] -> mul' [a] p n
                |[a;b],q' -> ((mul' [a] q' n) ap (0.::(mul' [b] q' n)))
                |p,[a;b] -> mul' [a;b] p n
                |p,q -> let n' = 1 + n/2 in (*n' sera pour appeler mul'*)
                        let p1,p2 = split p n in
                        let q1,q2 = split q n in
                        let p1q1 = mul' p1 q1 n' in
                        let p2q2 = mul' p2 q2 n' in
                        let ppqq = mul' (p1 ap p2) (q1 ap q2) n' in
                        let pqpq = (ppqq sp (p1q1 ap p2q2)) in
                        ( p1q1 sp ((mmul 1. n pqpq) sp (mmul 1. (2*n) p2q2)));;
let mul p q =
        let deg = (1 + (max (deg_p p) (deg_p q))/2) in
        mul' p q deg
;;

____
ref :
[1] http://perso.ens-lyon.fr/lionel.rieg...sujet-tp06.pdf)

[SpiceGuid]

Application aux grands nombres (c'est la même chose pour les polynômes)

La même problématique (Knuth-Karatsuba pour les polynômes) est également traitée page 18 de Algorithmique de Michel Quercia

[n0-sheep]

Bonjour,
merci beaucoup pour ces pistes de documentation !

[prgasp77]

Envoyé par SpiceGuid

Application aux grands nombres

Salut, j'en ai profité pour lire ton article ; il est fort intéressant. Je fais une pause pour te signaler que l'affichage des exposants pose problème

On peut alors décomposer p et q en les divisant par basen, comme ceci :

Cdlt,

[SpiceGuid]

DVP a changé le format de mon cours.
Du coup j'ai de nombreux problèmes

Dont l'affichage des exposants.

Mais aussi l'affichage de β.

Probablement d'autres encore mais je n'ai pas le temps de tout relire

Toutes mes excuses pour ces petits désagréments.