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é :
voici mon programme :
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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
____
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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)
Partager