Multiplication, comparaison et débordement

Le
Lucas Levrel
Bonjour,

Je dois comparer le produit de plusieurs int à une constante (dans une
macro). Typiquement :

#define LIMITE 512*1024*1024
int a,b,c;

if(a*b*c<LIMITE)

Comment faire ça proprement si LIMITE et le produit sont supérieurs à
INT_MAX ? Notamment :
- quel type pour LIMITE ;
- comment écririez-vous la comparaison ?

Le but étant la lisibilité et la portabilité, pas la performance.

Pour LIMITE je suppose qu'il faut opter pour long long int, parce qu'avec
unsigned int je vais buter sur 4 gigas. Mais je pourrais aussi utiliser
un flottant s'il est plus portable (une petite erreur d'arrondi n'est pas
grave dans mon contexte).

Merci.
--
LL
Vidéos High-Tech et Jeu Vidéo
Téléchargements
Vos réponses Page 1 / 2
Gagnez chaque mois un abonnement Premium avec GNT : Inscrivez-vous !
Trier par : date / pertinence
JKB
Le #22598481
Le Wed, 22 Sep 2010 15:00:41 +0200,
Lucas Levrel
Bonjour,



Bonjour,

Je dois comparer le produit de plusieurs int à une constante (dans une
macro). Typiquement :

#define LIMITE 512*1024*1024
int a,b,c;
...
if(a*b*c<LIMITE) ...

Comment faire ça proprement si LIMITE et le produit sont supérieurs à
INT_MAX ? Notamment :
- quel type pour LIMITE ;
- comment écririez-vous la comparaison ?

Le but étant la lisibilité et la portabilité, pas la performance.

Pour LIMITE je suppose qu'il faut opter pour long long int, parce qu'avec
unsigned int je vais buter sur 4 gigas. Mais je pourrais aussi utiliser
un flottant s'il est plus portable (une petite erreur d'arrondi n'est pas
grave dans mon contexte).



Justement, ça dépend du contexte et des valeurs a, b, et c. On peut
tout imaginer jusqu'à :

#define LIMITE ((log(512) + log(1024) + log(1024))

if ((log(a) + log(b) + log(c)) < LIMITE)
{
...
}

Bon, on suppose que a, b, et c sont strictement positifs. On peut
ajouter des valeurs absolues s'il le faut.

On peut aussi imaginer (a * b < LIMITE / c) en fonction des valeurs
relatives de a, b et c.

Il faut donc nous en dire plus sur a, b et c.

JKB

--
Si votre demande me parvient sur carte perforée, je titiouaillerai très
volontiers une réponse...
=> http://grincheux.de-charybde-en-scylla.fr
Marc Boyer
Le #22598471
Le 22-09-2010, Lucas Levrel
Bonjour,

Je dois comparer le produit de plusieurs int à une constante (dans une
macro). Typiquement :

#define LIMITE 512*1024*1024
int a,b,c;
...
if(a*b*c<LIMITE) ...

Comment faire ça proprement si LIMITE et le produit sont supérieurs à
INT_MAX ? Notamment :
- quel type pour LIMITE ;
- comment écririez-vous la comparaison ?



Si on est obligé d'écrire le test
if(a*b*c<LIMITE)
on peut pas faire grand chose (à par prier pour que long long int
soit suffisant).

Sinon, le log me semble plutôt une bonne idée.

Marc Boyer
--
En prenant aux 10% des francais les plus riches 12% de leurs revenus,
on pourrait doubler les revenus des 10% les plus pauvres.
http://www.inegalites.fr/spip.php?article1&id_mot0
Marc
Le #22598591
JKB wrote:

#define LIMITE ((log(512) + log(1024) + log(1024))

if ((log(a) + log(b) + log(c)) < LIMITE)



Cela apporte-t-il vraiment quelque chose comparé à :

#define LIMITE (512. * 1024 * 1024)
if ((double(a) * b * c) < LIMITE)

?

On peut aussi imaginer (a * b < LIMITE / c) en fonction des valeurs
relatives de a, b et c.



oui, remplacer la multiplication par une division est une des méthodes
usuelles dans certains contextes.
Antoine Leca
Le #22598581
Lucas Levrel écrivit :
#define LIMITE 512*1024*1024
int a,b,c;
...
if(a*b*c<LIMITE) ...

Comment faire ça proprement si LIMITE et le produit sont supérieurs à
INT_MAX ? Notamment :
- quel type pour LIMITE ;



Le même que celui que donne au final la multiplication

[...] je suppose qu'il faut opter pour long long int, parce
qu'avec unsigned int je vais buter sur 4 gigas.



Bzzz ! En fait officiellement tu vas buter sur 65535.
Pour avoir une limite garantie à 4 milliards [histoire de ne pas parler
jargon], il faudrait transtyper en unsigned long ; et tant qu'à faire,
si tu es sûr d'avoir une implémentation C99, tu passeras effectivement à
long long, pour une limite garantie à 8 trillions.

Savoir si cela suffit, ou pas, est ton problème ; si cela peut ne pas
suffire (genre, tu ne sais absolument rien de a,b,c _et_ ta machine
cible pour avoir des int sur 64 bits ou plus), la solution des flottants
est effectivement plus bétonné. De plus c'est conforme C90.

Et comme le fait remarquer JKB, attention aux nombres négatifs (le fait
d'utiliser des types non signés ne calcule pas les valeurs absolues !)


Antoine
Lucas Levrel
Le #22598621
Le 22 septembre 2010, JKB a écrit :

Bon, on suppose que a, b, et c sont strictement positifs.



Ah oui, j'ai oublié de le préciser (je voulais le faire mais ça a fait
pschit).

On peut aussi imaginer (a * b < LIMITE / c) en fonction des valeurs
relatives de a, b et c.

Il faut donc nous en dire plus sur a, b et c.



Effectivement, je n'avais pas pensé à cette division ! Justement,
c=sizeof(truc), ça paraît même logique de le mettre du même côté que
la constante LIMITE.

Actuellement, a00, b=2^16, c$. Dans ce cas de figure, avec LIMITE un
multiple de 2^(20 au moins), évidemment a*c<LIMITE/b donne un résultat
exact.

Il me reste une question : est-ce que tout compilateur va calculer
la constante 4*1024*1024*1024/65536 sans débordement ?

--
LL
Lucas Levrel
Le #22598671
Le 22 septembre 2010, Antoine Leca a écrit :

[...] je suppose qu'il faut opter pour long long int, parce
qu'avec unsigned int je vais buter sur 4 gigas.



Bzzz ! En fait officiellement tu vas buter sur 65535.
Pour avoir une limite garantie à 4 milliards [histoire de ne pas parler
jargon], il faudrait transtyper en unsigned long ; et tant qu'à faire,
si tu es sûr d'avoir une implémentation C99, tu passeras effectivement à
long long, pour une limite garantie à 8 trillions.



OK, je n'arrive jamais à mémoriser les intervalles « garantis » par chaque
type. J'ai juste constaté sur les intel 64 bits où je travaille que les
int sont 32 bits.

Y a-t-il des compilos récents sous Unix qui n'implémentent pas C99 ?

la solution des flottants
est effectivement plus bétonné. De plus c'est conforme C90.



Merci.

--
LL
Marc
Le #22598811
Lucas Levrel wrote:

Y a-t-il des compilos récents sous Unix qui n'implémentent pas C99 ?



Euh, oui, gcc par exemple.
Des qui n'ont pas long long, c'est plus dur à trouver...
Marc
Le #22598801
Lucas Levrel wrote:

Il me reste une question : est-ce que tout compilateur va calculer
la constante 4*1024*1024*1024/65536 sans débordement ?



gcc calcule 0 et affiche un warning.
Antoine Leca
Le #22599071
Lucas Levrel écrivit :
Y a-t-il des compilos récents sous Unix qui n'implémentent pas C99 ?



Si le compilo est vraiment récent, genre, conçu depuis 5 ans ou moins
(exemple : clang), et qu'en plus il cible UNIX (ou plus généralement des
stations de travail, des serveurs ou des ordinateurs de bureau), je
pense que cela va être difficile qu'il ne vise pas C99 ; et plus
difficile encore qu'il n'implémente pas long long...

Cela étant, les compilos récents sont l'exception : GCC date de 1988,
MSC de 1987 (dernière grosse refonte en 1993), etc. :^)

Par ailleurs, la norme Posix de 2001 demand(ait) la conformité C99.
Donc si tu vises une machine *nix moderne, tu es censé être tranquille.
Maintenant, deuxième douche froide, il faut voir que des projets comme
NetBSD ou OpenBSD (pour prendre deux exemples parlants) ne cherchent
même pas à y être conformes (cela ne veut pas dire qu'il font exprès
autre chose, seulement que la conformité est tellement complexe qu'ils
n'ont pas les moyens d'y arriver.)


Si la question est, peut-on rencontrer, sur une machine Posix, un
compilateur sans long long, la réponse est en fait oui... surtout si tu
sors un tant soit peu des cibles super-connues (genre Linux-ou-Solaris)

Trois exemples au hasard :
- le compilateur lcc de Fraser et Hanson, parfois utilisé pour des
petits systèmes embarqués, n'est pas conforme C99
- le compilateur C de Microsoft, et cela inclut le sous-système Unix de
Windows (SFU/Interix), n'avait pas de long long avant 2003
- MINIX 3, un système genre Posix (mais :1990) qui est censé
fonctionner en embarqué et est actuellement développé, utilise en
standard le compilateur ACK, qui n'a pas de type entier 64 bits

Par ailleurs, pour les cibles genre embarqué avec des UAL 8 ou 16 bits,
le support d'un type 64 bits comme long long est très loin de leurs
priorités... même si sur d'autres aspects, ils peuvent s'intéresser
beaucoup à C99.

Bon c'est vrai que tout cela, ce sont des systèmes pas usuels ; mais
cela montre aussi qu'il y a toujours des communautés de développeurs
avec des préoccupations différentes du monde des stations de travail Linux.


Antoine
JKB
Le #22599141
Le Wed, 22 Sep 2010 18:48:18 +0200,
Antoine Leca
Lucas Levrel écrivit :
Y a-t-il des compilos récents sous Unix qui n'implémentent pas C99 ?



Si le compilo est vraiment récent, genre, conçu depuis 5 ans ou moins
(exemple : clang), et qu'en plus il cible UNIX (ou plus généralement des
stations de travail, des serveurs ou des ordinateurs de bureau), je
pense que cela va être difficile qu'il ne vise pas C99 ; et plus
difficile encore qu'il n'implémente pas long long...

Cela étant, les compilos récents sont l'exception : GCC date de 1988,
MSC de 1987 (dernière grosse refonte en 1993), etc. :^)

Par ailleurs, la norme Posix de 2001 demand(ait) la conformité C99.
Donc si tu vises une machine *nix moderne, tu es censé être tranquille.
Maintenant, deuxième douche froide, il faut voir que des projets comme
NetBSD ou OpenBSD (pour prendre deux exemples parlants) ne cherchent
même pas à y être conformes (cela ne veut pas dire qu'il font exprès
autre chose, seulement que la conformité est tellement complexe qu'ils
n'ont pas les moyens d'y arriver.)



Encore que NetBSD, FreeBSD et Linux sont beaucoup plus conformes que
OpenBSD, surtout lorsqu'on parle de conformité Posix 2001. Et il y a
des systèmes prétendûment Posix (comme MacOS X ou Solaris) qui ne le
sont pas plus qu'un Linux brut de fonderie.

Si la question est, peut-on rencontrer, sur une machine Posix, un
compilateur sans long long, la réponse est en fait oui... surtout si tu
sors un tant soit peu des cibles super-connues (genre Linux-ou-Solaris)

Trois exemples au hasard :
- le compilateur lcc de Fraser et Hanson, parfois utilisé pour des
petits systèmes embarqués, n'est pas conforme C99
- le compilateur C de Microsoft, et cela inclut le sous-système Unix de
Windows (SFU/Interix), n'avait pas de long long avant 2003



Franchement, si c'était le seul problème d'Interix en terme de
conformité, ce serait un moindre mal...

- MINIX 3, un système genre Posix (mais :1990) qui est censé
fonctionner en embarqué et est actuellement développé, utilise en
standard le compilateur ACK, qui n'a pas de type entier 64 bits

Par ailleurs, pour les cibles genre embarqué avec des UAL 8 ou 16 bits,
le support d'un type 64 bits comme long long est très loin de leurs
priorités... même si sur d'autres aspects, ils peuvent s'intéresser
beaucoup à C99.

Bon c'est vrai que tout cela, ce sont des systèmes pas usuels ; mais
cela montre aussi qu'il y a toujours des communautés de développeurs
avec des préoccupations différentes du monde des stations de travail Linux.



Si déjà les développeurs pouvaient être conforme à Posix quelque
chose ou SysV, plutôt que d'être conforme Linux ou FreeBSD sur x86, ce
serait vraiment bien. Certains jours, je rêve de ça...

JKB

--
Si votre demande me parvient sur carte perforée, je titiouaillerai très
volontiers une réponse...
=> http://grincheux.de-charybde-en-scylla.fr
Publicité
Poster une réponse
Anonyme