Résolution d'un problème complexe
Un article de Mangue.org, l'encyclopéde libre.
Nous allons résoudre un problème complexe, le codage des grands nombres en utilisant la programmation fonctionnelle... Pas de nouvelles notions donc, juste un exercice complexe afin d'utiliser tout ce que vous savez !
| Sommaire |
Introduction
| Remarque |
| Ce cours est directement issu d'un cours dispensé à l'Université Paul Sabatier (http://www.ups-tlse.fr/) de Toulouse |
Inutile d'utiliser votre Caml pour le moment vous avez surtout besoin de réfléchir un peu ! Comme toujours nous allons partir du général pour aller vers le particulier (cette démarche n'est pas réservée à la programmation). Commençons donc par énoncer le problème...
Le Caml, bien que très orienté mathématiques est un langage de programmation comme les autres, ce qui implique que les nombres entiers codés en mémoire occupent un nombre de bits limités. Il en résulte que nous serrons incapables de dépasser 230-1 = 1 073 741 626
Comment procéder alors si on souhaite travailler avec des nombres plus grands ? La seule solution envisageable est d'implémenter un nouveau type de données, les BigNat permettant de coder des nombres plus grands !
Comment y parvenir ?
Nous allons définir un type BigNat ainsi que les fonctions dont nous aurons le plus besoin correspondant aux opérateurs arithmétiques...
La première question à se poser est de savoir comment coder ce type en mémoire. Nous pourrions penser à une tableau dans lequel chaque élément coderait un chiffre, mais ce type de données deviendrait rapidement très gourmand en mémoire. Une autre possibilité serait d'utiliser des chaînes de caractères mais cette fois-ci c'est la facilité d'utilisation qui en serait considérablement réduite.
Comme nous l'avons vu dans un cours précédent, un nombre entier, aussi grand soit-il peut-être codé de deux façons différentes. Il s'agit soit d'un chiffre en base B, soit d'un nombre, c'est à dire d'une suite de chiffres en base B.
Il semble donc tout approprié d'utiliser un type récursif pour coder nos BigNat. Mais il reste encore à choisir la base dans laquelle nos nombres serons exprimés. Celle-ci doit être la plus grande possible tout en restant dans les capacités de la machine.
Après un calcul rapide nous trouverons que la base numérique la plus grande que l'on puisse exploiter est 32767 en Caml. Cependant, et de manière à ce que le problème ne soit pas trop déroutant nous utiliserons la base 10000.
| Astuce |
En choisissant la base 10000 nous sommes d'ores et déjà capables de faire les quatre opérations élémentaires puisqu'il s'agit d'une base multiple de la base 10 que nous utilisons tous les jours.
|
Nombre en base 10 | Nombre en base 10000 | |||
|---|---|---|---|---|
| 651 | 651 | |||
| 10325 | 1 | 325 | ||
| 1234505183582 | 1 | 2345 | 518 | 3582 |
| 7253007089 | 72 | 5300 | 7089 |
Ne soyez pas surpris de voir que 7089 est un chiffre en base 10000
Définition du type
Rappellons simplement que le type BigNat est récursif, composé soit de chiffres, soit d'un chiffre suivi d'un autre BigNat.
La définition est alors évidente :
# let base = 10000 ;; base : int = 10000 # type BigNat = | Digit of int | Number of BigNat * int ;; Type BigNat defined.
| Astuce |
La constante globale base sera utilisée pour vérifier que le nombre que nous souhaitons définir en tant que BigNat (en utilisant nos fonctions d'entrées-sorties) ne possède pas de chiffres supérieurs à la base.
|
Fonction Somme
Avant de définir une fonction permettant d'ajouter deux BigNat entre eux il est nécessaire de définir une fonction permettant d'ajouer deux chiffres et de renvoyer le résultat avec l'éventuelle retenue.
# let AddDigits d1 d2 retenue = let s = d1 + d2 + retenue in ( s mod base, s / base) ;; AddDigits : int -> int -> int -> int * int = <fun>
Il est désormais possible de définir une fonction Somme prenant en argument des valeurs de type BigNat et renvoyant un résultat unique lui aussi de type BigNat...
# let Somme bignumber1 bignumber2 =
(* fonction locale récursive *)
let rec somme_aux = fun
| (Digit d1) (Digit d2) retenue ->
let ( dig, ret) = AddDigits d1 d2 retenue
in
if ( ret = 0)
then Digit dig
else Number (Digit ret, dig)
| (Digit d1) (Number (n, d2)) retenue ->
let ( dig, ret) = AddDigits d1 d2 retenue
in
if ( ret = 0)
then Number (n, dig)
else Number (somme_aux (Digit ret) n 0, dig)
| (Number (n, d1)) (Digit d2) retenue ->
(* innutile de tout réécrire, l'addition est commutative *)
somme_aux (Digit d2) (Number (n, d1)) retenue
| (Number (n1, d1)) (Number (n2, d2)) retenue ->
let ( dig, ret) = AddDigits d1 d2 retenue
in
Number (somme_aux n1 n2 ret, dig)
(* fin de fonction locale *)
in
(* appel de la fonction locale *)
(* avec les paramètres requis *)
somme_aux bignumber1 bignumber2 0 ;;
Somme : BigNat -> BigNat -> BigNat = <fun>
C'est une fonction difficile à interpréter, je le conçoie mais pourtant c'est typiquement le genre de problèmes que vous aurez à résoudre en Caml. Dans la résolution complète du problème nous écrirons également des fonctions pour la différence et le produit des nombres de ce type.
Seulement le type BigNat n'est que le début de la résolution d'un problème plus complexe dans lequel nous ne nous limitons plus au simple codage d'entiers naturels mais traitons directement des entiers relatifs, de type BigNum.
Les entrées-sorties
Nous allons maintenant écrire des fonctions permettant de passer d'une valeur de type string à une valeur de type BigNat et réciproquement. Encore une fois, vous vous en doutez, ces fonctions seront récursives.
Parcourez l'aide de votre compilateur à la recherche de la fonction sub_string. Celle-ci permet d'isoler une partie d'une chaîne de caractères afin de la traiter par la suite. C'est ce que nous allons utiliser pour passer d'une chaîne de caractères à un nombre naturel.
Pour la fonction string_of_BigNat, faites attention à ce que les 0 qui ne sont pas visibles dans le type BigNat lui même apparaissent bien dans la chaîne de caractères sans quoi le nombre ne serait plus du tout le même !
C'est à vous !
C'est maintenant à vous de résoudre le problème comme des grands ;-)
Si vous voulez des corrections sur ce que vous avez fait n'hésitez pas à me l'envoyer par mail...
Le problème sera résolu en plusieurs étapes... La première d'entre elles est de permettre le codage des nombres relatifs. Les modifications à apporter au type BigNat sont mineures puisqu'il suffit d'ajouter une information concernant le signe.
| Danger |
Certains parmis vous pourraient avoir l'idée d'utiliser le complément à 10000 pour coder les nombres relatifs dans ce système... Si vous y parvenez tant mieux mais ce n'est pas du tout ce que je vous demande puisque la complexité est bien plus élevée.
|
Vous pourrez ensuite penser à coder les fonctions Différence, Produit, etc. un peu sur le même modèle que la fonction Somme ci-dessus.
Jouez le jeu ! Cette fois-ci je ne donne aucune correction, pas même dans la page prévue pour la correctoin des exercices. Il est important que vous cherchiez par vous même... Je répondrai à chacune de vos questions sur le forum.
