Publicité
+ Répondre à la discussion
Affichage des résultats 1 à 5 sur 5
  1. #1
    Candidat au titre de Membre du Club
    Homme Profil pro Julien
    Eternel étudiant
    Inscrit en
    janvier 2013
    Messages
    37
    Détails du profil
    Informations personnelles :
    Nom : Homme Julien
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Eternel étudiant

    Informations forums :
    Inscription : janvier 2013
    Messages : 37
    Points : 12
    Points
    12

    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 :
    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)

  2. #2
    Rédacteur
    Avatar de SpiceGuid
    Homme Profil pro Damien Guichard
    Inscrit en
    juin 2007
    Messages
    1 574
    Détails du profil
    Informations personnelles :
    Nom : Homme Damien Guichard
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : juin 2007
    Messages : 1 574
    Points : 2 707
    Points
    2 707

    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: le cours OCaml, 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
    Candidat au titre de Membre du Club
    Homme Profil pro Julien
    Eternel étudiant
    Inscrit en
    janvier 2013
    Messages
    37
    Détails du profil
    Informations personnelles :
    Nom : Homme Julien
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Eternel étudiant

    Informations forums :
    Inscription : janvier 2013
    Messages : 37
    Points : 12
    Points
    12

    Par défaut

    Bonjour,
    merci beaucoup pour ces pistes de documentation !

  4. #4
    Membre Expert Avatar de prgasp77
    Homme Profil pro Yankel Scialom
    Ingénieur en systèmes embarqués
    Inscrit en
    juin 2004
    Messages
    1 083
    Détails du profil
    Informations personnelles :
    Nom : Homme Yankel Scialom
    Âge : 27
    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 083
    Points : 1 451
    Points
    1 451

    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,

  5. #5
    Rédacteur
    Avatar de SpiceGuid
    Homme Profil pro Damien Guichard
    Inscrit en
    juin 2007
    Messages
    1 574
    Détails du profil
    Informations personnelles :
    Nom : Homme Damien Guichard
    Localisation : France, Loire (Rhône Alpes)

    Informations forums :
    Inscription : juin 2007
    Messages : 1 574
    Points : 2 707
    Points
    2 707

    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: le cours OCaml, le dernier article publié, le blog dvp et le jeu vidéo.
    Avant de poser une question je lis les règles du forum.

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •