Un P4 battu par une casio ???

Bonjour à tous,

Voilà je met ce message car je voullais programmer une fonction factorielle pour de grand nombre et à ma grande surprise ma casio fait ça mieux qu'un programme écrit en C, je m'explique :

Ma calculatrice casio (graph 65) peut calculer jusque 9.99999...9e+99 (quand même). C'est pourquoi je peux calculer 69! sans problème.
Voici la fonction factorielle que j'ai écrit en C

Code:

---

1 2 3 4 5 6 7 8 9

long double factorielle(int a) { int i; long double b = 1L; for(i = a ; i > 0 ; i--) b *= i; return b; }

---

j'ai choisi long double car c'est le type ayant la plus grand capacitée que j'ai trouvé. Mais ça reste quand même très limité : je ne passe pas au dessus de 20!

La taille de long double sur mon compilateur (gcc) est de 12 octets soit 12*8 = 96 bits (ce qui me permet une limite positive de (2^96)-1 = 7.922816251e+28 )

Mais comment est-ce possible ? Ma calculatrice n'a pourtant pas un processeur 32 bits (je suppose moins) !! Comment faire pour obtenir des nombre pouvant aller jusque 9.999...9e+99 ??

Merci d'avance pour vos réponses.

Citation:

---

Mais comment est-ce possible ? Ma calculatrice n'a pourtant pas un processeur 32 bits (je suppose moins) !! Comment faire pour obtenir des nombre pouvant aller jusque 9.999...9e+99 ??

---

Il n'y a pas de rapport entre le processeur et le nombre maximal que tu peux stocker.
Tout n'est qu'une question de représentation.

Citation:

---

La taille de long double sur mon compilateur (gcc) est de 12 octets soit 12*8 = 96 bits (ce qui me permet une limite positive de (2^96)-1 = 7.922816251e+28 )

---

Attention, tu es en train de croire que les réels sont représentés de la même façon que les entiers.

Si je peux me permettre d'utiliser une source qui me cite ceci on a :

Citation:

---

LDBL_MAX

#define LDBL_MAX <long double rvalue >= 10^37>

The macro yields the largest finite representable value of type long double.

---

On a donc un minimum de 10^37 ce qui est au dessus de ce que tu nous annonce.

En fait, pour en revenir à ta question, ta calculatrice utilise une représentation des réels qui lui permet de représenter des réels jusqu'a 10^99.

En C, les types primitifs ne le peuvent pas, si tu veux effectuer la même chose, tu peux utiliser des bibliothèques qui te permettent d'utiliser des nombres réels très grand. Je pense notament à gmp.

Code:

---

long long double

---

peut être.

Mais il me semble que ce n'est pas portable.

Citation:

---

Mais il me semble que ce n'est pas portable.

---

Le problème n'est pas ici, perso je ne parlerai même pas de portabilité, je parlerai d'existence ...

Petite question : si je ne me trompe pas, une factorielle est par défintion un entier >=1 (*). Pourquoi alors ne pas stocker le resultat du calcul dans un unsigned long long int ?

Un tel type permet normalement de stocker des entiers non signés de 0 à 2^64 (soit 18446744073709551615). C'est beaucoup moins que les 10^99 que tu recherches, mais déjà mieux qu'avec des doubles dont tu n'as pas l'utilité ici.

Pour faire mieux, en effet, une biliothèque tierce spécialisée dans les grands nombres (entiers ou rééls) s'impose.


* : à part peut être pour les factorielles de nombres complexes, mais je n'en connais pas assez pour m'aventurer la dedans.

Citation:

---

Petite question : si je ne me trompe pas, une factorielle est par défintion un entier >=1 (*)

---

Oui, mathématiquement parlant, c'est ça. Mais comme l'a dis le principal interressé :

Citation:

---

j'ai choisi long double car c'est le type ayant la plus grand capacitée que j'ai trouvé

---

J'ai testé pour voir avec un double

factorielle(170) = 7.257415615308004024000000000000000000000e+306


avec un long double

factorielle(1754) = 1.979261890105010054000000000000000000000e+4930

(Compilateur borland)

Citation:

---

Envoyé par aide du compilo

Type Taille (bits) Intervalle Applications exemple
double 64 1,7 ^ 10^-308 <= X <= 3,4 ^ 10^308 Scientifique (précision sur 15 chiffres)
long double 80 3,4 ^ 10^-4932 <= X <= 1,1 ^ 10^4932 Financière (précision sur 18 chiffres)

---

Citation:

---

Envoyé par PRomu@ld

Oui, mathématiquement parlant, c'est ça. Mais comme l'a dis le principal interressé :

Citation:

---

j'ai choisi long double car c'est le type ayant la plus grand capacitée que j'ai trouvé

---

---

Oui c'est vrai ;)

C'était juste pour souligner que compte tenu du problème, long double n'est pas le type ayant la plus grande capacité...
Même si l'utilisation d'entiers ne suffit pas à rivaliser avec la casio qui a surement un système de représentation plus adapté, ça sera toujours ça de gagné !

EDIT
Mmmm, après tests (sur VC6), j'obtiens:

Citation:

---

long double : max = 170
unsigned long long int : max = 65

---

J'ai du rater quelquechose .... 8O

Citation:

---

Envoyé par websurfeur

Voilà je met ce message car je voullais programmer une fonction factorielle pour de grand nombre et à ma grande surprise ma casio fait ça mieux qu'un programme écrit en C

---

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28

#include <stdio.h> #include <stdlib.h>   double factorielle(int a) { int i; double b = 1L; for (i = a ; i > 0 ; i--) b *= i; return b; }   int main(void) { double f; int n;   n = 170; f = factorielle(n); printf ("fact(%d) = %g\n", n, f);   n = 171; f = factorielle(n); printf ("fact(%d) = %g\n", n, f);   return EXIT_SUCCESS; }

---

donne (mingw/Windows XP)

Code:

---

1 2 3

fact(170) = 7.25742e+306 fact(171) = 1.#INF

---

Citation:

---

unsigned long long int : max = 65

---

Idem sous mac (ibook G4) et gcc 4

Citation:

---

65536 ! = 51629485230 ...

---

En utilisant gmp.

Il faut donc bien vérifier les entrés, saisie de l'utilisateur par exemple. Ou les arguments passé si c'est une fonction.

D'ailleur, sur à peu près le même sujet.
Pour une fonction factorielle, en terme de vitesse et d'utilisation de la mémoire, mieux vaut-il une boucle ou une fonction récursive?

Citation:

---

Il faut donc bien vérifier les entrés, saisie de l'utilisateur par exemple.

---

Comme toujours lorsqu'il y a risque que ça ne fonctionne pas.

Citation:

---

Pour une fonction factorielle, en terme de vitesse et d'utilisation de la mémoire, mieux vaut-il une boucle ou une fonction récursive?

---

C'est une question d'algo, rien à voir avec le C. Mais néanmoins, pour te répondre, je dirais qu'il n'y a aucune différence de rapidité (on ne m'a toujours pas démontré la rapidité d'un algo récurisif sur un algo itératif, et ceci algorithmiquement parlant et par rapidité j'entend complexité en temps). De plus, aucun soucis de débordement de la pile d'appel avec une telle fonction donc c'est une question de goût. Mais dans la mesure où l'algo est aussi simple en itératif qu'en récursif, peut être faut-il utiliser la version itérative.

Bonjour,

Citation:

---

Envoyé par websurfeur

j'ai choisi long double car c'est le type ayant la plus grand capacitée que j'ai trouvé.

---

Il existe (en C99) les long long codés sur au moins 64 bits! avec le type unsigned long long double tu devrais avoir de quoi t'ammuser ;)

Citation:

---

Envoyé par gege2061

avec le type unsigned long long double tu devrais avoir de quoi t'ammuser ;)

---

Gné ? unsigned long long peut être ?

Citation:

---

Gné ? unsigned long long peut être ?

---

Oui, je suppose que c'est ça. Mais pour répondre à gege2061, la fonction factorielle à une explosion en terme de taille qui est telle qu'une factorielle d'un petit nombre (disons 200) dépasse allègrement les types donnés.

Citation:

---

Envoyé par Emmanuel Delahaye

Citation:

---

Envoyé par gege2061

avec le type unsigned long long double tu devrais avoir de quoi t'ammuser ;)

---

Gné ? unsigned long long peut être ?

---

:oops: euh, je me suis emmêlé les pinceaux.