Calcul sur de grand nombre

Question

Bonjour,

Je suis actuellement sur un projet où mon but est de créer une calculatrice qui sera capable de calculer des nombres plus grand que des doubles.
Là où ça se corse c'est que je m'interdit l'utilisation de la classe Math.
Je décide donc de metre les nombres sous forme de string pour pouvoir les stocker, car un string permet d'avoir plus de caractère que toute les aures classes que j'ai trouvé. 
Mon problème est que pour faire les calculs, je ne peux pas faire String + String.
Donc je déroule les deux String en faisant une addition à la main avec une boucle. C'est lourd mais ça peut passer. Mais lorsque je ferai la multiplication ou encor pire la puissance ... mes calcul vont être horriblement long.

Je voulais savoir si vous connaissiez une methode ou un algo, ou même une piste à creuser, car là ça me parait vraiment très arcaique ma façon de faire.

danimo · Answer

Salut,

As-tu regardé la classe BigIntger (que je n'ai jamais utilisée) ?

...\ Dan /...

cs_Julien39 · Answer

Bonjour,

La classe biginteger peut être intéressante mais je pense que le but de ton projet est de créer un package qui fournit les mêmes services que bigInteger. 

Un BigInteger est enregistré sous la forme d'un tableau de byte, c'est peut être une idée qui te permettrait d'avoir un objet moins lourd que le String à gérer. Pour pouvoir augmenter la taille de ton objet, tu peux peut être même utiliser une ArrayList.

Je vais te dire exactement ce que je ferais si jétais toi.

Je définierais une classe Chiffre qui contient un attribut byte, ensuite, je définierais une classe Nombre qui contient une arrayList<Chiffre>. Ensuite tu définis les opérations de calcul sur les nombres, tu peux également en faire pour les chiffres.

Tu peux cehrcher sur internet, il y a des algorithmes d'optimisation des opérations, leur but est de limiter le nombre d'opérations à effectuer. En gros, pour ton pc faire 2*2 coute aussi cher que de faire 999*999, par contre, ce qui prend du temps c'est de répéter ces opérations. Je te donne un exemple que je connais pour l'exponentiation.

Supposons que tu cherhces à faire une fonction qui calcul 10^10 (je sais pas besoin d'une fonction mais admettons) tu peux multiplier 10 fois le nombre 10.

Pour effectuer cette algorithme, tu as effectué 10 calculs 10*10*10*10*10*10*10*10*10*10* 

En revanche, si tu fais ceci :

10^10
= (10^2)^5 
= (10^2)*((10^2)^4)
= (10^2)*((10^2)^2)^2
Si tu fais le calcul du nombre d'opérations :
Calcul de 10^2 = 100
Calcul de (10^2)^2=100^2 = 10000

On a fait deux calculs pour l'instant

On calcul ensuite le résultat 
(10^2)*((10^2)^2)^2 = 100*10000*10000
Cette opération te coute 2 calculs.

Donc, à la fin, tu as effectué seulement 4 calculs (donc ton programme ira deux fois plus vite)

Si tu veux j'ai implémenté cet algo en vb, il y quelques années maintenant, tu peux regarder, c'est très simple : http://www.vbfrance.com/codes/EXPONENTIATION-RAPIDE_34807.aspx

Si c'est pour un projet de fin d'études, c'est ce genre d'algorithme qui te fera passer du 12 au 18.

Dinsfire · Answer

Merci beaucoup pour votre aide, je vais m'inspirer des byte et arraylist. Pour l'optimisation des calculs ça me rappelle les cours d'arithmétiques. JE vais monté de suite le parseur avec les bytes, car j'y avais pas pensé mais c'est vraiment pas bête ^^'
J'aurai préféré que ce soit un projet de fin d'année, mais c'est un projet a faire en 1 mois donc je dois me dépêcher, je vais jeter un coups d'oeil a ton implémentation si je suis blocké. Merci encore, je vous donnerai des nouvelle de comment ça avance ;)

cs_Julien39 · Answer

Si c'est un projet d'un mois, je ne pense pas que l'optimisation des algorithmes de calcul soit attendue. Essaye de faire fonctionner les opérations de base et ce sera déjà pas mal.

Calcul sur de grand nombre

4 réponses

Votre réponse

Discussions similaires