Arithmétique






Contexte informatique

Nous vous proposons de travailler sous Eclipse. (Si vous préférez utiliser Emacs, voici des instructions.) Pour cela, vous devez installer un plug-in Eclipse pour OCaml. Voici les instructions pour le faire.

  1. Lancer Eclipse, par exemple avec un nouveau workspace inf549.
  2. Cliquer sur le menu Help > Install New Software...
  3. Cliquer sur le bouton Add, entrer l'adresse http://www.algo-prog.info/ocaide/ dans le champ Location, puis cliquer sur OK.
  4. Cocher OcaIDE, cliquer deux fois sur Next, accepter la license, puis cliquer sur Finish.
  5. Accepter l'installation (le plug-in n'est pas signé) et redémarrer Eclipse quand cela est proposé.
  6. Utiliser le bouton Open Perspective en haut à droite pour sélectionner la perspective OCaml.
  7. Créer un nouveau projet avec le menu File > New > OCaml project (ocamlbuild) et lui donner le nom td1.

1 Algorithme d'Euclide

Ajouter un nouveau module dans le projet td1 avec le menu contextuel New > Module du projet et lui donner le nom pgcd. Un fichier source pgcd.ml doit s'ouvrir. On pourra y copier-coller le modèle suivant.

Compléter la fonction pgcd de type int -> int -> int qui calcule le pgcd selon la méthode d'Euclide, c'est-à-dire

pgcd(u, 0) = u
pgcd(u, v) = pgcd(v, u mod v) sinon

Pour compiler, sélectionner Properties dans le menu contextuel du projet, sélectionner Project et inscrire pgcd.byte dans la boîte Targets. Un exécutable pgcd.byte doit alors apparaître dans l'explorateur du projet. On peut le lancer avec son menu contextuel Run As > OCaml Executable, puis le relancer à chaque fois avec le bouton Run d'Eclipse ou avec Ctrl-F11.

On doit obtenir 

4
6
dans l'onglet OCaml Toplevel.
Solution.

2 Une autre technique pour le PGCD

Au collège, on ne connaît pas encore l'algorithme d'Euclide, et on calcule le PGCD différemment : en décomposant les nombres u et v en facteurs premiers, puis en identifiant les facteurs communs.

On s'inspire ici de cette technique. Supposons connue la suite des nombres premiers p1=2, p2=3, p3=5, etc. L'idée est d'essayer de diviser u par les nombres premiers pris dans l'ordre :

décompose(i, 1) =  []   
décompose(i, u) = pi :: décompose(i, u/pi)    si pi divise u
décompose(i, u) = décompose(i+1, u)    si pi ne divise pas u

En fait, l'algorithme fonctionne toujours si on remplace la suite des pi par une suite croissante (qi), commençant à 2 et qui contient les nombres premiers (les pi, donc). En effet, par construction et à chaque étape, u n'est divisible par aucun des qk avec k < j, et donc u n'est pas non plus divisible par un nombre premier strictement inférieur à qj. Donc, si qj est un diviseur de u, alors qj n'a pas de facteur premier strictement plus petit que qj, c'est-à-dire qj est premier.

Si on veut optimiser un peu, on peut choisir la suite définie par

q1 = 2,    q2 = 3,    qj+1 = qj+2 (j ≥ 2)
afin d'éviter de tester les entiers pairs à partir de 4.

On peut aussi terminer plus rapidement. Soit qj tel que v, résultat de la divison euclidienne de u par qj, est strictement plus petit que qj, alors u est premier. En effet, d'une part, v < qj entraîne qj × qj > u (u = qj × v + r avec r < qj et v < qj. et donc u < qj × (v + 1) ≤ qj × qj), et d'autre part, la définition de décompose entraîne que u n'est divisible par aucun nombre pris dans [2…qj[. Soit f tel que 2 ≤ f et f × f ≤ u, alors on a nécessairement f < qj (sinon, f × f ≥ qj × qj > u). Soit finalement f n'est pas un facteur de u. Or, si u n'est pas premier, alors il existe deux nombres f et g, avec 2 ≤ f ≤ g et u = f × g. Et donc u possède un diviseur propre f, avec f × f ≤ u. Bref, on peut ajouter la règle :
décompose(i, u) = u    si u/qj < qj

2.1 Décomposer en facteurs premiers
Écrire une fonction decompose de type int -> int list qui prend un entier u en argument et renvoie la liste de ses facteurs premiers.

Il est conseillé d'écrire une fonction auxiliaire préalable qui suit la définition « théorique » décompose, mais prend en argument qi et la valeur courante de u. Dans un premier temps, on peut s'abstenir des optimisations signalées.

On pourra tester avec le code suivant 
let rec print_ints l = match l with
  | []    -> Printf.printf "\n"
  | [x]   -> Printf.printf "%d\n" x
  | x::xs -> Printf.printf "%d " x; print_ints xs

let () =
  print_ints (decompose 524287);
  print_ints (decompose 1048575);
  print_ints (decompose 2097151)
et on doit obtenir le résultat suivant : 
524287
3 5 5 11 31 41
7 7 127 337
Solution.

2.2 Retrouver le PGCD
Il suffit maintenant d'identifier les facteurs communs à u et v et de les multiplier entre eux pour retrouver le pgcd.
  1. Écrire une fonction communs de type int list -> int list -> int list qui prend en argument deux listes d'entiers triées selon l'ordre croissant et qui renvoie la liste des entiers communs aux deux listes. Il convient de profiter de l'ordre des listes pour écrire une fonction de coût linéaire en la somme des longueurs de ses arguments. La bonne façon de décomposer les listes en OCaml est d'utiliser le filtrage, c'est-à-dire la construction match with ou la construction function.
    Solution.
  2. Écrire une fonction produit de type int list -> int qui renvoie le produit des éléments de la liste passée en argument. Trouver une convention raisonnable pour le cas de la liste vide.
    Solution.
  3. En déduire une fonction qui calcule le pgcd de deux entiers selon la méthode apprise au collège.
    Solution.

Tester avec le code suivant : 

let () = Printf.printf "%d\n" (pgcd 8 12)
let () = Printf.printf "%d\n" (pgcd 48 18)
let () = Printf.printf "%d\n" (pgcd 1048575 3100)
On doit obtenir le résultat suivant : 
4
6
775
3 Vérification
Nous disposons maintenant de deux fonctions pour calculer le pgcd. Nous allons vérifier qu'elles renvoient bien les mêmes résultats en procédant à quelques tests.

Écrire une fonction verification: int -> int -> unit qui prend en arguments deux entiers m et n et procéde à n essais, consistant en un tirage pseudo-aléatoire de deux entiers u et v compris entre 1 et m (voir Random.int), au calcul du pgcd selon les deux méthodes et à leur comparaison.

En cas d'échec le programme doit afficher un message explicatif. La fonction Printf.printf permet de composer de beaux messages. Pour afficher un beau message donnant le contenu de la variable i on procède ainsi :

  Printf.printf "i=%d\n" i (* «\n» est le retour à la ligne *)

Tester avec 
let () = verification 1_000_000 1_000
c'est-à-dire 1000 tests avec des valeurs comprises entre 1 et 1000000.
Solution.

4 Le PPCM comme au collège
Les décompositions en facteurs premiers de u et v permettent de trouver la décomposition du ppcm (Plus Petit Commun Multiple) de u et de v.

Modifier un peu votre programme pour qu'il trouve et affiche le PPCM.
Solution.

Ce document a été traduit de LATEX par HEVEA et HACHA.