Un P4 battu par une casio ???

**websurfeur** · 04/04/2006, 18h26

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**PRomu@ld** · 04/04/2006, 18h35

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.

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 :

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.

**Pragmateek** · 04/04/2006, 18h36

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

long long double

peut être.

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

**PRomu@ld** · 04/04/2006, 18h39

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 ...

**bigquick** · 04/04/2006, 18h45

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.

**PRomu@ld** · 04/04/2006, 18h52

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é :

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

**CGi** · 04/04/2006, 18h54

J'ai testé pour voir avec un double

factorielle(170) = 7.257415615308004024000000000000000000000e+306

avec un long double

factorielle(1754) = 1.979261890105010054000000000000000000000e+4930

(Compilateur borland)

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)

**bigquick** · 04/04/2006, 18h57

Envoyé par PRomu@ld

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

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:

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

J'ai du rater quelquechose ....

**Emmanuel Delahaye** · 04/04/2006, 19h31

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**PRomu@ld** · 04/04/2006, 19h33

unsigned long long int : max = 65

Idem sous mac (ibook G4) et gcc 4

**PRomu@ld** · 04/04/2006, 19h52

65536 ! = 51629485230 ...

En utilisant gmp.

**Lucky-94** · 05/04/2006, 03h57

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

**Lucky-94** · 05/04/2006, 04h00

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?

**PRomu@ld** · 05/04/2006, 08h08

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.

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.

**gege2061** · 05/04/2006, 16h54

Bonjour,

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

**Emmanuel Delahaye** · 05/04/2006, 17h36

Envoyé par gege2061

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

Gné ? unsigned long long peut être ?

**PRomu@ld** · 05/04/2006, 20h26

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.