Utilisation de grands nombres en C

Voila, on me demande de réaliser un petit programme tout simple en C (un simple petit calcul de fraction ), mais voila, il y a la petite clause en bas de page, vous savez, celle qui rend toujours tout beaucoup plus compliqué

La clause en question spécifié que le résultat de l’opération devra être une approximation … sur plusieurs centaines, voire milliers, de chiffres :confused:

Donc, la question, comment travailler sur des nombres dépassant le plus grand type possible ?

On a pensé à la technique apparement la plus courante à savoir : Mettre le nombre dans un tableau où chaques cases serais une partie du grand nombre cherché (et en poussant encore un peu plus loin, effectuer un changement de base pour les nombres dans le tableau, ce qui permettrai de maximisé encore le nombre de chiffres possible).

Mais bon, on a pas toujours spécialement envie de copier ce que tout le monde fait, alors, si une personne avait une autre idée pour travailler sur de très très grand nombres, je suis preneur

ps : la vitesse d’excécution n’a pas d’importance dans notre projet.

Edit : un peu d’ortho !
Ce message a été édité par Hazadess le 05/05/2003

nombre entier? flottant? un double 64bits n’est pas suffisant?

LoneWolf

Putain vous faites des trucs rigolos, vous

Malheuresement non, aucun type n’est suffisant !

De plus, le but du projet est aussi de nous faire trouver un système pour dépasser les type du C ! Donc, je ne m’en sortirais pas avec les differents types possible !

D’un autre coter, en admettant une quantité de RAM suffisante, et un temps de calcul en conséquance, le programme devrait être capable de travailler avec une quantité infinie de chiffres ! Oui, moi aussi ça m’a foutu les boulles au debut

ps : le nombre que je cherche est un flottant (cause fraction ), si vous vous demandé !
[i]

Edit : Ajout de precision [/i]
Ce message a été édité par Hazadess le 05/05/2003
Ce message a été édité par Hazadess le 05/05/2003

[quote]Malheuresement non, aucun type n’est suffisant !

De
plus, le but du projet est aussi de nous faire trouver un système pour
dépasser les type du C ! Donc, je ne m’en sortirais pas avec les
differents types possible !

ps : le nombre que je cherche est un flottant (cause fraction ), si vous vous demandé !
Ce message a été édité par Hazadess le 05/05/2003[/quote]
Ouais, c’est evident que c’est des fractions

Je suis pas sur que ca soit une bonne idee de reinvente la roue: Les
techniques actuelles de gestion des grands nombres sont au point,
pourquoi se priver?

Je te copie/colle un bout de cours que j’ai ecrit pour une formation en
decembre:

Utilise ca pour extrapoler avec une mantisse a 500 bits par exemple. Il
existe d’autres techniques (comme les flottants monetaires, qui doivent
etre sans aucune erreur lors des calculs).

Dans l’absolu:

Struct nombre

{

  unsigned char mantisse[50]; /508bits de mantisse*/

  unsigned char exposant[5];

  unsigned char signe[1]; /C’est peut etre moins
couteux d’utiliser le dernier bits de la mantisse, mais c’est moins
clair
/

};

Un entier relatif est un entier pouvant être négatif. Il
faut donc coder le nombre de telle façon que l’on puisse savoir
s’il s’agit d’un nombre positif ou d’un nombre négatif, et il
faut de plus que les règles d’addition soient conservées.
L’astuce consiste à utiliser un codage que l’on appelle
complément à deux.

•   un entier relatif positif ou nul sera
représenté en binaire (base 2) comme un entier naturel,
à la seule différence que le bit de poids fort (le bit
situé à l’extrême gauche) représente le
signe. Il faut donc s’assurer pour un entier positif ou nul qu’il est
à zéro (0 correspond à un signe positif, 1
à un signe négatif). Ainsi si on code un entier naturel
sur 4 bits, le nombre le plus grand sera 0111 (c’est-à-dire 7 en
base décimale).

D’une manière générale le plus grand entier
relatif positif codé sur n bits sera 2n-1-1

•   un entier relatif négatif grâce au
codage en complément à deux.

Principe du complément à deux ; soit à
représenter un nombre négatif :

o   Prenons son opposé (son équivalent en
positif)

o   On le représente en base 2 sur n-1 bits

o   On complémente chaque bit (on inverse,
c’est-à-dire que l’on remplace les zéros par des 1 et
vice-versa)

o   On ajoute 1

On remarquera qu’en ajoutant le nombre et son complément
à deux on obtient 0…

Voyons maintenant cela sur un exemple:

On désire coder la valeur -5 sur 8 bits. Il suffit :

•   d’écrire 5 en binaire: 00000101

•   de complémenter à 1: 11111010

•   d’ajouter 1: 11111011

•   la représentation binaire de -5 sur 8 bits
est 11111011

Remarques :

Le bit de poids fort est 1, on a donc bien un nombre négatif.

Si on ajoute 5 et -5 (00000101 et 11111011) on obtient 0 (avec une
retenue de 1…)

2.5.3   Représentation d’un nombre réel

Il s’agit d’aller représenter un nombre binaire à virgule
(par exemple 101,01 qui ne se lit pas cent un virgule zéro un
puisque c’est un nombre binaire mais 5,25 en décimale) sous la
forme 1,XXXXX… * 2n (c’est-à-dire dans notre exemple
1,0101*22). La norme IEEE 754 définit la façon de coder
un nombre réel.

Cette norme se propose de coder le nombre sur 32 bits et définit
trois composantes :

•   le signe est représenté par un seul
bit, le bit de poids fort (celui le plus à gauche),

•   l’exposant est codé sur les 8 bits
consécutifs au signe,

•   la mantisse (les bits situés après la
virgule) sur les 23 bits restants.

Ainsi le codage se fait sous la forme suivante :

seeeeeeeemmmmmmmmmmmmmmmmmmmmmmm

•   le s représente le bit relatif au signe

•   les e représentent les bits relatifs
à l’exposant

•   les m représentent les bits relatifs
à la mantisse

Certaines conditions sont toutefois à respecter pour les
exposants :

•   l’exposant 00000000 est interdit

•   l’exposant 11111111 est interdit. On s’en sert
toutefois pour signaler des erreurs, on appelle alors cette
configuration du nombre NaN, ce qui signifie Not a number

•   les exposants peuvent ainsi aller de -126 à
127

•   L’exposant e est égal à
e=(exposant+127)

Voyons voir ce codage sur un exemple :

Soit à coder la valeur 525,5

•   525,5 s’écrit en base 2 de la façon
suivante : 1000001101,1

•   on veut l’écrire sous la forme 1.0000011011
x (2^9)

•   Par conséquent : le bit s vaut 0, l’exposant
vaut 9, soit 9+127, soit 10001000 la mantisse est 0000011011, car le 1
disparaît lorsque l’on utilise la norme IEEE

•   La représentation du nombre 525.5 en binaire
avec la norme IEEE est :

0 10001000 0000011 0110 0000 0000 0000

Edit: des trucs qui sont pas passe au copy/paste

LoneWolf

Le codage des nombres, c’est rigolo :-;;
Ce message a été édité par LoneWolf le 05/05/2003

Tu peux peut-être pêcher quelques idées ici …

GNU MP : http://www.swox.com/gmp/

Librairie GNU avec des types int, float, etc … en précision infinie (enfin, pour autant que tu as de la RAM qui reste)

Edit: LoneWolf powaah …
Ce message a été édité par Tele le 05/05/2003

Merci LoneWolf ! Dingue, on dirait un copier/Coller de mes cours de septembre dernier (en plus compréhensible quand meme )

Ainsi qu’un grand poutou baveux a Tele avoir trouve cette url !!

Je n’ai pas vraiment de merite, je n’ai fait que reprendre des cours
existant sur le web, et les remanier a ma sauce personnelle.

A noter que l’exemple IEEE, tous les exemples trouves etaient faux, j’en ai chier pour trouver la bonne methode de calcul

LoneWolf

Mais c’etait fun, putain… Rah jouer avec les octets, miam
Ce message a été édité par LoneWolf le 05/05/2003

Aaaaah la pire classe du monde, les codages des nombres…non mais c’est horrible, je me suis jamais autant emmerdé pour un truc que j’ai JAMAIS utilisé )

Attention, c’est peut-être star utile pour beaucoup de monde mais perso, brrrr, je déteste ça…et j’ai jamais eu besoin de ressortir mes vieux cours (et pourvu que ça dure ^^;

[/3615 MaVie]

[quote]Attention, c’est peut-être star utile pour beaucoup de monde mais perso, brrrr, je déteste ça…et j’ai jamais eu besoin de ressortir mes vieux cours (et pourvu que ça dure ^^;

Moi j’adore ca. Je me souvenais plus de la technique du complement a 2
pour les negatifs, mais quand on reflechit 5 min, elle est totalement
geniale, cette methode.

LoneWolf

Mais bon, je suis electronicien a la base, aussi…
Ce message a été édité par LoneWolf le 05/05/2003