Programmer en CAMLLIGHT

Résumé du document

Le but de ce projet est de programmer en CAMLLIGHT quelques manipulations élémentaires de grands nombres entiers naturels représentés par des listes de chiffres. Nous implémenterons en particulier l'addition, la soustraction et la multiplication de deux grands entiers. Nous terminerons par quelques expérimentations comme le calcul de la fonction factorielle et de la fonction de Fibonacci sur de grandes entrées ainsi que le calcul de l'exponentielle de deux grands entiers par la méthode usuelle et par la méthode Russe.

Extraits

[...] Voici le code de ces deux fonctions : let rec big_fact = fun s s (big_fact # big_fact : string string let rec big_fb = fun s let = big_fb in let big_fib s = let = (big_fb in # big_fib : string string Exemples : big_fact 50 # - : string = big_fib 200 # - : string = 453973694165307953197296969697410619233826 Nous voulons maintenant calculer l'exponentielle de deux grands entiers. Nous programmons alors deux versions : la première est une simple itération de la multiplication et la seconde utilise la méthode russe en base 10. [...]

[...] REPRESENTATION DES GRANDS ENTIERS Nous définissons le type digit de la manière suivante : Nous pouvons maintenant définir deux fonctions simples permettant de passer d'un digit à un chiffre de type int, et réciproquement : let int_of_digit = fun # int_of_digit : digit int let digit_of_int = fun m raise(Failure "digit_of_int Entrée Incorrecte # digit_of_int : int digit Exemples : int_of_digit d0 digit_of_int 5 # - : int = 0 # - : digit = d5 Un grand nombre entier est donc une liste de digit (poids faibles en tête de liste). [...]

[...] La différence de rapidité est plus flagrante pour de grandes entrées. DIVISION DE DEUX GRANDS ENTIERS Nous programmons tout d'abord deux petites fonctions comparant le nombres de chiffres respectifs de deux grands entiers (nous préférons travailler dans ce chapitre sur des grands entiers de type string) : let inf s1 s2 = (string_length s1) [...]

[...] PARISOT Olivier DEUG MIAS 2 MONIER BENJAMIN GROUPE 3 MODULE DE PROGRAMMATION FONCTIONNELLE PROJET D'INFORMATIQUE MANIPULATION DE GRANDS NOMBRES UNIVERSITE DE METZ ANNEE CAMPUS BRIDOUX 1999 / 2000 BUT DU PROJET Le but de ce projet est de programmer en CAMLLIGHT quelques manipulations élémentaires de grands nombres entiers naturels représentés par des listes de chiffres. Nous implémenterons en particulier l'addition, la soustraction et la multiplication de deux grands entiers. Nous terminerons par quelques expérimentations comme le calcul de la fonction factorielle et de la fonction de Fibonacci sur de grandes entrées ainsi que le calcul de l'exponentielle de deux grands entiers par la méthode usuelle et par la méthode Russe. [...]

[...] Son principe n'est pas d'une grande complexité. En effet elle calcule le produit entre ce digit et chaque élément de la liste et concatène le tout. Sans oublier évidemment de reporter à chaque fois la retenue : let mult_digit n = clean (mult_dgt d0 n where rec mult_dgt = fun r d0 l r n r n let p = ((int_of_digit * (int_of_digit + (int_of_digit in (digit_of_int mod 10))::(mult_dgt (digit_of_int (div_int p n # mult_digit : digit digit list digit list Remarquons que l'emploi de la fonction clean n'est pas inutile : mult_digit est fait de telle façon qu'il laisse des d0 non significatifs alourdissant le résultat. [...]