IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Caml Discussion :

multiplication de deux polynômes


Sujet :

Caml

  1. #1
    Membre du Club
    Homme Profil pro
    C++
    Inscrit en
    Janvier 2013
    Messages
    45
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : C++

    Informations forums :
    Inscription : Janvier 2013
    Messages : 45
    Points : 44
    Points
    44
    Par défaut multiplication de deux polynômes
    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 : 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
    voici mon programme :
    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)

  2. #2
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Points : 2 990
    Points
    2 990
    Par défaut Auto-promotion éhontée
    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
    Du même auteur: mon projet, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

  3. #3
    Membre du Club
    Homme Profil pro
    C++
    Inscrit en
    Janvier 2013
    Messages
    45
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : C++

    Informations forums :
    Inscription : Janvier 2013
    Messages : 45
    Points : 44
    Points
    44
    Par défaut
    Bonjour,
    merci beaucoup pour ces pistes de documentation !

  4. #4
    Membre émérite
    Avatar de prgasp77
    Homme Profil pro
    Ingénieur en systèmes embarqués
    Inscrit en
    Juin 2004
    Messages
    1 306
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 36
    Localisation : France, Eure (Haute Normandie)

    Informations professionnelles :
    Activité : Ingénieur en systèmes embarqués
    Secteur : High Tech - Électronique et micro-électronique

    Informations forums :
    Inscription : Juin 2004
    Messages : 1 306
    Points : 2 466
    Points
    2 466
    Par défaut
    Citation Envoyé par SpiceGuid Voir le message
    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,
    -- Yankel Scialom

  5. #5
    Membre émérite
    Avatar de SpiceGuid
    Homme Profil pro
    Inscrit en
    Juin 2007
    Messages
    1 704
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : Juin 2007
    Messages : 1 704
    Points : 2 990
    Points
    2 990
    Par défaut S'il n'y avait que ça comme problème
    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.
    Du même auteur: mon projet, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

Discussions similaires

  1. [Turbo Pascal] Addition de deux polynômes avec liste chaînée
    Par Ecquini dans le forum Turbo Pascal
    Réponses: 15
    Dernier message: 01/11/2011, 20h11
  2. Multiplication de deux signaux
    Par Neocid dans le forum Signal
    Réponses: 10
    Dernier message: 03/03/2008, 12h52
  3. Calcul de la multiplication de deux matrices
    Par al_alias dans le forum Pascal
    Réponses: 2
    Dernier message: 30/05/2007, 23h37
  4. Réponses: 8
    Dernier message: 14/05/2007, 18h10
  5. [OCaml] Multiplication de deux polynômes
    Par snyper_ubi dans le forum Caml
    Réponses: 1
    Dernier message: 17/10/2006, 18h12

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo