Discussion :

[Wachter]

Bonjour,

J'ai écrit un code qui affiche un nombre entier N sous la forme : N = a₁ x 1! + a₂ x 2! + ... + a_p x p! avec a₁ + ... + a_p minimal.

Exemple 1
Entrée : N = 52
Sortie : p = 4 ; les coefficients sont : 0, 2, 0, 2

Exemple 2
Entrée : N = 120
Sortie : p = 5 ; les coefficients sont : 0, 0, 0, 0, 1

J'obtiens l'erreur Floating Point Exception sur un serveur d'évaluation pour un entier donné que j'ignore (N <= 500 millions). Pourtant, j'ai évité une division par 0 (ou un modulo).

Pour N = 479 000 000, j'ai p = 11 et les coefficients : 0, 1, 1, 3, 4, 4, 7, 8, 9, 10, 11
Pour N = 480 000 000, il affiche p = 12 puis se plante !

Code cpp :

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
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <stack>
#include <cstdio>
using namespace std;
stack<int> coef;
 
 
int main()
{
   int nb;
   scanf("%d", &nb);
 
   int fact = 1;
   int rang = 1;
   while (fact <= nb)
   {
       rang = rang + 1;
       fact = fact * rang;
   }
   fact = fact / rang;
   rang = rang - 1;
 
   printf("%d\n", rang);
   coef.push(nb / fact);
 
   while (rang >= 2)
   {
       nb = nb % fact;
       fact = fact / rang;
       rang = rang - 1;
       coef.push(nb / fact);
   }
 
   while(!coef.empty())
   {
       printf("%d ", coef.top());
       coef.pop();
   }
}

Merci pour votre aide !

[Bousk]

Y'a fort à parier que fact = fact / rang; vaut 0 à un moment donné.
Utilise un vrai debugger et tu le sauras assez vite.

[imperio]

De manière générale, j'ai toujours tendance à me méfier des divisions (et des modulos aussi). Si je suis certain que le diviseur ne sera jamais 0, je n'y mets pas de condition, sinon :

Code :

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

1
2
3
float nombre, diviseur;
 
nombre = (diviseur != 0 ? nombre / diviseur : 0);

[Jean-Marc.Bourguet]

13! = 6227020800 > INT_MAX après quoi on ne peut plus compter sur rien.

@imperio, pourquoi utiliser des float ici? (en général, il vaut mieux ne pas utiliser les flottants. Quand il le faut, les doubles sont le choix normal, les floats ayant une précision faible ne sont à utiliser qu'après avoir montré qu'ils conviennent)

[imperio]

@Jean-Marc.Bourguet: Pas de raison particulière. Ça aurait tout aussi bien pu être un char qu'un unsigned long double. Je donnais juste un exemple.

Concernant la précision faible des floats, je ne suis pas sûr de te suivre. La majorité des codes de bibliothèques mathématiques que j'ai vu utilisaient des floats et non des doubles. Si c'était vraiment si faible que ça, pourquoi ne pas utiliser des doubles dans ce cas ?

[bacelar]

Pour la vitesse.

[Jean-Marc.Bourguet]

@Jean-Marc.Bourguet: Pas de raison particulière. Ça aurait tout aussi bien pu être un char qu'un unsigned long double. Je donnais juste un exemple.

Concernant la précision faible des floats, je ne suis pas sûr de te suivre. La majorité des codes de bibliothèques mathématiques que j'ai vu utilisaient des floats et non des doubles. Si c'était vraiment si faible que ça, pourquoi ne pas utiliser des doubles dans ce cas ?

La totalité des bibliothèques mathématiques que j'ai vu étaient soit disponible en float, double, voire extended et quad, ou pour celles en C++ template sur le type flottant. Et faites par des gens capables de faire l'analyse de propagation d'erreur. Un float a 24 bits de précision. Un calcul naïf perd facilement un bit par niveau. Plus si la malchance s'en mêle.

Pour la vitesse.

Ça reste à mesurer.

En fait, tout dépend des calculs, si c'est du calcul relativement simple, homogène à faire sur des masses de données, float a du sens, en particulier si c'est vectorisable ou que le facteur limitant est la bande passante. Sinon je maintiens: float n'est pas le type à utiliser par défaut.

[bacelar]

Attention, je suis à 200% derrière Jean-Marc.Bourguet sur le faite qu'on doit utiliser double par défaut.
S'il y a des float dans des bibliothèques numériques c'est que cela peut avoir un avantage de vitesse (calcul parallélisable sur architecture SIMD, etc.), je ne chercherai pas des poux dans les cheveux dans la tête des auteurs de bibliothèques qui ont largement un niveau supérieur à la moyen en ce qui concerne l'analyse numérique et l'optimisation algébrique.

[Wachter]

Je vous remercie pour vos interventions.

Cependant, ce que je ne comprends pas c'est que la condition rang >= 2 devrait logiquement empêcher une éventuelle division par zéro dans l'instruction fact = fact / rang;.

Pour ce qui est d'un éventuel dépassement de la limite du type int, on est certain de calculer au plus 12! (N <= 500 000 000).

[Astraya]

Pour la vitesse.

Quoi? un double est plus rapide qu'un float?

Un petit récap de comment fonctionne la mémoire et la taille des bus...
Si le bus mémoire est de 32 bits soit 4 octets donc il lit des lignes de 4 octets dans la mémoire, donc si le programme demande de lire un float (4 octets aligné sur 32/64/128 bits ), il n'y à qu'un seul accès à la mémoire. Si le programme demande de lire un double ( 8 octets aligné sur 32/64/128 bits ) il fait automatiquement 2 appel mémoire donc il y a deux utilisation du bus non pas 1 pour un float. Donc non le double n'est pas plus rapide qu'un float quand on parle de la mémoire.
Si le bus est de 64 bits (DDR, DDR2, or DDR3) alors c'est idem pour float et double... sauf! au cas ou tu lit 2 float contiguë en mémoire aligné... tu n'auras que une lecture de faite.

Ça va également dépendre de si tu compile en 32bits ou 64bits.

Tu auras une différence en fonction de ton matériel coté calcul sur float/double. Tout vas dépendre du FPU de ton processeur. Mais généralement aujourd'hui le float sera émulé en double et donc le float sera plus long que de travailler directement avec un double et encore... ici encore cela va dépendre de ton FPU ici aussi.

Donc:
Le float ne sera pas forcement toujours plus rapide qu'un double et inversement et ce avec le même code. Tout dépend de la machine...

Il faut toujours prendre un float car 4 octets car sera toujours lu en 1 seul accès mémoire peut importe ta machine ( tout du moins si elle à un bus de 32 bits minimum) sauf mettre double pour les cas ou MAX_FLOAT est insuffisant, mais l'algorithme sera donc plus lent car plus d'accès via le bus mémoire.

Pour le coté historique, la mémoire évolue beaucoup moins rapidement que le processeur donc si tu veux optimiser, 90% du temps tu le fais coté mémoire.

Voila pourquoi les librairies travaille en float et également les moteurs de jeu vidéo, et peuvent fournir une surcharge en double au besoin. Et coté précision, c'est très rare d'avoir besoin de plus que float.

[Jean-Marc.Bourguet]

Pour ce qui est d'un éventuel dépassement de la limite du type int, on est certain de calculer au plus 12! (N <= 500 000 000).

Si tu affiches p=12, tu as calcule 13! dans ton programme.

Quoi? un double est plus rapide qu'un float?

Ou ca? J'ai ecrit qu'il fallait mesurer en reponse a une affirmation qu'utiliser float etait bon pour les perfs, donc sous-entendant que float n'etait pas necessairement plus rapide que double, mais certainement pas que les doubles sont plus rapides que les float.

Un petit récap

Acces memoire:

1/ si on n'est pas en cache, inutile de parler de perf de calcul, c'est un probleme d'optimisation de bande passante (et j'ai explicitement dit que les cas ou la BP est un facteur limitant sont les cas ou il faut envisager float, apres avoir confirme que la precision est suffisante)
2/ tout les acces en lecture a la memoire principale transferent des lignes completes de cache
3/ si tes donnees ne sont pas alignees de sorte qu'elles sont completement dans une ligne de cache, a nouveau inutile de parler de perf de calcul
4/ si tes donnees sont completement dans la ligne de cache, leur taille n'a pas d'importance.

Sur l'aspect CPU (que dissocier qu'un FPU de nos jours n'a plus guere de sens). Les CPU etant pipeline, superscalaire, a execution dans le desordre, ils peuvent avoir plus d'une centaine d'instruction en cours d'execution. Le temps d'execution d'une instruction n'a plus de sens, il faut regarder un groupe et voir comment le processeur gere. Les interdependances ont de bonnes chances de masquer les differences entre float et double, sauf quand tout est concu pour (en gros les cas vectorisable, qu'on utilise ou non des instructions pour).

Le float ne sera pas forcement toujours plus rapide qu'un double et inversement et ce avec le même code. Tout dépend de la machine...

Et nous sommes d'accord sur la conclusion.

Il faut toujours prendre un float car 4 octets car sera toujours lu en 1 seul accès mémoire peut importe ta machine ( tout du moins si elle à un bus de 32 bits minimum) sauf mettre double pour les cas ou MAX_FLOAT est insuffisant, mais l'algorithme sera donc plus lent car plus d'accès via le bus mémoire.

Le probleme n'est pas souvent MAX_FLOAT, c'est le nombre de bits de la "mantisse" qui n'est que de 24 pour les floats. C'est 6 chiffres decimaux et bien souvent trop peu pour garder une precision suffisante quand on enchaine des calculs.

Voila pourquoi les librairies travaille en float et également les moteurs de jeu vidéo, et peuvent fournir une surcharge en double au besoin. Et coté précision, c'est très rare d'avoir besoin de plus que float.

Les librairies de calculs sont tres souvent disponibles en float, double, extended et parfois quad, celles en C++ sont souvent templatees.

Pour ce qui concerne les jeux videos, l'affichage a besoin de 13/14 bits de precision finale, que les 24 de float suffisent souvent ne m'etonnerait pas trop. Mais c'est un domaine atypique de ce point de vue, je reste sur ma position: double est le type flottant a utiliser par defaut

[Wachter]

Si tu affiches p=12, tu as calcule 13! dans ton programme.

Oups... Tu as raison. Même l'utilisation des long int ne résoudra pas le problème.

[Jean-Marc.Bourguet]

Oups... Tu as raison. Même l'utilisation des long int ne résoudra pas le problème.

long long, ou changer la condition en (fact < nb/(rang+1).