Ce que je veux dire, c'est que si vous avez deux doubles qui ont bien la même valeur (la même valeur au sens informatique du terme, avec les mêmes bits dans les mêmes octets), qui ont été calculés de l'exact même manière, alors le test d'égalité entre ces deux double renverra VRAI. Et encore heureux !
Non, mais le cas est déterministe (NaN est toujours différent de NaN) donc ça ne pose pas de problème en pratique.
Pour moi la digression sur les flottants (les doubles, mais c’est généralisable à tous les formats d’IEEE-754) est aussi intéressante que le bug du processeur, parce qu’elle montre qu’une « solution commune » (et appliquée dans ce cas précis si j’en crois des commentaires sur les autres publications qui en parlent) ne sont pas adaptées, à cause d’une incompréhension sur le fonctionnement de ces flottants et de la raison qui fait qu’on demande une comparaison à un epsilon au lieu d’une égalité directe.
Posté par Computer (site web personnel) .
Évalué à 1 (+5/-4).
Dernière modification le 21 août 2025 à 08:55.
La comparaison à un epsilon aurait simplement reporté son problème à un autre cas. En effet il pourrait tout simplement tomber sur un cas où les deux float à comparer sont à epsilon près et qu'une approximation fpu->proc. fasse basculer le test là encore.
C'est son algo. à la base qui est foireux : déjà utiliser un Set comme une structure totalement ordonnée c'est mathématiquement du grand n'importe quoi. Utiliser une fonction non injective pour construire la relation d'ordre est encore plus aberrant dans son cas. Mais la dernière fois que j'ai dit que les informaticiens faisaient n'importe quoi avec les maths je me suis fait moinser à mort :'(
Un moyen simple aurait été de sélectionner tous les points qui ont la déviation minimale en 1 seule passe. Le résultat diffère toujours d'une machine à l'autre, mais si ça plante toujours alors c'est son algo qui est pas bon. En effet en analyse numérique on admet une tolérance sur les calculs flottants et on apprend à être robuste là-dessus.
Oh, et déterministe ça ne veut pas dire « j'obtiens le même résultat partout tout le temps », ça veut dire : à conditions identiques j'obtiens le même résultat. Les conditions impliquent aussi la machine et le compilateur… Là il dit bien, que le comportement est parfaitement déterministe : en 32 bits ça plante tout le temps ! La encore en analyse numérique j'avais des résultats différents d'une machine à l'autre, par contre ils se devaient d'être consistant (c'est-à-dire conforme à un epsilon calculé près).
Je suis l'auteur de l'article, je me permets donc de répondre.
C'est son algo. à la base qui est foireux : déjà utiliser un Set comme une structure totalement ordonnée c'est mathématiquement du grand n'importe quoi.
C'est littéralement la définition d'un std::set en C++ : « std::set is an associative container that contains a sorted set of unique objects » (cf la doc)
Un std::set C++ est totalement ordonné. Si tu prétends le contraire il va quand même falloir ramener de bons arguments, et me sortir un programme de contre-exemple où itérer sur le set ne te donne pas une séquence ordonnée…
Utiliser une fonction non injective pour construire la relation d'ordre est encore plus aberrant dans son cas.
Je ne vois pas en quoi la fonction est non-injective ? Chaque éléments est trié par déviation, et par index dans le cas où la déviation est égale. Chaque point ayant par définition un index différent, chaque élément de l'ensemble d'arrivé a bien au plus un antécédent, ce qui me semble être la définition d'une fonction injective ?
Un moyen simple aurait été de sélectionner tous les points qui ont la déviation minimale en 1 seule passe.
Si tu as un algo de simplification de polyligne plus optimal, n'hésite pas à le publier. Je me suis basé sur une variante (certes très simplifiée) de l'algo de Visvalingam–Whyatt, qui a priori est relativement efficace (voir Wikipédia).
Le résultat diffère toujours d'une machine à l'autre, mais si ça plante toujours alors c'est son algo qui est pas bon.
Ça plante à cause d'un comportement inattendu dû à des optimisations du processeur, et ça ne plante plus quand on a compris cela et qu'on a désactivé les optimisations, désolé si l'article n'est pas clair à ce sujet. L'algo fonctionne très bien, ne pas hésiter à le faire à la main sur papier pour s'en convaincre.
En effet en analyse numérique on admet une tolérance sur les calculs flottants et on apprend à être robuste là-dessus.
Je ne comprends pas cette remarque. L'analyse numérique, c'est vaste, sans parler des applications, donc j'ai tendance à me méfier des "on" très généralistes. Les biblios de calculs exacts (MPFR, GMP) n'utilisent pas de tolérance, par exemple, mais des représentations avec une précision variable et améliorable dynamiquement.
Et en l'occurrence, je ne vois toujours pas en quoi l'utilisation d'une tolérance dans mon cas réglerait le problème : au risque de me répéter, c'était un problème d’optimisation, qui a été résolu en désactivant les optimisations. Tout marche très bien maintenant, c'est tout à fait robuste, ça a tourné sur un paquet de polylignes en fournissant le résultat attendu sans plantage.
Oh, et déterministe ça ne veut pas dire « j'obtiens le même résultat partout tout le temps », ça veut dire : à conditions identiques j'obtiens le même résultat.
OK OK, j'admets avoir sans doute été abusif dans le terme déterministe. Bon j'ai quand même pu observer un même test dire vrai puis faux au sein d'un même run du même programme compilé sur la même plateforme à deux lignes d'écart. Mais OK, oui, techniquement chaque ligne était déterministe, donc admettons.
Posté par Computer (site web personnel) .
Évalué à -3 (+0/-3).
Dernière modification le 23 août 2025 à 14:57.
Y'a plein de trucs qui me chiffonnent dans ce que tu racontes. Il y a un gros problème de conception dans la lib C++ qui parle de Set à tort. Il y en a aussi un chez toi qui détourne le Set de son usage attendu. Je vais pas me battre là-dessus. Juste utilise une vrai queue de priorité, en évaluant la deviation une bonne fois pour toute (et les voisins à chaque élimination). Parce que là en fait dans un contexte pro j'aurai pas cherché et retoqué le code. Là en plus ça me donne la désagréable sensation que tu fais recalculer la même déviation à plusieurs reprise.
Tu n'aurais plus eu besoin de faire le test a < b (c'est quoi en C++ ? des adresses mémoires ?)
PS : non les lib. ne font pas de la magie, un nombre irrationnel n'est pas représentable, donc il y aura toujours un ɛ dans un calcul avec des réels dans le cas général.
Posté par Computer (site web personnel) .
Évalué à -2 (+0/-2).
Dernière modification le 24 août 2025 à 12:44.
Ouais –2 pour avoir signalé que l'implémentation n'est pas conforme à l'algorithme donné dans wikipédia… histoire d'aider à résoudre proprement le bug et sans perte de performance (en réalité un problème de double test de l'ordre strict — qui n'en ai en fait pas un dans l'implémentation donc — selon les éléments qui nous sont fournis, même si ça demanderait plus d'investigation pour confirmer).
Ça donne envie d'aider.
Au passage j'avais eu à pondre un tel algo en dim 2 (optimisation d'une surface dans l'espace). Une bonne fonction score c'est la courbure, généralisation de la dérivée seconde ; un poil plus complexe car il faut récupérer des valeurs et vecteurs propres ensuite. C'est ptet d'ailleurs très proche de l'algo de ton lien en 1d, faudrait plonger dans les calculs. Flemme. Mais ça marchait bien sans aucune itération (juste une valeur seuil, on peut aussi jouer sur un quantile). À bon entendeur…
# Ahem
Posté par Benoît Sibaud (site web personnel) . Évalué à 7 (+4/-0).
tousse tousse https://gcc.gnu.org/bugzilla/show_bug.cgi?id=18567 (et coucou Laurent Guerby https://gcc.gnu.org/bugzilla/show_bug.cgi?id=15134 )
Donc je dirais bien sans commentaire.
[^] # Re: Ahem
Posté par Benoît Sibaud (site web personnel) . Évalué à 3 (+0/-0).
D'ailleurs en fait et précédemment https://linuxfr.org/users/oumph/liens/the-bug-323-community-where-all-x87-floating-point-errors-in-gcc-come-to-die
[^] # Re: Ahem
Posté par SpaceFox (site web personnel, Mastodon) . Évalué à 2 (+0/-0).
D’ailleurs ce commentaire https://linuxfr.org/users/oumph/liens/the-bug-323-community-where-all-x87-floating-point-errors-in-gcc-come-to-die#comment-1933009 contient bien le lien, mais la recherche a été infoutue de me le trouver -_-
La connaissance libre : https://zestedesavoir.com
# Ahem
Posté par Pol' uX (site web personnel) . Évalué à 4 (+2/-0).
Même si la valeur du double est NaN ? :)
Adhérer à l'April, ça vous tente ?
[^] # Re: Ahem
Posté par SpaceFox (site web personnel, Mastodon) . Évalué à 5 (+3/-0).
Non, mais le cas est déterministe (NaN est toujours différent de NaN) donc ça ne pose pas de problème en pratique.
Pour moi la digression sur les flottants (les doubles, mais c’est généralisable à tous les formats d’IEEE-754) est aussi intéressante que le bug du processeur, parce qu’elle montre qu’une « solution commune » (et appliquée dans ce cas précis si j’en crois des commentaires sur les autres publications qui en parlent) ne sont pas adaptées, à cause d’une incompréhension sur le fonctionnement de ces flottants et de la raison qui fait qu’on demande une comparaison à un epsilon au lieu d’une égalité directe.
La connaissance libre : https://zestedesavoir.com
[^] # Re: Ahem
Posté par Computer (site web personnel) . Évalué à 1 (+5/-4). Dernière modification le 21 août 2025 à 08:55.
La comparaison à un epsilon aurait simplement reporté son problème à un autre cas. En effet il pourrait tout simplement tomber sur un cas où les deux float à comparer sont à epsilon près et qu'une approximation fpu->proc. fasse basculer le test là encore.
C'est son algo. à la base qui est foireux : déjà utiliser un Set comme une structure totalement ordonnée c'est mathématiquement du grand n'importe quoi. Utiliser une fonction non injective pour construire la relation d'ordre est encore plus aberrant dans son cas. Mais la dernière fois que j'ai dit que les informaticiens faisaient n'importe quoi avec les maths je me suis fait moinser à mort :'(
Un moyen simple aurait été de sélectionner tous les points qui ont la déviation minimale en 1 seule passe. Le résultat diffère toujours d'une machine à l'autre, mais si ça plante toujours alors c'est son algo qui est pas bon. En effet en analyse numérique on admet une tolérance sur les calculs flottants et on apprend à être robuste là-dessus.
Oh, et déterministe ça ne veut pas dire « j'obtiens le même résultat partout tout le temps », ça veut dire : à conditions identiques j'obtiens le même résultat. Les conditions impliquent aussi la machine et le compilateur… Là il dit bien, que le comportement est parfaitement déterministe : en 32 bits ça plante tout le temps ! La encore en analyse numérique j'avais des résultats différents d'une machine à l'autre, par contre ils se devaient d'être consistant (c'est-à-dire conforme à un epsilon calculé près).
[^] # Re: Ahem
Posté par gee . Évalué à 10 (+11/-1).
Hello,
Je suis l'auteur de l'article, je me permets donc de répondre.
C'est littéralement la définition d'un
std::seten C++ : « std::set is an associative container that contains a sorted set of unique objects » (cf la doc)Un
std::setC++ est totalement ordonné. Si tu prétends le contraire il va quand même falloir ramener de bons arguments, et me sortir un programme de contre-exemple où itérer sur le set ne te donne pas une séquence ordonnée…Je ne vois pas en quoi la fonction est non-injective ? Chaque éléments est trié par déviation, et par index dans le cas où la déviation est égale. Chaque point ayant par définition un index différent, chaque élément de l'ensemble d'arrivé a bien au plus un antécédent, ce qui me semble être la définition d'une fonction injective ?
Si tu as un algo de simplification de polyligne plus optimal, n'hésite pas à le publier. Je me suis basé sur une variante (certes très simplifiée) de l'algo de Visvalingam–Whyatt, qui a priori est relativement efficace (voir Wikipédia).
Ça plante à cause d'un comportement inattendu dû à des optimisations du processeur, et ça ne plante plus quand on a compris cela et qu'on a désactivé les optimisations, désolé si l'article n'est pas clair à ce sujet. L'algo fonctionne très bien, ne pas hésiter à le faire à la main sur papier pour s'en convaincre.
Je ne comprends pas cette remarque. L'analyse numérique, c'est vaste, sans parler des applications, donc j'ai tendance à me méfier des "on" très généralistes. Les biblios de calculs exacts (MPFR, GMP) n'utilisent pas de tolérance, par exemple, mais des représentations avec une précision variable et améliorable dynamiquement.
Et en l'occurrence, je ne vois toujours pas en quoi l'utilisation d'une tolérance dans mon cas réglerait le problème : au risque de me répéter, c'était un problème d’optimisation, qui a été résolu en désactivant les optimisations. Tout marche très bien maintenant, c'est tout à fait robuste, ça a tourné sur un paquet de polylignes en fournissant le résultat attendu sans plantage.
OK OK, j'admets avoir sans doute été abusif dans le terme déterministe. Bon j'ai quand même pu observer un même test dire vrai puis faux au sein d'un même run du même programme compilé sur la même plateforme à deux lignes d'écart. Mais OK, oui, techniquement chaque ligne était déterministe, donc admettons.
[^] # Re: Ahem
Posté par Computer (site web personnel) . Évalué à -3 (+0/-3). Dernière modification le 23 août 2025 à 14:57.
Y'a plein de trucs qui me chiffonnent dans ce que tu racontes. Il y a un gros problème de conception dans la lib C++ qui parle de Set à tort. Il y en a aussi un chez toi qui détourne le Set de son usage attendu. Je vais pas me battre là-dessus. Juste utilise une vrai queue de priorité, en évaluant la deviation une bonne fois pour toute (et les voisins à chaque élimination). Parce que là en fait dans un contexte pro j'aurai pas cherché et retoqué le code. Là en plus ça me donne la désagréable sensation que tu fais recalculer la même déviation à plusieurs reprise.
Tu n'aurais plus eu besoin de faire le test a < b (c'est quoi en C++ ? des adresses mémoires ?)
PS : non les lib. ne font pas de la magie, un nombre irrationnel n'est pas représentable, donc il y aura toujours un ɛ dans un calcul avec des réels dans le cas général.
[^] # Re: Ahem
Posté par Computer (site web personnel) . Évalué à -2 (+0/-2). Dernière modification le 24 août 2025 à 12:44.
Ouais –2 pour avoir signalé que l'implémentation n'est pas conforme à l'algorithme donné dans wikipédia… histoire d'aider à résoudre proprement le bug et sans perte de performance (en réalité un problème de double test de l'ordre strict — qui n'en ai en fait pas un dans l'implémentation donc — selon les éléments qui nous sont fournis, même si ça demanderait plus d'investigation pour confirmer).
Ça donne envie d'aider.
Au passage j'avais eu à pondre un tel algo en dim 2 (optimisation d'une surface dans l'espace). Une bonne fonction score c'est la courbure, généralisation de la dérivée seconde ; un poil plus complexe car il faut récupérer des valeurs et vecteurs propres ensuite. C'est ptet d'ailleurs très proche de l'algo de ton lien en 1d, faudrait plonger dans les calculs. Flemme. Mais ça marchait bien sans aucune itération (juste une valeur seuil, on peut aussi jouer sur un quantile). À bon entendeur…
Envoyer un commentaire
Suivre le flux des commentaires
Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.