snowball a écrit 168 commentaires

Sans blague !
Pourquoi penses-tu que j'ai écrit cet exemple ? Pour montrer que les tests d'égalité sur les flottants étaient intelligents ou bien pour montrer que même en utilisant des "décimaux" tout gentils en apparence on peut avoir de graves surprises si l'on méconnaît l'arithmétique flottante ?

Tu veux une calculatrice ne possédant que les touches +, - et * uniquement sur des décimaux de toute petite taille.

Tu ne veux pas qu'on puisse diviser (sinon on est bien d'accord que ça ne pourra jamais faire ce que tu veux, j'espère que tu l'as compris). Avec ça tu ne peux même pas programmer la moindre résolution de problème de niveau supérieur au CE2.

Rends toi compte de l'absurdité totale de ce que tu racontes s'il te plaît. Ne le fais pas pour nous, mais juste pour toi.

Donc tu veux juste faire des additions et multiplications sur quelques décimaux pas trop grands. Car on est bien d'accord que tu ne pourras rien faire d'autre (pas de division, encore moins de racines carrées etc). C'est ça que tu veux faire ?

Dans ce cas là, tu as plein de langages qui font ça très bien (Ada par exemple). Mais tu ne pourras quasiment rien faire sorti de +, - et * (pour des tout petits nombres) Genre même partager une somme d'argent en trois, en sept, en 9 etc, tu pourras pas… Très utile… Je doute que ça ait un quelconque intérêt au niveau informatique, sauf pour essayer de s'en sortir sur un forum où tu as refusé de comprendre de multiples intervenants qui t'on dit pourtant plein de choses intéressantes.

Tu confonds la taille de la représentation en machine avec la précision.
Si tu veux parler de maths et d'info, il te faut connaître les maths.

L'opération 3.0 * (5.0 / 3.0) ne concerne que des décimaux et elle donne le décimal 5.0 en math. Pourtant elle se vautre avec le module decimal de python. CQFD. J'ai essayé d'être patient, ça ne sert à rien. Parle à toi même, convaincs toi, toi même de tes bêtises si ça te chante.
Bonne soirée.

I love Ada ;)

Par contre, comme ce type ne peut gérer correctement que l'addition et la multiplication si tu fais

with Ada.Text_io; use Ada.Text_Io;

procedure Test_Real is
   type mon_real is delta 0.1 digits 3 range 0.0..10.0;

begin
   Put_line (mon_real'Image(3.0*(5.0/3.0)));
end Test_Real;

Au lieu de te sortir 5.0, il te sort 4.8 :)
Ada n'échappe malheureusement pas à la dure loi des math: les décimaux ne forment qu'un anneau et pas un corps (cf https://fr.wikipedia.org/wiki/Corps_(math%C3%A9matiques) et https://fr.wikipedia.org/wiki/Anneau_unitaire )

Je ne parle pas de réels, mais de décimaux.

Un décimal est un réel.

Je ne parle pas de précision infinie, mais bien de 1.8 et 0.2

Bah si tu n'autorises pas d'intervalle d'incertitude c'est bien que tu souhaites représenter EXACTEMENT 1.8 en machine donc que tu veux une précision infinie. Ton problème c'est que tu veux parler d'un sujet mathématique, mais que tu n'as pas les bases.

Par exemple Python propose Decimal qui est très bien,

Demande à ce module de te calculer 3.0 * (5.0 /3.0)
On est d'accord que ce ne sont que des décimaux comme tu le veux hein ?
On est d'accord que le résultat est évidemment 5.0 normalement hein ?
Bah devine quoi ! Il se vautre ton module python. Et c'est normal pour les raisons qu'on t'a déjà expliquées 30 fois.
La preuve en image:

>>> Decimal (3.0)* (Decimal (5.0)/ Decimal (3.0))
Decimal('5.000000000000000000000000001')

Tu me dis que la science DEMONTRE qu'on ne peut pas faire mieux, et pourtant les 3/4 des commentaires me disent qu'il me suffit d'utiliser des bibliothèques dédiées.

Les 3/4 des commentaires disent exactement ce que je dis mais tu ne les comprends visiblement pas. Les bibliothèques dédiées servent (avec une énorme lourdeur) à représenter des rationnels jusqu'à une précision liée aux capacités de la machine. Si ton téléphone devait calculer rien que ta géolocalisation avec ça, il n'aurait plus de batterie en 30mn ! En plus ça ne servirait à rien de géolocaliser au micron près sachant que ça provient d'une mesure à 10m près.

De toute façon, il n'existe aucun système qui fasse ce que tu attends car on démontre que ça ne peut pas exister sur des machines de Turing (sauf pour gérer de "petits" nombres avec une usine à gaz) et comme en plus l'ensemble des décimaux n'est pas stable par la division, ça se vautrerait en terme d'affichage au premier quotient pas sympa.

Y a un moment où il faut respirer, écouter, apprendre et se taire, rien que par respect pour ta propre personne. On dirait que tu ne veux rien de tout ça, c'est dommage pour toi.

@gUI

Non bc fait aussi mal: la preuve il dit que 3*(5/3) = 4.999999999999
Autrement dit il fait les mêmes bêtises que python (juste qu'il ne fait pas pour les mêmes nombres que Python).

Je t'ai expliqué que la science DEMONTRE (c'est assez simple en plus) qu'on ne peut pas faire mieux que ce qu'on fait en terme de représentation des réels en machine et que, quelque soit le choix que tu fasses, tu te retrouveras avec des problèmes du même type. Tu lis ou tu lis pas les commentaires ?

C'est pas demander la Lune quand même, si ?

La Lune c'est possible on y est allés.

Mais ce que tu demandes (calcul exact chez les réels ou même chez les rationnels) c'est pas possible et on le démontre que c'est pas possible.
On peut te créer des illusions (du genre travailler en système BCD) pour que les décimaux s'affichent la plupart du temps correctement, pas plus.
mais dès que tu demanderas: 3*(5/3) il y a fort à parier que tu n'obtiennes pas 5 et si ça marche pour ça, pour d'autres calculs ça marchera pas.
Par exemple, en bc, 3*(5/3) ne donne pas 5.

Attention 20172017, c'est déjà une opération.

Tu peux l'écrire, ça devient une opération quand tu appuies sur exe. Attention j'ai écrit et non .

Je parlais juste des possibilités théoriques pour tout calcul effectué par un ordinateur concret

Ordinateur, calculatrice : même combat, mêmes problèmes, la seule chose qui change c'est la taille de la mantisse.

Ouhla, on parlait de nombres rationnels ! Cela dit, là encore, il est tout à fait possible de programmer le logiciel de telle sorte qu'il donne (une sur-approximation de) les marges d'erreur

Non. Ce n'est pas possible. Ou alors dis moi comment on fait.

Ce que je voulais dire, c'est qu'à défaut de promettre de réussir tous les calculs, il est possible d'avertir l'utilisateur qu'un résultat est (ou est susceptible d'être) aberrant.

Non plus. Si tu donnes à Maple ou autre, à calculer la somme des de 1 à 10000000 il va te donner un résultat sans te prévenir de rien. Si tu augmentes la précision
souhaitée, il te donnera des résultats qui semblent contradictoires, jamais il ne te préviendra. Pourtant les nombres utilisés sont très petits (on tape pas plus haut 10 puissance 14).

Ce genre d'énoncé est bien trop flou. Pris tel quel, il est trivial

Prends le tel quel. Tant mieux s'il est trivial vu qu'il est vrai. Si tu veux que je précise le "flou" je dirais, par exemple qu'il ne peut même pas gérer les rationnels de [0;1] de la forme p/q avec p < q premiers entre eux et .

Bon de toute façon, on ne parlait pas de nombres réels.
Ca tombe bien, je viens de t'expliquer pourquoi même les rationnels de [0;1] ne sont pas manipulables (seule une infime partie d'entre eux le sont).

Si on utilise un calculateur formel pour faire des choses basiques même avec les entiers on est très vite limité. Par exemple, résoudre un problème de première année (ou de bon terminale S) du type "donner le dernier chiffre de ".

Encore une fois, que ce soit avec les entiers, les rationnels, ou les réels, un pc ne peut pas faire grand chose, heureusement, souvent, on peut s'en contenter.

La seule chose qu'un pc sait faire, très vite et très bien, c'est le calcule modulaire modulo n où n est relativement petit (ie rentre en mémoire). Ca s'arrête là, et c'est déjà bien.

Non car pour donner le meilleur arrondi, il faut parfois user du test d'égalité. C'est pourquoi il faut laisser le test d'égalité possible.

Par contre, celui qui programme et veut faire des maths doit apprendre ce qu'une machine peut et celle qu'elle ne peut pas faire. Elle doit aussi comprendre qu'il n'y a aucune solution à ce problème car on l'a démontré.

En fait, la communauté scientifique a travaillé depuis 40 ans (voire plus) sur ces sujets et on en a tout simplement fait le tour sur les machines de Turing.
Pour la faire simple, on démontre qu'avec les machines dont on dispose on ne peut pas faire mieux que ce qu'on fait actuellement.
Un logiciel de calcul formel qui fait du calcul avec des réels ne fait d'ailleurs que ce que IEEE754 fait sauf qu'on peut fixer le nombre de bits de la mantisse et de l'exposant augmentant ainsi un peu le champ des possibles. Rien de plus.

@gUI
Ca fait plusieurs fois que je te réponds la chose suivante (l'as tu vu ?):

La science a progressé et permet de démontrer qu'aucun système de calcul (formel ou non) basé sur les machines classiques ne peut répondre à ce que tu demandes. C'est la nature des nombres réels qui fait que c'est impossible.

bc ne fait pas mieux mais tu ne le comprends pas (il fait des erreurs similaires sur des calculs tout aussi simples).
Exemple:

3*(1/3)
.99999999999999999999

Autrement dit, c'est le progrès scientifique qui permet de prouver qu'il n'y a aucun "progrès" possible dans la direction que tu souhaites.

J'ai mis des guillemets autour de "progrès" car en fait, la science ne progresse pas dans l'illusion mais dans l'étude de la réalité.

Si la conversation tourne au troll depuis une trentaine de commentaires c'est parce qu'il te manque des connaissances sur le concept de nombre réel et en particulier celui de sa représentation (nécessairement impossible) dans une machine de Turing. Donc tu écris des choses assez véhémentes sans te rendre compte que tu réponds à côté malgré la patience (relative) de tes interlocuteurs.

Bonne journée à toi :)

C'est peanuts, mais ça inclut les nombres qu'un utilisateur humain entre dans une calculatrice

2017 rentre dans une calculatrice, aussi, mais le résultat te donne une erreur.
On parlait bien de calculateur formel ? (tu embrayes sur la calculatrice là).
La calculatrice fait les mêmes erreurs que python (sauf qu'elle utilise la représentation BCD pour éviter de surprendre l'utilisateur quand il manipule des décimaux). Dès qu'on la fait calculer avec des 1/3, paf !, elle fait les mêmes "bêtises" que Python.

Si on reparle de calculateur formel, celui qui l'utilise aujourd'hui est un utilisateur d'un type spécial: il sait que son calculateur ne peut faire que très peu de choses et il doit malgré tout sortir des choses cohérentes. Ca nécessite des connaissances (souvent importantes), pour arriver à faire des choses intéressantes malgré tout.

Il est en revanche possible de promettre de ne pas retourner de résultat faux ou imprécis, pour peu qu'on s'autorise à retourner "je ne sais pas", quand on sort (ou risque de sortir) des capacités de la machine pour la représentation utilisée.

Ce n'est malheureusement pas du tout le cas (sauf à faire des petits calculs tout gentils). Mais, par exemple: tu demandes à Maple ou Mathematica (ou ce que tu veux) de calculer la somme des pour n variant de 1 à 10000000 (par exemple pour conjecturer si la série est bornée). Tous les nombres en jeu sont gentils (pas trop gros) et pourtant, si tu fais l'expérience, en lui demandant 2 chiffres après la virgule de précision, elle va te renvoyer un truc du genre 32.45, puis tu lui en demandes le même calcul avec 3 chiffres de précision et elle peut te renvoyer un truc du genre -1234.769 (fais l'expérience).
Pourtant les nombres manipulés sont petits, pourtant tu as demandé d'augmenter la précision (chaque fois que tu vas demander d'augmenter la précision tu obtiendras des résultats totalement farfelus qui semblent contradictoires).

Donc, non, un calculateur formel, ne permet que dans des cas simples, des "cas d'école", de donner des résultats satisfaisants mais la plupart du temps, dès qu'on en a justement carrément besoin, ça calcule comme ça peut, c'est à dire très mal. Et c'est normal car:

Aucun système de calcul basé sur les machines actuelles ne peut prétendre ne serait-ce que de manipuler correctement les réels de [0;1].
Ce n'est pas parce qu'on est mauvais, mais parce qu'on est assez bon pour démontrer que c'est impossible.

Bon après, si on touche aux ordinateurs quantiques, ça change tout hein (même s'il n'y aura toujours pas de miracle). Mais là je parle des machines classiques.

Petit commentaire 2 : Les nombres réels, ce sont à peu près les seuls qui n'existent pas dans la nature.

En 400avJC on ne disposait que des rationnels et l'absence des réels ne permettait pas de résoudre des problèmes issus de la géométrie naturelle, du genre:
Comment tu fais pour calculer la diagonale d'un carré de de côté 1 sans les réels ?
La diagonale d'un carré de côté 1 "n'existe pas dans la nature" ? (<-- je ne comprends pas vraiment ce que ça veut dire)

2000 ans après, on résout les problèmes qu'on avait en construisant les réels (qui de fait existent dans nos têtes donc dans la nature).

@gUI

En fait, on peut démontrer qu'il n'existe aucun système informatique de calcul basé sur nos machines classiques permettant de faire des calculs justes avec les nombres réels (déjà parce qu'ils ne sont pas représentables en machine, pour des raisons mathématiques liées à la nature des nombres réels).
Ce n'est pas une question de progrès. Je dirais même qu'on a suffisamment fait de progrès en science pour démontrer que ce que tu voudrais n'existe pas.

Excel ou d'autres tentent de gommer les merdouilles qu'ils calculent mal par des algos plus ou moins sophistiquées (des magouilles en fait), pour donner un résultat tout rond (parce que c'est censé être probablement tout rond mais bon, c'est pas certain), ça les regarde. Ca ne rend pas les résultats qu'ils donnent plus crédibles en général.

Certes. Mais il n'y a pas que les représentations en virgule flottante dans la vie.

Le sujet de la conversation c'est la représentation des flottants en machine et les problèmes que ça pose pour faire des calculs du quotidien. C'est de ça que je parlais aussi.

Avec d'autres représentations, il est tout à fait possible de réaliser des calculs exacts avec n'importe quels nombres rationnels (limités seulement par la mémoire de la machine)

Si tu veux pinailler, pinaillons. Ca fait très, très, très peu d'entiers "ceux dont l'écriture est limitée par la mémoire de la machine" puisque c'est fini de chez fini ! C'est peanuts :)

La promesse de l'infini est une illusion totale et ce n'est d'ailleurs absolument pas celle tenue par les logiciels de calcul formel munis de librairies d'arithmétique multiprécision.

En arithmétique, ces bibliothèques fournissent tout au mieux des outils pour conjecturer, rien de plus.

En première année, toujours en arithmétique, les étudiants font souvent cet exercice qui consiste à déterminer le dernier chiffre de . Le premier truc qu'on leur dit, c'est "abandonnez l'idée d'effectuer directement ce calcul avec un ordinateur, et on leur demande d'expliquer pourquoi".

Idem pour la valeur de l'entier , qui contrairement à celle de 123 n'est pas représentable en machine au sens de la représentation des entiers en machine (c'est à dire via l'écriture dans une base). Par exemple si tu demandes à un système de calcul formel de de te calculer la somme de ses chiffres, il ne pourra pas (alors que ça fait juste 1) car il ne peut le calculer au sens de la représentation dans une base.

Je serais beaucoup plus prudent que toi :)
Exemple en python 3:

r=0
while r != 1:
  r += 0.1
print ('fini !')

Ça boucle à l'infini sans jamais afficher 'fini !' alors que "normalement", ça devrait s'arrêter au bout de 10 tours.
Le pire c'est que si tu contrôles avec des print (r), tu verras qu'il "passe" par 1 (à l'affichage mais pas en interne !!!)
Ce genre d'erreurs c'est ultra fréquent et on peut s'arracher les cheveux dessus pendant longtemps avant de se rendre compte qu'on doit apprendre des choses sur la représentation des flottants en machine.

Tu découvres simplement que les nombres décimaux non entiers ne sont pas représentables nativement par un ordinateur de manière exact.

Ce n'est pas tout à fait vrai. Je me place, pour simplifier les écritures, dans le cas où on travaille sur un processeur 64 bits. La norme de représentation IEEE754 stipule que les "rationnels binaires" sont exactement représentables en machine. Il s'agit des rationnels de la forme où ( désigne ce qu'on appelle la mantisse du nombre). Je ne mentionne pas la partie "exposant" du flottant qui permet essentiellement d'atteindre des rationnels de la forme précédente multipliés par des puissances positives ou négatives de 2 (histoire de se "rapprocher" de 0 ou de ) et je ne parle pas du bit de signe non plus (qui permet d'aller titiller les négatifs).

Les calculs qui sont faits avec ces rationnels binaires sont parfaitement exacts tant que les tailles des résultats restent dans les plages de représentation imposées par la norme.

Tout rationnel binaire est un décimal mais la réciproque est fausse.

En gros un nombre de la forme 0,375 (qui vaut 1/8, c'est à dire ) est un rationnel binaire, donc est représentable sur 64 bits sans aucune approximation. En mémoire, les 52 derniers bits de mantisse (occupant 6,5 octets) seraient
110000000000000000000000000000000000000000000000000000
Pour illustrer, en python, si tu calcules: 0.25 - 0.375 + 0.125 alors il sort bien 0.0.

A contrario, un nombre comme 0,2 (qui vaut 1/5) ne l'est pas (car c'est un décimal non rationnel binaire). Il sera stocké avec une mantisse de la forme avec arrondi (en fonction des options données au FPU) à l'entier le plus près, ou inférieur, ou supérieur.

C, C++, Pascal, Ada, Python ou autres utilisent la norme IEEE754 pour manipuler des flottants et font tous une approximation au rationnel binaire le plus proche avant de procéder aux opérations. On peut utiliser des librairies qui augmentent le nombre de chiffres de la mantisse et donnent l'illusion d'une précision infinie, ce qui est évidemment totalement faux. Par exemple, même avec des bibliothèques spécialisées comme GMP pour faire de l'arithmétique multiprécision, la valeur de l'entier n'est pas représentable en machine (car le nombre de chiffres à afficher (à savoir ) dépasse le nombre d'atomes dans l'univers visibles !!!).

Merci pour tes précisions mais je n'ai pas compris ce que fait un shift right de 64 sur un PowerPC (par exemple avec du C compilé par gcc).

• À bas niveau il y n'y a que la logique des transistors. Là on est d'accord.
• À plus haut niveau, on a une couche d'abstraction qui fait qu'un "computer" est là pour "calculer" en respectant des règles arithmétiques communes à tout le monde.

La discussion (sans fin), c'est que certains langages dits de "haut niveau" ne fournissent pas cette couche d'abstraction et ce, essentiellement parce que:
1. ils ne disposent pas de la notion de sous-type contraint (donc des fonctions prennent des arguments qui peuvent aboutir silencieusement, à des comportements non définis)
2. ils prétendent que ça "optimise" (alors que ça pourrait l'être tout autant avec la notion de sous-type contraint comme je l'ai montré plus haut).

Tu pourrais nous donner le résultat d'un shift right sur un espace mémoire de 64 bits initialisé à 1 en C avec gcc sur powerpc (si tu as ça sous la main bien évidemment) ?

Je complète mon post précédent pour préciser que même GMP ne permet pas à la machine de faire d'arithmétique sur (comme aucune machine qui, pour stocker un entier, stocke ses chiffres). Cela augmente significativement les possibilités mais c'est tout.
Je m'intéressais aux capacités natives des langages (sinon j'avais déjà évoqué gmp dans un post précédent).

De l'arithmétique sur  ? Vraiment ? Ca me paraît impossible.

Ada fait de l'arithmétique exacte dans avec N naturel compris entre 1 et . C'est déjà pas mal du tout (avec une arithmétique optimisée au plus bas niveau pour N=8, 16, 32 ou 64. Il y a la notion de type modulaire pour cela.

Pour faire de l'arithmétique sur un minuscule sous ensemble de (j'imagine que c'est ce dont tu parles) il y a le type (et des sous types) de Integer. Les opérations arithmétiques peuvent générer des exceptions si les résultats ne sont pas représentables (sortent des plages de représentation). Dans tous les cas, aucun résultat n'est donné s'il est incohérent avec l'arithmétique (ce qui n'est pas le cas de OCaml, C, C++, Pascal etc qui laissent des comportements indéfinis, sources de résultats inattendus pour celui qui n'a pas lu les moindres détails de la doc, et ils sont nombreux ceux là). Ceci est fait au prétexte de l'optimisation sur certains processeurs. Or ce prétexte s'explique par le fait que ces langages ne disposent pas de la notion de sous type contraint.

En Ada, il y a deux options laissées au développeur:

• être certain que les opérations ne provoquent aucun overflow et demander au compilo, par une pragma clairement écrite dans le code source, de ne pas les gérer pour optimiser les calculs.

• laisser le compilo vérifier les "constraint errors" ce qui ralentit l'exécution mais permet de s'apercevoir, pendant la conception, d'éventuelles erreurs de programmation.

Les choses sont ainsi parfaitement claires, toujours optimisées bas niveau (si besoin), aucun appel ne provoque de résultat indéfini silencieusement. A mon âge, quand je vois un langage qui ne propose pas ça, j'ai du mal à le considérer de "haut niveau" (même s'il possède d'autres qualités très intéressantes par ailleurs).

C'est extrêmement formateur. Combien d'étudiants déclarent un integer pour manipuler des entiers sans se soucier de la cohérence arithmétique des résultats ? Chaque année, en C ou Pascal, avec les collègues, on en voit passer des boucles infinies par méconnaissance de la modularité du type integer dans ces langages de "haut niveau".

Ainsi les cas exceptionnels qui ont besoin de sortir de ces bornes doivent coder leur propre fonction avec un test sur la valeur de l'entrée.

Non.
Si OCaml disposait de la notion de sous types (contraints) alors il disposerait de deux fonctions shr. L'une utilisant ce type contraint garantirait l'efficacité optimale et l'autre (qui ferait le test) pour assurer la cohérence de l'arithmétique pour tout valeur naturelle de l'argument.
Il n'y aurait donc la vérification à faire que lorsque cela est nécessaire pour le développeur. On y gagnerait sur tous les plans. C'est ce que j'expliquais dans un ancien post.

D'autre part une signature de la fonction shr avec deux int en entrée et un int en sortie est étrange puisque le second paramètre devrait être un entier naturel (en tout cas sûrement pas un modulaire, qui n'a aucune signification arithmétique cohérente). Du coup on se retrouve avec une fonction qui a des comportements indéfinis en fonction de certaines valeurs des paramètres ce qui est source de bug (la preuve avec mes étudiants). Là tu peux avoir des résultats qui ne lèvent aucune exception au runtime ni aucun avertissement à la compilation.

Le choix de l'école a été de former les étudiants dans leurs deux premières années d'info sur FreePascal. Dans un post plus haut ce choix a été expliqué.

Je milite à titre personnel (mais je ne fais pas partie de l'équipe d'info) pour qu'on passe, comme à l'INSA Toulouse, à Ada. Le problème c'est que ça demande beaucoup de temps (entre autres pour refaire tous les supports de cours et former les collègues qui ne connaissent pas ce langage). Je le redis au passage: ils apprennent également Python et C au cours de leur projet math et de leur projet info. Ceux qui iront dans le département info toucheront à tout.

FreePascal permet de répondre malgré tout aux besoins (et même plus) qu'ont les étudiants (grands débutants en première année). Le projet que j'ai donné est destiné à des élèves en fin de premier cycle dans le cadre d'une introduction à l'analyse numérique et à la sensibilisation au problème épineux de la représentation des nombres en machine source de nombreuses erreurs de conception dans des algorithmes de calculs (phénomène de cancellation, d'absorption, gestion de l'erreur relative et de l'erreur absolue etc).

Le projet n'a pas été pensé et préparé en Ada. Il a été pensé de façon théorique puis implémenté initialement en Pascal chez moi. Mon implémentation tournait parfaitement mais je n'étais pas allé faire des tests unitaires aussi poussés qu'eux tout persuadé que mon algo était bon (et il l'était !). Fallait quand même imaginer qu'un décalage de 64 entre deux exposants de deux flottants qu'on veut additionner allait provoquer cette erreur sournoise et non documentée par FreePascal.

Ensuite j'ai voulu faire la même chose proprement en Ada chez moi pour le fun.

Et là, je reçois un mail d'un binôme qui a le bon algo, exactement la bonne démarche, la bonne implémentation a priori, qui me dit "on a une incohérence dans des tests unitaires". Après leur propre investigation (pendant une semaine) et un ou deux échanges avec eux on isole le problème et on voit que shr a un comportement (non documenté par la doc de fpc) complètement incohérent sur le plan arithmétique. Puis je me suis aperçu avec un ami (l'auteur du journal) que de nombreux langages soit disant de haut niveau souffraient de cette incohérence qui consiste à reproduire "bêtement" ce que fait le shr des X86 pour des raisons d'optimisation à bas niveau.

Une fois le bug identifié, un simple "if" a permis de régler le problème et tout revenait dans l'ordre.

Voilà l'histoire :)

En tout cas, j'ai trouvé ça super intéressant de suivre les remarques de chacun, ça montre un aperçu de la façon d'aborder l'arithmétique des entiers dans plein de langages et c'est chouette !

J'aime beaucoup le principe du moindre étonnement :)

Mais une question que j'avais posée est : qu'est-ce qui peut pousser un développeur à utiliser cette fonction en dehors des bornes 0 .. 63 ?

A cette question je pourrais répondre bêtement en disant que je veux que la fonction suivante calcule le quotient de n par pour toutes les valeurs de la plage des types de ses arguments.

function quo_power2 (n, a: natural) return natural;

Mais je vais préfère t'expliquer dans quel contexte moins artificiel on peut avoir besoin d'un décalage supérieur ou égal à 64 en te décrivant une petite partie du projet de mes étudiants.

Description partielle du projet

Celui-ci consiste à coder les opérations et sur le type "double" en n'utilisant que des opérations sur les entiers unsigned sur 64 bits (les qword en Pascal). Autrement dit jouer avec la norme IEEE754 qui décrit la représentation des flottants en machine ainsi que les opérations standard sur ces flottants. Cela permet vraiment de comprendre en profondeur qu'une machine ne sait vraiment pas manipuler correctement les réels (contrairement à ce qu'ils croient tous).

Description de la représentation machine des « double »

Grosso modo, cette norme stipule qu'un double est un espace mémoire sur 64 bits organisé, de gauche à droite, de la façon suivante: 1 bit de signe (s) , 11 bits d'exposant (e) et 52 bits de mantisse (k). Le réel correspondant à cet espace mémoire est alors . Donc déjà, une remarque, il faut un langage permettant de lire un même espace mémoire avec deux typages différents (double et qword) donc, adieu Python.

Addition machine des « double »

Je ne vais pas traiter tous les cas mais celui qui a fait apparaître le fameux problème dont on discute : l'addition de x et y (x>y>0). Je note k et k' les mantisses entières respectives de x et y, e et e' leurs exposants.

Un petit calcul montre que l'exposant de la somme est le max des deux exposants (éventuellement + 1) . Pour le calcul de la mantisse on a nécessairement, à un moment donné, . Vu que e'-e<0, cela revient à diviser k' par une puissance de deux comprise entre 0 et 2046. Donc à faire un shr sur k' d'un amount compris entre 0 et 2046.

Sauf que voilà, pour une raison d'optimisation qui leur était totalement inconnue, le comportement arithmétique de cette opération redevient identique modulo 64 et patatra !

Quand j'ai préparé le projet chez moi, en Ada, je n'ai vu aucun problème car Ada ne reproduit pas les optimisations de bas niveau en cassant l'arithmétique. Le compilateur FreePascal lui, reproduit ce comportement arithmétique incohérent et sa doc ne dit rien à ce sujet.

Côté statique

with ada.text_io;use ada.text_io;
procedure test_int_ada is
begin
  put_line (natural'image(natural'last+1)); -- demander l'affiche du dernier naturel + 1 
end test_int_ada;

renvoie à la compilation:
test_int_ada.adb:4:39: value not in range of type "Standard.Integer"
test_int_ada.adb:4:39: static expression fails Constraint_Check

Côté dynamique:

with ada.text_io;use ada.text_io;
procedure test_int_ada is
  i : natural := natural'last-1;
begin
  for j in 1..2 loop
    i := i +1;
  end loop;
  put_line (i'img);
end test_int_ada;

Renvoie:
raised CONSTRAINT_ERROR : test_int_ada.adb:6 overflow check failed

Donc non le type natural n'est pas du tout cyclique. Mais…

Ada gère les types modulaires

Par exemple, si tu écris :

type my_mod_7 is mod 7; -- ce type représente les éléments de  Z/7Z
[...]
put_line (my_mod_7'img (my_mod_7'mod(8))); -- on affiche le représentant de la classe de 8

alors ça t'affiche 1.

Ada fait dont exactement ce qu'on lui demande dans la mesure du réalisable avec les types primitifs gérables par la machine.
Si on veut un comportement modulaire, on définit comme ci-dessus le type, et on dispose de toute l'arithmétique (cohérente) sur ce type dans les limites offertes par la machine.
Maintenant, si on veut dépasser les limites du jeu d'instruction du processeur et qu'on veut faire de l'arithmétique multi-précision ils existe bien évidemment un binding Ada pour gmp.

Comparaison avec C++

#include <iostream>

int main()
{unsigned char u=254;
  while (u<=255) u+=2;
  std::cout<<u;
  return 0;
}

Aucun warning, aucune erreur de compilation, aucune exception à l'exécution, et le programme boucle à l'infini car 'unsigned char' est vu comme un type modulaire (modulo ) ce qui ne s'appuie sur aucun fait explicable (à part le fait de vouloir représenter la table ASCCI comme un cercle). Plus intéressant, il est impossible d'arriver à un tel comportement avec Ada.