From: Renaud.Rioboo@lip6.fr
To: caml-list@inria.fr
Subject: BigNum Gmp et Ocaml
Date: 10 Sep 1999 11:17:59 +0200
Bonjour,
Il y a eu récemment une petite discussion sur Ocaml et les bignums. Le projet
Foc développe une librairie de calcul formel certifiée. On sait que
l'efficacité des algorithmes de calcul formel dépend beaucoup de la qualité
des bignums qui peuvent devenir très gros.
On voulait donc tester :
- la facilité de rajouter une nouvelle librairie de bignum dans Foc,
- les performances obtenues.
Et on a mis un stagiaire de MST (Aland Valdor) sur ça. Il est parti du code de
David Monniaux permettant d'interfacer GMP et Ocaml, il a été supervisé par
Valérie Ménissier-Morain et moi même. Le travail consistait à remonter les
fonctions de mlgmp dans des classes Ocaml utilisables pour Foc.
En Foc les ensembles mathématiques sont des objets d'Ocaml qui manipulent des
structures de données laissées au choix du programmeur. Ces structures de
données sont des types Ocaml qui "représentent" les éléments de ces ensembles.
Ainsi on peut implémenter les entiers en utilisant différentes structures de
données (le type big_int de la librairie num ou le type Z.t de mlgmp).
Les classes permettent de regrouper les opérations communes à différents
objets tout en assurant un partage et une réutilisation maximale de ce qui est
général pour une famille d'ensembles donnés. Elles sont donc des structures
mathématiques et Foc a une classe (abstraite) ['a] monoide_additif qui
contient une méthode (virtuelle) plus : ('a * 'a) -> 'a. Les classes
(concrètes)
grand_entiers_big_int et
grand_entiers_gmp en héritent par
inherit [Big_int.big_int] monoide_additif et
inherit [Gmp.Z.t] monoide_additif respectivement.
Les objets plus compliqués comme les polynômes par exemple peuvent alors
recevoir :
- des paramètres de type qui vont permettre de transmettre la nature des
structures de données et celle des objets Ocaml manipulés,
- des paramètres de classes qui vont permettre de passer des valeurs Ocaml
c'est à dire soit des ensembles soit des éléments. Ainsi on peut obtenir les
classes
class ['a]entiers_modulo(a:'a)
et
class ['a,'a_set]polynomes_univaries(a:'a_set) avec la contrainte
constraint 'a_set = ('a)#anneau
Tout ceci a été implémenté, le modèle est un peu compliqué mais il marche.
On peut alors obtenir très facilement des polynômes dont les coefficients sont
soit des Big_int.big_int soit des Gmp.Z.t, l'ensemble du code "algébrique"
étant alors exactement le même.
Vous pourrez trouver plus de détails à <URL:http://www-calfor.lip6.fr/~foc>.
J'ai donc intégré le code d'A. Valdor dans la librairie Foc pour voir ce que
ça donne. Quelques petits détails :
- Ocaml 2.01 compilé avec gcc 2.7.2.1 sur sparc 10 (50Mhz) et pentium 100
- gmp 2.0.2 compilé avec gcc 2.7.2.1 sur sparc 10 et pentium 100
- l'interface mlgmp 0.13 de David Monniaux.
- le portage est "minimal", les librairies n'offrent pas les mêmes
fonctionnalités, beaucoup de choses sont implémentées en Foc. En pratique
seules la multiplication, l'addition, l'opposé, les comparaisons et le signe
viennent d'Ocaml, le reste est écrit en Foc.
- les temps sont calculés par Sys.time d'Ocaml.
L'exemple choisi est un calcul de résultant de deux polynômes. Cela utilise des
additions, multiplications, divisions exactes (implémentées en Foc à partir
des divisions "euclidiennes" de Num et Gmp).
p = x^(30) + a*x^(20) + 2*a*x^(10)+3*a
q = x^(25) + 4*b*x^(15) + 5*b*x^(5)
avec a = 10^240 et b = a+1.
Le résultant fait 10833 chiffres en base 10, les calculs intermédiaires montent
jusqu'à 4-5 fois cette taille. Voici ce que ça donne en byte code, si on
compile en code natif ça donne à peu près les mêmes temps.
+-------------+--------------+-----------------+----------------+
|Gmp Sparc 10 | Num Sparc 10 | Gmp Pentium 100 | Num Pentium 100|
+-------------+--------------+-----------------+----------------+
+ 11.15 secs + 12.13 secs + 3.24 secs + 7.15 secs +
+-------------+--------------+-----------------+----------------+
Voilà, j'espère que ça éclairera quelqu'un :-)
R. Rioboo
pour le projet Foc
<URL:http://www-calfor.lip6.fr/~foc>
This archive was generated by hypermail 2b29 : Sun Jan 02 2000 - 11:58:25 MET