Bibliothèque sur les nombres

Version imprimable

18/12/2010, 15h02
servalanime

Bibliothèque sur les nombres

Bonjour,

Voila, pour un petit programme que je me fais, j'ai besoin de manipuler des nombres un petit peu grand:
( les nombres seront compris entre 0 et 100 000 000 000 000 environ ).

Les manipulations seront des additions, soustractions, multiplications et divisions par des entiers et des flottants, et les résultats devront être retournés sour la forme d'entier.

Pour cela, j'ai tenté d'utiliser des tableaux mais c'est plus galère qu'autre chose ^^ : je dois recoder des méthodes de calculs sur les cases d'un tableau et c'est chiant (autant dire les choses telles qu'elles sont).

Après m'être renseigné, j'ai trouvé la bibliothèque GMP qui a l'air très intéressante pour effectué les calculs sur mes nombres. J'ai pas encore commencé à coder mes classes, donc je n'ai pas encore jeter d'oeil sur le fonctionnement de la librairie.

Ma première question: est ce judicieux d'utiliser cette librairie et pas une autre ?

Pour plus tard:
Je programme sous Linux (ma console est mon ami :p )et j'ai envie que mon programme soit compatible sur Linux et sur Windows une fois que j'aurai fini.

Des suggestions pour ? Car je ne vois pas comment je pourrais exporter mon programme pour qu'il utilise ma 'future' librairie sous windows et que je puisse ainsi transmettre mon programme compilé facilement.

Je sais pas si je suis très clair ( il fait froid, il neige et je suis fatigué :p ).

Cordialement,
18/12/2010, 15h14
droggo

Lai,

Oui, GMP est une très bonne bibliothèque.

Je te conseille de l'utiliser plutôt que de faire la tienne, sauf si c'est pour apprendre.

Car la base est facile et rapide à implémenter, mais si on veut aller vite, ça demande pas mal d'optimisations, ET l'implémentation de divers algorithmes "rapides".
20/12/2010, 21h01
servalanime

La bibilothèque est un peu difficile d'utilisation, mais je pense avoir saisi le 'truc'.

J'avais commencer à me coder les méthodes à la main en gérant mes nombres sous forme de tableau, autant les additions et les soustractions ca va par contre, les multiplications et les divisions, c'est un peu plus compliqué ^^'

Citation:

Car la base est facile et rapide à implémenter, mais si on veut aller vite, ça demande pas mal d'optimisations, ET l'implémentation de divers algorithmes "rapides".

Je ne saisi pas exactement ce que tu veux dire.
22/12/2010, 10h28
Emmanuel Deloget

Citation:

Envoyé par servalanime

Je ne saisi pas exactement ce que tu veux dire.

C'est pourtant simple : comment implémente-tu une multiplication entre deux grand nombres ?

La réponse naïve est : on implémente l'algorithmes qu'on utilisait lorsqu'on avait 10 ans, et qu'on utilise toujours lorsqu'on pose une opération sur le papier. Mais on se rend compte rapidement que ces algorithmes sont lents pour deux nombres de N et M digits dans la base sélectionnée, il faut un nombre d'opérations proche de NxM.

Ou on utilise l'algorithme de Schönhage–Strassen qui passe par une transformée de Fourier rapide.

Des opérations qui paraissent triviales telles la multiplication cachent en fait une complexité assez importante. D'ou la remarque de droggo.

Ceci dit, pour une solution simple à ton problème, et pourvu que les nombres ne dépassent jamais 2^50 (environ 1,000,000,000,000,000), tu dois pouvoir t'en sortir avec un tableau de 2 ou 4 entiers de 64 bits (tu peux en mettre un peu plus si tu as des nombres plus importants). Vu la petitesse des tableaux, il est alors inutile de cherche plus loin que les algorithmes naïfs pour obtenir le résultat de tes opérations. Il faudra par contre les coder avec soin.
22/12/2010, 10h50
Jean-Marc.Bourguet

Citation:

Envoyé par Emmanuel Deloget

Ceci dit, pour une solution simple à ton problème, et pourvu que les nombres ne dépassent jamais 2^50 (environ 1,000,000,000,000,000), tu dois pouvoir t'en sortir avec un tableau de 2 ou 4 entiers de 64 bits (tu peux en mettre un peu plus si tu as des nombres plus importants).

Si les nombres ne depassent pas 2^63 en valeur absolue, un entier de 64 bits suffit chez moi ;)
22/12/2010, 11h08
Emmanuel Deloget

Citation:

Envoyé par Jean-Marc.Bourguet

Si les nombres ne depassent pas 2^63 en valeur absolue, un entier de 64 bits suffit chez moi ;)

Ok pour l'addition et la soustraction, mais la multiplication de deux entiers de 63 bits produit un entier de 126 bits, ce qui va faire court sur un long long :)

(et pour info, j'ai choisi 2^50 parce que c'est la première puissance de 2 proche d'une puissance de 10 qui permettent de stocker des valeurs allant jusqu'à 100,000,000,000,000).
22/12/2010, 12h03
Jean-Marc.Bourguet

Citation:

Envoyé par Emmanuel Deloget

Ok pour l'addition et la soustraction, mais la multiplication de deux entiers de 63 bits produit un entier de 126 bits, ce qui va faire court sur un long long :)

Il y aurait des nombres qui depassent 2^63 ;)

Plus serieusement, les algo simples ont generalement des constantes plus petites faisant qu'ils sont preferables sur les donnees plus petites. Pour les multiplications, si j'ai bonne memoire, GMP passe a un algo non naif qu'au dela de 500 bits environ(*) et utilise 2 ou 3 autres algo avant d'aborder celui utilisant la FFT.

(*) C'est calibre par plateforme et ils ont des routines en assembleur permettant de faire baisser encore la constante multiplicatives.

Citation:

les multiplications et les divisions, c'est un peu plus compliqué

La multiplication me semble simple, on fait comme a la main. Faire comme a la main n'est pas si simple pour la division -- on joue aux devinettes pour trouver les chiffres -- mais D.E. Knuth a donne un moyen de ne pas trop deviner en normalisant les donnees. Je le redonne ici:
http://www.bourguet.org/v2/cs/division/ avec une demonstration differente de celle de Knuth (qui est par l'absurde a certaines etapes et me laisse comme beaucoup de demonstration par l'absurde l'impression d'etre d'accord sans reellement comprendre pourquoi c'est comme ca. Je ne suis pas sur que ma demonstration donne une meilleure comprehension, mais l'etablir me l'a donnee a moi).