 |
C++Talk.NET
C++ language newsgroups
|
| View previous topic :: View next topic |
| Author |
Message |
Dudule
Guest
|
 Posted: Tue May 17, 2005 10:29 pm Post subject: Comment savoir si on atteint le MAX d'un type ? |
 |
|
Hello,
Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci.
Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du
type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1)
était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en
rebouclant;
Il y a une méthode ? Merci.
|
|
| Back to top |
|
 |
Pierre Maurette
Guest
|
| Posted: Tue May 17, 2005 11:39 pm Post subject: Re: Comment savoir si on atteint le MAX d'un type ? |
|
|
Dudule, le 18/05/2005, a écrit :
| Quote: | Hello,
Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci.
Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du
type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1)
était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en
rebouclant;
Il y a une méthode ? Merci.
Vous testez : |
LONG_MAX - f(N) >= f(N-1)
avant chaque
f(N+1) = f(N) + f(N-1)
Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long.
Tout ça défini dans <climits>.
Pour le reste de votre raisonnement, ce qui me gêne c'est que vous
parlez d'un long (donc signed). Pour des unsigned long, il est valable.
La norme garantit que si le résultat est plus grand que ULONG_MAX,
alors le résultat renvoyé est le résultat exact modulo ULONG_MAX + 1. A
ce moment là, f(N-1) < f(N) < ULONG_MAX (inégalités strictes) fournit
la preuve que (f(N-1) + f(N))%(ULONG_MAX+1) < f(N) si et seulement si
il y a eu dépassement.
Pour des long, je pense qu'il y a comportement indéfini. Néanmoins,
pour des entiers naturels en complément à 2 se comportant civilement,
le résultat sera négatif si et seulement si on a dépassé.
Tout ceci n'est valable que si on le fait à chaque opération.
--
Pierre
|
|
| Back to top |
|
|
Pierre Maurette
Guest
|
| Posted: Tue May 17, 2005 11:39 pm Post subject: Re: Comment savoir si on atteint le MAX d'un type ? |
|
|
Dudule, le 18/05/2005, a écrit :
| Quote: | Hello,
Toujours dans le cadre d'un exercice, je suis sur les suites de Fibonacci.
Et j'aimerais savoir au bout de combien de termes j'atteins le maximum du
type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si f(N+1)
était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en
rebouclant;
Il y a une méthode ? Merci.
Vous testez : |
LONG_MAX - f(N) >= f(N-1)
avant chaque
f(N+1) = f(N) + f(N-1)
Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long.
Tout ça défini dans <climits>.
Pour le reste de votre raisonnement, ce qui me gêne c'est que vous
parlez d'un long (donc signed). Pour des unsigned long, il est valable.
La norme garantit que si le résultat est plus grand que ULONG_MAX,
alors le résultat renvoyé est le résultat exact modulo ULONG_MAX + 1. A
ce moment là, f(N-1) < f(N) < ULONG_MAX (inégalités strictes) fournit
la preuve que (f(N-1) + f(N))%(ULONG_MAX+1) < f(N) si et seulement si
il y a eu dépassement.
Pour des long, je pense qu'il y a comportement indéfini. Néanmoins,
pour des entiers naturels en complément à 2 se comportant civilement,
le résultat sera négatif si et seulement si on a dépassé.
Tout ceci n'est valable que si on le fait à chaque opération.
--
Pierre
|
|
| Back to top |
|
|
Jean-Marc Bourguet
Guest
|
| Posted: Wed May 18, 2005 12:05 pm Post subject: Re: Comment savoir si on atteint le MAX d'un type ? |
|
|
Dudule <nospam_svdbg_nospam (AT) free (DOT) fr> writes:
| Quote: | Au départ, je me suis dit que vu que la suite était croissante, si f(N+1)
était inférieur f(N), alors on avait rebouclé. Mais àa ne suffit pas.
|
Loin de la. Si tu utilises un type signe, le comportement devient
indefini, il n'est pas garanti que ca va boucler (mais c'est bien ce
qui se passe sur la plupart des machines).
| Quote: | Il y a une méthode ? Merci.
|
Tester avant l'addition. Genre
if (std::numeric_limits<long>::max() - f1 < f2) {
traite le depassement
} else {
long tmp = f2;
f2 = f1;
f1 += tmp;
}
A+
--
Jean-Marc
FAQ de fclc++: http://www.cmla.ens-cachan.fr/~dosreis/C++/FAQ
C++ FAQ Lite en VF: http://www.ifrance.com/jlecomte/c++/c++-faq-lite/index.html
Site de usenet-fr: http://www.usenet-fr.news.eu.org
|
|
| Back to top |
|
|
Dudule
Guest
|
| Posted: Thu May 19, 2005 9:50 pm Post subject: Re: Comment savoir si on atteint le MAX d'un type ? |
|
|
Pierre Maurette wrote:
| Quote: | Vous testez :
LONG_MAX - f(N) >= f(N-1)
avant chaque
f(N+1) = f(N) + f(N-1)
Remplacer éventuellement LONG_MAX par ULONG_MAX avec des unsigned long.
Tout ça défini dans <climits>.
|
Merci !
| Quote: | Pour le reste de votre raisonnement, ce qui me gêne c'est que vous
parlez d'un long (donc signed). Pour des unsigned long, il est valable.
|
Je parlais effectivement d'un unsigned long.
|
|
| Back to top |
|
|
Dudule
Guest
|
| Posted: Thu May 19, 2005 9:50 pm Post subject: Re: Comment savoir si on atteint le MAX d'un type ? |
|
|
Jean-Marc Bourguet wrote:
| Quote: | Il y a une méthode ? Merci.
Tester avant l'addition. Genre
|
Merci !
|
|
| Back to top |
|
|
Patrick 'Zener' Brunet
Guest
|
| Posted: Thu May 19, 2005 10:06 pm Post subject: Re: Comment savoir si on atteint le MAX d'un type ? |
|
|
Bonjour.
Je réponds à Dudule <nospam_svdbg_nospam (AT) free (DOT) fr> qui a écrit :
| Quote: | Hello,
Toujours dans le cadre d'un exercice, je suis sur les suites de
Fibonacci. Et j'aimerais savoir au bout de combien de termes
j'atteins le maximum du type utilisé (en l'occurence, un long).
Au départ, je me suis dit que vu que la suite était croissante, si
f(N+1) était inférieur f(N), alors on avait rebouclé. Mais àa ne
suffit pas.
Si mon type va de 0 à 10, on peut très bien passer de 8 à 6, tout en
rebouclant;
Il y a une méthode ? Merci.
|
Pour une suite croissante, le critère à évaluer est la différence entre le
prochain accroissement et la réserve de capacité du type.
Si la réserve est calculable par soustraction à partir de la constante
adéquate de limits.h, par contre pour le prochain accroissement, soit on en
dispose, soit il faut calculer la prochaine valeur et de soustraire la
valeur courante : on déborde en faisant le test (à moins de le faire dans un
autre type de capacité suffisante).
Puisque vous travaillez sur une suite pour laquelle la formule de récurrence
s'écrit explicitement f(n+1) = f(n) + f(n-1), vous disposez déjà du prochain
accroissement avec f(n-1). Par contre avec une factorielle par exemple, ce
serait plus difficile.
Donc AMHA, c'est faisable avec une telle suite, mais avec d'autres ça reste
un problème transcendant au codage, donc relevant de l'intelligence du
concepteur du code, non transférable.
Cordialement,
A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
--
/***************************************
* Patrick BRUNET
* E-mail: lien sur http://zener131.free.fr/ContactMe
***************************************/
|
|
| Back to top |
|
|
Dudule
Guest
|
| Posted: Thu May 19, 2005 10:20 pm Post subject: Re: Comment savoir si on atteint le MAX d'un type ? |
|
|
Patrick 'Zener' Brunet wrote:
| Quote: | Donc AMHA, c'est faisable avec une telle suite, mais avec d'autres ça
reste un problème transcendant au codage, donc relevant de l'intelligence
du concepteur du code, non transférable.
|
C'est effectivement la conclusion à laquelle je suis finalement arrivé.
Merci pour l"exposé. :-)
| Quote: | A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
|
Cela ne relève en fait d'aucun langage particulier...
Désolé :-(
|
|
| Back to top |
|
|
Dudule
Guest
|
| Posted: Thu May 19, 2005 10:21 pm Post subject: Re: Comment savoir si on atteint le MAX d'un type ? |
|
|
Dudule wrote:
| Quote: | A part ça, ceci ne relève pas trop du langage C++, de C tout au plus.
Cela ne relève en fait d'aucun langage particulier...
Désolé 
|
Quoique si.
Quand j'ai posé la question, j'ai pensé qu'il pouvait exister une
classe/fonction du C++ standart qui aurait pu faire le boulot pour moi. :-)
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in to check your private messages
Log in
