kantien a écrit 1131 commentaires

Difference between CLOCK_REALTIME and CLOCK_MONOTONIC? ;-)

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

D'ailleurs, je préfère la version verbeuse, je la trouve plus lisible ;)

C'est parce que la pipeline est courte. Il faut voir cette notation pointée de Rust comme le pipe | du shell : reader.next() | unwrap_or | map_err | map. Sur de longues pipelines, c'est plus simple à écrire et il vaut mieux laisser le compilateur inliner le tout plutôt que de le faire à la main (comme dans sa version verbeuse, qui contient d'ailleurs une erreur : le cas None doit retourner Ok(false) de type Result<Bool, String>).

En OCaml (j'étais bien obligé), on écrirait un code du genre :

next reader |> Option.default (Ok "q") |> Result.map_both (fun s -> s <> "q") format_error

Les patterns à base de map sont omniprésents dans le paradigme fonctionnel. Un type paramétrique à un paramètre (comme les options, les listes, les tableaux, les vecteurs…) est une fonction des types dans les types. Ainsi si j'ai une fonction qui transforme les objets du paramètre (disons des int en string), je peux la lifter pour opérer sur le type paramétrique (un peu comme une composition de fonction, si tu veux). Exemples :

(* un int optionnel devient un string optionnel *)
Option.map string_of_int (Some 1);;
- : string option = Some u"1"

(* une liste de ints devients une liste de strings *)
List.map string_of_int [1; 2; 3];;
- : string list = [u"1"; u"2"; u"3"]

(* un tableau de ints devient un tableau de strings *)
Array.map string_of_int [|1; 2; 3|];;
- : string array = [|u"1"; u"2"; u"3"|]

Le type Result est lui un type paramétrique à deux paramètres : on peut donc faire un map soit sur le type en paramètre de Ok, soit sur celui en paramètre de Err. Ce qui soit donne deux fonctions map (comme en Rust), soit une fonction map_both comme dans mon exemple en OCaml (ou bimap en Haskell) qui prend deux fonctions en paramètres (une pour chaque type).

(* la double map pour le type result *)
let bimap f g = function Ok x -> Ok (f x) | Error e -> Error (g e)

(* le unwrap_or comme en Rust *)
let unwrap_or d = function None -> d | Some x -> x

(* la pipeline comme en Rust *)
let pipeline x = 
  x
  |> unwrap_or (Ok "q")
  |> bimap (fun s -> s <> "q") ( Printf.sprintf "Houla y'a eu un truc: %s")

(* exemples de sortie *)
pipeline None;;
- : (bool, string) result = Ok false

pipeline (Some (Ok "f"));;
- : (bool, string) result = Ok true

pipeline (Some (Error "une erreur"));;
- : (bool, string) result = Error u"Houla y'a eu un truc: une erreur"

P.S : sinon sympa le journal, et comme depuis les derniers journaux sur la virgule flottante j'ai installé GNAT et GNAT Programming Studio je vais pouvoir regarder un code ADA idiomatique et jouer avec :-) (ravi de voir au passage qu'il y a des développeurs ADA qui comprennent l'encapsulation ;-).

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Pourquoi vous n'avez jamais trouvé un moyen d'éviter d'utiliser les insupportables opérateurs float (+.),(-.),(/.),(*.) ?

Il y a une proposition pour résoudre ce problème, et offrir bien plus de possibilité, sous la forme de modules implicites. Il y a eu une discussion sur le sujet sur le forum OCaml, et il reste des questions tant théoriques que pratiques (au niveau de l'implémentation) à résoudre avant de voir apparaître le système dans le langage.

Pour faire simple, l'idée est de passer par des modules de premières classes et, dans le cas de ces opérateurs, de définir, disons, un type de module pour les corps :

module type CORPS = sig
  type t
  val zero : t
  val one : t
  val add : t -> t -> t
  val sub : t -> t -> t
  val mul : t -> t -> t
  val div : t -> t -> t
end

puis à définir, disons une fonction add, qui opère sur n'importe quel corps et des valeurs du support du corps :

let add (type a) (module M : CORPS with type t = a) x y = M.add x y;;
val add : (module CORPS with type t = 'a) -> 'a -> 'a -> 'a = <fun>

Ici le corps à passer en paramètre est explicite et si on utilise l'alternative Batteries à la bibliothèque standard, on peut écrire :

add (module Float) 2.3 4.5;;
- : float = 6.8

L'idée étant de faire du module de première classe un paramètre implicite déterminé automatiquement par le compilateur en fonction du type des paramètres x et y. Ici comme ce sont des float, le compilateur cherchera dans son environnement au moment de l'appel à add un corps sur les float déclaré utilisable comme arguments implicites.

En attendant, si tu utilises Batteries tu peux écrire ton code sur les flottants via des open locaux :

let open Float.Infix in 2.3 + 4.5;;
- : float = 6.8

voir la définition du module Float.Infix :

#show_module Float.Infix;;
module Infix = BatFloat.Infix
module Infix :
  sig
    type bat__infix_t = float
    val ( + ) : float -> float -> float
    val ( - ) : float -> float -> float
    val ( * ) : float -> float -> float
    val ( / ) : float -> float -> float
    val ( ** ) : float -> float -> float
    val ( -- ) : float -> float -> float BatEnum.t
    val ( --- ) : float -> float -> float BatEnum.t
    val ( =~ ) : ?epsilon:float -> float -> float -> bool
  end

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Ltac est un bousin sans nom qui est la source d'un tas de problèmes, le genre de code qu'il suffit de regarder fixement pour faire péter un développement à l'autre bout de la planète.

Justement, au sujet de Ltac, vous avez des idées ou des pistes pour l'améliorer et faciliter l'écriture de tactiques ? Si on prend l'exemple de patrick_g :

Par exemple dans de nombreux articles de géométrie arithmétique ou de géométrie algébrique on peut voir des phrases du style : "Par un argument à la GAGA il est facile de voir que blabla".

il doit bien être possible d'écrire une tactique gaga, mais ce possible reste souvent « théorique », écrire une tactique finissant par rendre à moitié fou (j'ai jamais bien compris comment marchait le système).

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Et tu n'as pas parlé d'une partie qui me semble prendre de plus en plus de temps dans le monde académique : la recherche de financement.

Pour le langage développé au sein de sa nouvelle équipe, on trouve ces informations sur le site du langage. À l'origine, le projet fut financé par l'entreprise Boston Scientific spécialisé dans le matériel médical, puis par des fonds publics provenant de la National Science Foundation (équivalent américain du CNRS).

Je me demande, d'ailleurs, si le nom du langage (Abella) ne vient pas du premier financeur : l'entreprise a été cofondée par John Abele. Au départ (j'aime bien essayé de trouver l'origine des noms des projets) je pensais que le nom faisait référence au logicien de l'époque scolastique Pierre Abélard car il est souvent utilisé en théorie de la démonstration avec sa bien aimée Héloïse (comme dans l'article Formules valides, jeux et protocoles réseau qui utilise des principes identiques à ceux dont parle gasche dans son journal, mais pour la certification de protocoles réseau), mais l'hypothèse de John Abele me semble plus probable.

démystifier l'activité de recherche et montrer à quoi « ça sert » puisque l'on vit dans un monde où la finalité semble importante à beaucoup :-/

Il en a été de tout temps ainsi, et une citation du maître pour la route :-)

Il n'est point de connaissance qui soit superflue et inutile de façon absolue et à tous égards, encore que nous ne soyons pas toujours à même d'en apercevoir l'utilité. C'est par conséquent un objection aussi mal avisée qu'injuste que les esprits superficiels adressent aux grands hommes qui consacrent aux sciences des soins laborieux lorsqu'ils viennent demander : à quoi cela sert-il ? On ne doit en aucun cas poser une telle question quand on prétend s'occuper de science. À supposer qu'une science ne puisse apporter d'explication que sur un quelconque objet possible, de ce seul fait son utilité serait déjà suffisante. Toute connaissance logiquement parfaite a déjà quelque utilité possible : même si elle nous échappe jusqu'à présent, il se peut que la postérité la découvre. Si en cultivant les sciences on n'avait jamais mesuré l'utilité qu'au profit matériel qu'on pourrait retirer, nous n'aurions pas l'arithmétique et la géométrie. Aussi bien notre intelligence est ainsi conformée qu'elle trouve satisfaction dans la simple connaissance, et même une satisfaction plus grande que dans l'utilité qui en résulte. Platon l'avait déjà remarqué. L'homme y prend conscience de sa valeur propre; il a la sensation de ce qui se nomme : avoir l'intelligence. Les hommes qui ne sentent pas cela doivent envier les bêtes. La valeur intrinsèque que les connaissances tiennent de leur perfection logique est incomparable avec leur valeur extrinsèque, qu'elles tirent de leur application.

Emmanuel Kant, Logique

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

tu veux dire Inria? ^{^}

C'est une boutade au sein de l'Institut depuis qu'ils ont changé leur identité visuelle ?

En tout cas, gasche suit la graphie de sa nouvelle équipe — qui n'a peut être pas mis à jour sa page de présentation depuis le changement, à la lecture des dates qui y figurent.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Bon je vais arrêter là, on ne tombera jamais d'accord. Juste deux remarques :

Et comment tu lui dis à Python comment il doit arrondir sachant que les règles d'arrondi tu en as quasiment une par pays ! cf https://en.wikipedia.org/wiki/Cash_rounding

C'est des règles pour les paiements en liquide, ça ne nous concerne pas : personne n'a besoin de machine pour faire cela. Par exemple en Belgique, ils ont retiré les pièces de 1 et 2 cents d'euros, donc si le marchand te sors un montant de 9.98 (via sa machine) alors tu paieras 9.95 : le commerçant comme toi appliquez la règle. ;-)

Rien de de que dit Muller dans le lien que tu me donnes ne contredit tout cela (ou alors j'ai raté un passage).

Ça tombe bien je n'ai jamais soutenu cela, ni cherché à contredire ce que tu faisais avec tes float. Relis bien tout mon laïus sur la différence entre type concret et type abstrait, et tu comprendras que l'article n'avait nullement pour intention de te contredire. Je ne sais pas si c'est moi qui m'exprime mal ou si c'est toi qui a du mal à comprendre, mais il y a un problème de communication entre nous.

Comme il y a un quelqu'un qui moinse sans raison, ni sans s'exprimer, comme je pisse dans un violon en me fatigant à écrire tout un texte sur le principe qu'une bibliothèque doit fournir une API, c'est-à-dire un langage pour un domaine métier spécifique (ou EDSL), en cachant l'implantation concrète des types qu'elles exposent (qui peuvent tout à fait être dans notre cas un float comme tu n'as pas cessé de l'illustrer, et donc je n'ai jamais cherché à te contredire sur ce point là), je préfère arrêter les frais de cette discussion qui ne mène nulle part. Peut être que la célèbre fable de Reynolds sur les deux représentations des nombres complexes à la Bessel (coordonnées polaires) ou à la Descartes (coordonnées cartésiennes) te fera voir où je voulais en venir.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Appelons D le type censé représenter notre monnaie. Qu'attendons nous de lui ?

1. D doit pouvoir représenter de façon exacte les nombres de la forme k/100 où k est un entier compris dans un intervalle fixé borné (ici on pourrait se contenter de k inférieur à 1 million de milliards soit 10 puissance 15).
2. […]

Je m'arrête là pour le fond et je conteste cette partie de la spécification que tu proposes (sinon tout le reste s'ensuit bien, comme il se doit, sur le plan mathématique : je conteste ta première prémisse).

Regardons déjà ce que Dring t'a répondu quand tu lui as proposé les décimaux à virgules fixes avec deux chiffres après la virgule :

Le truc chiant avec les devises, c'est qu'elles n'ont pas toutes 2 décimales. Du coup, est-ce que dans ce code la valeur du delta peut être une variable ? Je crains que non.

et maintenant regardons, par exemple, les règles fixées par la Communauté Européenne lors de l'introduction de l'euro dans la publication The introduction of the euro and the rounding of currency amounts. On y trouve dans la section 3.3 Use of the conversion rate (p. 8) :

The rates have been adopted with six significant figures, e.g. 1 EUR = 40.3399 BEF.

Wherever these conversion rates are used, they will have to be applied exactly, i.e. with six significant figures; no rounding or truncating of the conversion rates is allowed (Article 4(2)).

Parmi les taux de change fixés par la commission, on trouve :

1 euro = 40.3399 francs belges
1 euro = 1.95583 marks allemands
1 euro = 166.386 pesetas espagnoles

personnellement j'appelle cela des décimaux flottants avec 6 chiffres significatifs (et donc le type decimal32, qui a 7 chiffres significatifs, permet de gérer les taux de changes dont la norme est légalement fixée par l'Union Européenne).

Les mêmes règles existent de nos jours pour les conversions avec les monnaie hors zone euro. Celles fixant la gestion des arrondis, les problèmes de double-conversion pour revenir dans la monnaie d'origine y sont également définies.

J'espère que ce simple exemple répond à la demande qui conclut ton commentaire :

Peut-être pourrais-tu nous rappeler précisément ces besoins. J'ai l'impression que ni toi ni moi ne les connaissons précisément. Je fais ce que je peux en raisonnant mais si tu as des choses plus précises n'hésite pas à en faire part, c'est toujours intéressant.

Pour ta partie sur la forme, tu as mal compris ce que je voulais dire.

Mauvaise foi ? On était parti d'erreurs factuelles sur le site d'IBM que tu as mentionné concernant le calcul de 0.70 x 1.05. Ils font deux erreurs: la première sur le résultat du calcul en utilisant des "double".

Il n'y a aucune mauvaise foi, c'est bien un problème d'API. Un programmeur qui a besoin de décimaux veut pouvoir écrire : arrondi moi ce nombre à la deuxième décimal selon telle règle d'arrondis. Autrement dit, il veut quelque chose du genre :

module type Decimal = sig
  type t
  val round : int -> t -> t
  (+) : t -> t -> t
  (*) : t -> t -> t
  dec : string -> t
end

et si il utilise une module Decimal avec une telle interface, il exige que l'opération suivante retourne 0.74 :

Decimal.(round 2 (dec "0.70" * dec "1.05"))

Toi ce que tu dis, c'est que l'on peut prendre t = float et définir round de façon à ce qu'il se comporte correctement. Ce à quoi je t'ai répondu : personne ne l'a jamais nié, mais le programmeur ne veut pas avoir à faire ça à la main, il veut une bibliothèque qui lui fournisse cela ou un type primitif du langage. Ici le type sera abstrait (en théorie des types on parle de type existentiel¹) ce qui est la base d'un idiome standard en programmation : l'encapsulation. ;-) Et du point de vue de l'utilisateur, rien ne le distingue d'un type primitif : il ne peut rien faire d'autre que de l'utiliser à partir des fonctions exportées par le module.

C'est là toute la distinction entre la représentation abstraite du type de données, déterminée par sa spécification, et la représentation concrète effectivement utilisée par le module pour l'implantation. Je n'ai jamais dit qu'il fallait tout reconstruire à la main, mais seulement que le seul type des entiers naturels permet d'être utilisé pour faire cela, rien de propre au type des flottants binaires.

Je te disais en note de bas de page qu'il y a des articles sur le sujet : utiliser les flottants binaires comme représentation concrète pour implanter la norme IEEE-754 des flottants décimaux. En voici un : Implementing Decimal Floating-Point Arithmetic through Binary: some Suggestions, avec parmi les co-auteurs Jean-Michel Muller que tu as cité dans un de tes commentaires. En voici le résumé :

We propose algorithms and provide some related results that make it possible to implement decimal floating-point arithmetic on a processor that does not have decimal operators, using the available binary floating-point functions. In this preliminary study, we focus on round-to-nearest mode only. We show that several functions in decimal32 and decimal64 arithmetic can be implemented using binary64 and binary128 floating-point arithmetic, respectively. We discuss the decimal square root and some transcendental functions. We also consider radix conversion algorithms.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Quand on a décidé de mal arrondir, c'est sûr, on arrondit mal, ça on est d'accord.

Non ce qui est reproché aux flottants binaires sont leur API si on veut travailler avec du décimal. Que l'on puisse présenter un type abstrait, représenté de manière sous-jacente via le type float primitf (en binaire) d'un langage donné, qui se comporte comme des décimaux : personne ne le nie. Mais à ce compte là, il te suffit de ce type :

type nat =
  | Zero
  | Succ of nat

et de pouvoir faire de la récursion pour encoder tout est n'importe quoi dedans : c'est le principe même de l'informatique et du numérique. Ça va juste mettre à l'épreuve l'ingéniosité et la sagacité du programmeur.

Mais ce que veulent les gens qui ont besoin de décimaux, c'est d'un type qui se comporte comme des décimaux : ils ont autre chose à foutre que de se taper l'encodage à la main. Donc soit le langage le fournit comme un type primitif, soit ils utilisent une bibliothèque le fournissant (et ils se foutent royalement du mécanisme effectivement utilisé pour l'implanter, tant qu'il se comporte comme souhaité).

Si tu spécifies ce que tu veux, tu peux faire une fonction de deux lignes qui renverra exactement ce qu'est censé recevoir l'utilisateur.

Oui et c'est ce qu'a fait l'auteur du site en question, à savoir Mike Cowlishaw, en rédigeant la norme IEEE-754 pour les décimaux flottants.

This specification defines these components in the abstract. It neither defines the way in which operations are expressed (which might vary depending on the computer language or other interface being used),[1] nor does it define the concrete representation (specific layout in storage, or in a processor’s register, for example) of numbers or context.

Si tu veux l'implanter en utilisant des flottants binaires comme représentation concrète¹, libre à toi, tant que tu respectes l'API décrite dans la norme : c'est de cela dont ont besoin les programmeurs.

Voilà comment je comprends le problème concernant la monnaie:

En entrée, on reçoit du décimal x à près (appelons ce type D).
En sortie on veut du décimal y à près.

Effectivement, c'est bien ce qu'il me semblait : tu n'as aucune idée des besoins et des attentes de ce domaine métier. ;-)

Comme Colinshaw a passé un bon bout de temps à se pencher sur ces contraintes métiers, tu devrais te promener un moment sur le site que je cite depuis le début, tu y verras sans doute plus clair après.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Ils veulent le bon arrondi au centième et ils s'y prennent bizarrement je trouve. Le float qu'ils obtiennent 0.734999[…] s'arrondit au millième le plus proche en 0.735 sans aucun soucis. On applique alors la convention bancaire et on obtient bien 0.74. Ils font ça dans tous leurs exemples et argumentent ainsi en faveur du décimal flottant.

Non, ce n'est pas cela qu'il cherche à illustrer mais l'arrondi d'une opération à la deuxième décimale.

>>> round(0.70 * 1.05, 2)
0.73
>>> round(1.30 * 1.05, 2)
1.37

# comparé à
>>> from decimal import Decimal as D
>>> DELTA = D('0.01')
>>> (D('0.70') * D('1.05')).quantize(DELTA)
Decimal('0.74')
>>> (D('1.30') * D('1.05')).quantize(DELTA)
Decimal('1.36')

En plus ils ne mentionnent pas que la plupart du temps, les taux proviennent du résultat d'un quotient et donc ne se stocke quasiment jamais de façon exacte (dans quelque base que ce soit).

Non, les taux de taxes et les taux de change sont fournis en décimal et doivent pouvoir être représentés de manière exacte dans le type. L'exemple du dessus provient d'ailleurs de l'application d'une taxe à 5%.

Pour ce qui est des besoins des Dring, il a surtout fait mention du langage COBOL qui utilise des flottants et du type BigDecimal de Java qui est assez proche des flottants de la norme IEEE-754.

Immutable, arbitrary-precision signed decimal numbers. A BigDecimal consists of an arbitrary precision integer unscaled value and a 32-bit integer scale. If zero or positive, the scale is the number of digits to the right of the decimal point. If negative, the unscaled value of the number is multiplied by ten to the power of the negation of the scale. The value of the number represented by the BigDecimal is therefore (unscaledValue × 10^-scale).

extrait de la documentation de la classe BigDecimal. Un BigDecimal à la forme :

où mant est un entier signé de précision arbitraire et exp un entier signé sur 32 bits. On retrouve aussi dans cette classe la notion de contexte pour les opérations (qui gère les modes d'arrondis, la levée ou non d'exception en cas de résultat non représentable strictement…), toutes choses qui se retrouvent dans la norme IEEE-754 pour les décimaux flottants.

Ce qui semble le plus dérangé Dring, c'est la syntaxe concrète pour faire usage du type en question. Pour ma part je trouve que c'est une question mineure, appeler le constructeur avec une chaîne de caractère pour les constantes au lieu de la syntaxe pour les float ça demande juste d'ajouter deux guillemets ''.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

A bien y réfléchir, je pense que ce que voudrait Dring c'est de la virgule fixe façon COBOL

Sauf que COBOL propose des décimaux à virgule flottante. ;-)

Typically a precision of 25-30 digits is used, though the ISO COBOL 2002 standard requires 32-digit decimal floating-point for intermediate results.

source

D'où la question de Dring pour avoir un exposant (un delta) variable. ;-)

Il y a une raison à ton obsession pour le décimal en virgule fixe et la virgule flottante uniquement en binaire ?

Le standard IEEE-754 pour les décimaux à virgule flottante définit trois types de base avec leur précision :

• decimal32 sur 32 bits avec 7 chiffres significatifs;
• decimal64 sur 64 bits avec 16 chiffres significatifs;
• decimal128 sur 128 bits avec 34 chiffres significatifs.

Il vaut voir que l'ingénieur IBM qui est l'auteur de la norme a passé toute sa vie à développer des outils et langages pour les besoins métiers de Dring. Pourquoi insistes-tu pour l'envoyer sur de la virgule fixe ?

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Pour un flottant décimal comme évoqué dans ton lien, que va provoquer l'affectation sinon de l'absorption ?

Le résultat escompté en base 10

>>> from decimal import Decimal as D
>>> D('10e10') + D('0.01')
Decimal('100000000000.01')

soit .

Le contexte est donc celui de la virgule fixe non ?

Pas spécialement, la dynamique apportée par les flottants peut s'avérer nécessaire, ainsi que le contrôle du mode d'arrondi qui va différer, pour des raisons législatives, selon les régions du monde.

How much precision and range is needed for decimal arithmetic?
What rounding modes are needed for decimal arithmetic?

ou plus simplement la conclusion de la première question de la FAQ

Both problems (the artifacts of binary floating-point, and the limitations of decimal fixed-point) can be solved by using a decimal floating-point arithmetic. This is now available in both hardware and software, as described on the General Decimal Arithmetic page, and is standardized in the IEEE Standard for Floating-Point Arithmetic (IEEE 754).

Dis-toi que si la norme IEEE-754 a été révisée en 2008 pour y ajouter une standardisation de l'arithmétique flottante en base 10, ce n'est pas sans raison mais parce qu'il y a un besoin métier derrière.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Si la spécification est complète, alors je ne vois pas en quoi le type float apporterait plus de problèmes que le type décimal.

Non, il y a des domaines métiers pour lequel les flottants binaires ne sont pas une solution recevable, d'où le besoin de flottants (j'insiste bien sur l'aspect flottant et non fixe) décimaux.

What problems are caused by using binary floating-point?

Une erreur à 5 millions de dollars par an pour une compagnie de téléphone (voir exemple 2, et le benchmark telco associé à ces problématiques métiers), ça fait cher les erreurs de calcul sur l'émission de factures (sans parler des contraintes légales : le législateur fixe les règles et algorithmes en base 10 et il vaut mieux les respecter ;-)

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

mais peut-être qu'ils admettent que le cercle est rectifiable?

Oui et cela sans aucun soucis, voir cette proposition d'Archimède :

Un cercle quelconque est égal à un triangle rectangle dont un des côtés de l'angle droit est égal au rayon de ce cercle, et dont l'autre côté de l'angle droit est égal à la circonférence de ce même cercle.

Dans le même traité, il donne une approximation de par la fraction 22 / 7 (proposition 2).

Ils admettaient (pour des raisons de complétude) que toutes les proportions étaient réalisables, mais ils n'en proposaient par pour autant une construction effective (il y a même là impossibilité pour la trisection de l'angle).

Du côté de chez Euclide, dans son livre IV, où il traite des polygones inscrits et circonscrits, il ne fournit que la construction effective pour le triangle, le carré, le pentagone, l'hexagone et le quindécagone. Le dernier cas est une bonne illustration de la façon dont le géomètres grecs pratiquaient le raisonnement par analyse-synthèse, où la solution est obtenue par combinaison de celle du triangle équilatéral et du pentagone régulier.

Par contre, des livres disponibles sur ce site, je n'ai pas trouvé la preuve du fait que tous les cercles sont semblables (et donc que la circonférence est proportionnelle au diamètre). Il manque la livre V qui traite de la théorie des proportions (en langue moderne, cette partie fait abstraction de la nature des objets dont on considère les proportions et se retrouve proche d'une théorie qui ferait des proportions un corps et des objets un espace vectoriel sur ce corps). S'ensuit le livre VI où il traite de la similitude (de nos jours on incorpore ce concept dans l'axiomatique même des espaces vectoriels), on y trouve bien la preuve du théorème de Thalès mais toujours pas celle de la similitude des cercles. En revanche, au livre XI, on a bien un théorème sur la proportion des surfaces de polygones semblables inscrits dans des cercles, ainsi que celui de la proportion entre la surface d'un cercle et la carré de son diamètre.

Mais l'approche que je voulais souligner chez les anciens et le recours à la méthode d'exhaustion ancêtre du calcul infinitésimal. D'après Wikipédia, Archimède l'aurait utilisée avec pour séries les polygones réguliers avec 2ⁿ côtés : il part du carré inscrit puis procède par bisection de chaque angle entre des sommets consécutifs et le centre (la bissectrice c'est une construction effective).

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Il n'est quasiment jamais constructible (sauf quand n est un produit d'une puissance de deux par des nombres premiers de Fermat c'est à dire de la forme 1+2^{(2m)}).

C'est bien ce qu'il me semblait, mais je ne me souvenais plus de la condition (d'où le partiellement). Cela étant cela suffit pour avoir un processus constructif (on n'a pas besoin de tous les termes), même si ce n'est pas essentiel à mon propos.

Si on y pense bien, la preuve de l'existence de n points uniformément répartis sur le cercle n'a rien d'évident à l'aide des théorèmes de la géométrie euclidienne classique.

Ah bah si ça l'est, c'est ainsi que les géomètres grecs (dont Euclide) démontraient que le périmètre d'un cercle était proportionnel à son diamètre : par passage à la limite de Thalès sur les polygones réguliers inscrits et circonscrits au cercle. Mais n'ayant pas de moyen rationnel ou irrationnel pour évaluer le rapport, on lui donna le nom de . De mémoire (ça fait un moment que je n'ai pas lu les Éléments de Géométrie), on prouve qu'un angle est toujours subdivisible dans les proportions entières que l'on veut, puis on considère les points d'intersections avec la circonférence (par contre c'est là qu'ils admettaient inconsciemment la complétude au sens de Cauchy de leur espace).

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Pour le plaisir de digresser, je ne pense pas que qu'on puisse vraiment procéder de cette façon, parceque l'algorithme en question utilise déjà 𝜋 puisqu'on ne sait pas construire les polygones réguliers autrement qu'en disant que le polygone régulier à n côtés inscrit dans le cercle unité a pour sommets e^(2i𝜋 * k / n).

Il y a méprise sur ce que je voulais dire : c'est ainsi que l'on démontre, d'après les principes de la géométrie euclidienne, que dans celle-ci le périmètre d'un cercle est proportionnel à son diamètre. C'est-à-dire par triangulisation (les grecs anciens triangulaient tout et dans ce cas découpaient les polygones réguliers en autant de triangles que nécessaires) puis en appliquant le théorème de Thalès à chaque étape de la construction : les polygones réguliers des deux cercles sont semblables à chaque étapes et leurs périmètres sont dans la même proportion que les diamètres des cercles, il en est donc de même des périmètres des cercles. Ergo, le périmètre d'un cercle est dans un rapport constant avec son diamètre que l'on appellera . Il y a là un passage à la limite qui n'était pas totalement justifié par les anciens et qui ne fut correctement formalisé que par Cauchy (via sa notion d'espace complet) ou par Dedekin (via ses coupures). Ceci étant ce processus est (partiellement ?) constructible à la règle et au compas, donc par des procédés algébriques bien que sa limite soit transcendante.

Je ne voulais pas dire par là que cette approche fournit un algorithme effectif de calcul de implantable sur machine. C'est un peu comme quand les pythagoriciens on découvert l'irrationnalité de (ce qui foutu un sacré bordel dans leur conception du monde) et que plus tard Socrate fit résoudre le problème de la duplication du carré à un esclave ignorant dans le dialogue du Ménon : si tu n'arrives pas à décrire une procédure qui te donne la solution, montre moi la ligne qui résout le problème, à savoir la diagonale du carré :

SOCRATE — Combien de pieds a donc cet espace ?
L’ESCLAVE — Huit pieds.
SOCRATE — De quelle ligne est-il formé ?
L’ESCLAVE — De celle-ci.
SOCRATE — De la ligne qui va d’un angle à l’autre de l’espace de quatre pieds ?
L’ESCLAVE — Oui.
SOCRATE — Les savants appellent cette ligne diamètre. Ainsi, supposé que ce soit là son nom, l’espace double, esclave de Menon, se formera, comme tu dis, du diamètre.
L’ESCLAVE — Vraiment oui, Socrate.

Ménon

Là on a du Socrate cité par Platon cité par kantien sur un forum linuxfrien, mais il me semble bien que Lincoln est d'accord sur l'origine de la source. ;-)

Si tu vas lire le début du dialogue, tu verras qu'au début l'esclave propose de doubler le côté du carré, puis tente le ratio 3/2 (on se rapproche de la bonne valeur) mais voyant qu'il n'y arrivera pas, Socrate l'oriente vers la bonne réponse.

Sinon toujours dans le rapport géométrie-mathématique-informatique, l'interprétation des géométries hyperboliques dans la géométrie euclidienne par Poincaré :

Considérons un certain plan que j’appellerai fondamental et construisons une sorte de dictionnaire, en faisant correspondre chacun à chacun une double suite de termes écrits dans deux colonnes, de la même façon que se correspondent dans les dictionnaires ordinaires les mots de deux langues dont la signification est la même :

Espace. . . . . Portion de l’espace située au-dessus du plan fondamental.

Plan. . . . . Sphère coupant orthogonalement le plan fondamental.

Droite. . . . . Cercle coupant orthogonalement le plan fondamental.

Sphère. . . . . Sphère.

Cercle. . . . . Cercle.

Angle. . . . . Angle.

Distance de deux
points. . . . . Logarithme du rapport anharmonique de ces deux points et des
. . . . . . . . intersections du plan fondamental avec un cercle passant par ces deux
. . . . . . . . points et le coupant orthogonalement.
etc… etc…

Prenons ensuite les théorèmes de Lobatchevsky et traduisons-les à l’aide de ce dictionnaire comme nous traduirions un texte allemand à l’aide d’un dictionnaire allemand-français. Nous obtiendrons ainsi des théorèmes de la géométrie ordinaire.

Par exemple, ce théorème de Lobatchevsky : « la somme des angles d’un triangle est plus petite que deux droits » se traduit ainsi : « Si un triangle curviligne a pour côtés des arcs de cercle qui prolongés iraient couper orthogonalement le plan fondamental, la somme des angles de ce triangle curviligne sera plus petite que deux droits ». Ainsi, quelque loin que l’on pousse les conséquences des hypothèses de Lobatchevsky, on ne sera jamais conduit à une contradiction. En effet, si deux théorèmes de Lobatchevsky étaient contradictoires, il en serait de même des traductions de ces deux théorèmes, faites à l’aide de notre dictionnaire, mais ces traductions sont des théorèmes de géométrie ordinaire et personne ne doute que la géométrie ordinaire ne soit exempte de contradiction.

La Science et l'hypothèse, Henri Poincaré.

Bah voilà, son dictionnaire c'est analogue à un schème de compilation : il traduit les primitives d'un langage dans les primitives d'un autre avec préservation de la sémantique et, à partir de là, tous les énoncés de l'un se traduisent en un énoncé de l'autre. :-)

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Non. L'informatique, c'est juste de l'électronique

Non, l'électronique c'est juste le domaine de l'ingénierie utilisé de nos jours (rien de ne dit qu'il en serait toujours de même) pour construire des machines à calculer.

L'informatique, c'est juste de l'ébenisterie :

ah, non, en fait l'informatique c'est juste de la mécanique :

ou peut être bien de l'électronique :

ou en fait, comme le disent les anglais c'est la science du calcul ou des calculateurs (computer science). Ce qui impliquent deux choses : les principes généraux pour traiter du calcul en soi (c'est à dire les mathématiques) et les principes pour fabriquer des machines à calculer (c'est ici qu'intervient l'électronique). La première partie est une science rationnelle (i.e. non empirique) qui n'a rien à craindre de l'épreuve du temps, la seconde n'appartient que de manière contingente aux traitements automatiques de l'information (elle dépend de notre connaissance des lois de la nature — de la physique — et demain un autre champ du savoir physique pourra prendre le relais¹).

D'ailleurs le choix privilégié de la base 2, de nos jours, dans l'informatique est lié à l'électronique : ce n'est pas pour les propriétés mathématiques intrinsèques de cette base, mais pour la façon dont sont conçues les machines basées sur l'électronique que l'on utilise cette base. La pascaline, qui était mécanique, fonctionnait en base 10.

Maintenant revenons sur la représentation des nombres, avec les polygones réguliers inscrits dans un cercle :

on voit là, sur le dessin, un processus, un algorithme qui construit des polygones avec de plus en plus de côté qui se rapprocheront de plus en plus du cercle. On peut se servir de ce processus, en considérant deux cercles de même centre et en utilisant Thalès, pour prouver que le diamètre d'un cercle est proportionnel à son rayon; ce qui pourrait servir de définition au nombre ². Mais on pourrait tout aussi bien appelé le processus, l'algorithme ou le programme lui-même. C'est cette dernière solution (avec un autre processus que celui de la construction des polygones réguliers, mais l'idée est la même) qui a été retenue par Jean Vuillemin avec le développement en fractions continues dans l'article que j'ai donné en lien plus haut³. L'étude de la totalité de ces processus calculatoire, de leurs propriétés, du fait que les deux (voire trois) définitions de sont équivalentes, voilà en quoi consiste la science du calcul que l'on nomme mathématique.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Je veux un langage qui permette d'exprimer un litéral décimal.

Utilise Haskell, avec son mécanisme de type classes il a de la surcharge sur l'interprétation des littéraux.

bd = 5.5 :: Decimal

Par défaut (sans l'annotation de type) c'est de la base deux, mais avec une annotation tu peux l'interpréter dans n'importe quel type qui implante l'interface fractionnal.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Ah oui, j'avais même pas vu. Comme l'article parle d'arithmétique réelle, mes doigts ont du continuer sur leur lancée. :-P

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Tu devrais ouvrir une entrée dans le suivi, ça ressemble à un problème d'interprétation du CSS (il y a des erreurs dans la mise en page et l'insertion des images correspondant aux formules LaTeX dans le texte).

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Ce qui me désole, c'est de tout ramener à des notions de mathématiques, en faisant abstraction du besoin de millions de codeurs.

Pas le temps de développer, mais on est bien obligé de tout ramener à des notions mathématiques : l'informatique ce n'est que des maths dans le fond. Cela étant, on ne fait pas abstraction du besoin de millions de codeurs : il existe des bibliothèques de calcul à virgule fixe ou virgule flottante en base 10 pour la plupart des langages. On dit juste que si tel est son besoin alors il faut les utiliser et non passer par des flottants en base 2.

J'en ai marre de corriger toujours les mêmes bugs après toutes ces années, du code qui génère une facture dont le total n'est pas égal à la somme des lignes qui la compose, et provoque la consternation de nos clients, et crée des problèmes de réconciliation qui font perdre du temps, et créent parfois des paniques (rigolez, mais quand deux lignes de plusieurs centaines de millions d'euros ne correspondent pas exactement, et qu'en plus il n'y a pas de seuil de tolérance, y'a de la sueur sur les claviers avant de comprendre d'où ça vient).

Si le programmeur n'a pas utilisé les bons outils pour la tâche qui lui est assignée, c'est une faute professionnelle : il mérite une bonne volée de bois de vert de la part de ses supérieurs hiérarchiques (vu les conséquences de son erreur).

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Pourquoi écris-tu un "réelle" plutôt qu'un "réel" ?

Erreur de frappe, j'ai pensé réel et mes doigts ont écrit réelle. Mes doigts ils sont libres, un peu comme les pinceaux : l'autre jour je voulais peindre des enfants nus qui couraient dans un champ, à la fin je regarde la toile, et j'avais peint un pingouin ! :-P

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

La technique employée ressemble à l'arithmétique d'intervalles

C'est bien ce qu'il me semblait. Et en plus il y a un troll caché sur les brevets d'algorithmes (que ce soit logiciel ou matériel, accepter un brevet sur des algorithmes faut vraiment pas être centré :-/).

Sinon, depuis l'autre journal je suis tombé sur une approche des plus intéressantes : la représentation par fractions continues. :-) Elle est décrite dans ce rapport de recherche INRIA : Arithmétique Réelle Exacte par Fractions Continues de Jean Vuillemin (il date tout de même de 1987 ;-). L'idée étant de représenter une fraction continue, possiblement infinie, de manière finie via une continuation : vive la programmation fonctionnelle ! :-)

L'article décrit la théorie : le corps des fractions continues et deux algorithmes pour les fonctions algébriques (fractions de polynômes) et les fonctions transcendantes (exponentielle, logarithme, fonctions trigonométriques et hyperboliques) basées sur des formules de Gauss, Legendre et Lambert. C'est une approche géométrique (un réelle comme produit d'homographies) particulièrement élégante, dont voici le résumé :

Nous étudions une représentation des réelles calculables par fractions continues, qui prend en compte l'infini ∞ = 1 / O et l'indéfini ⊥ = 0 / 0. Deux algorithmes généraux sont introduits pour effectuer les opérations. L'Algorithme Algébrique, qui se particularise aux sommes et produits de fractions continues, opère de façon positionnelle, en produisant un terme du résultat par termes des paramètres. L'Algorithme transcendant, fondé sur la fraction continue de Gauss, permet le calcul d'une vaste classe de fonctions spéciales (exp, log …). Ces algorithmes ont été implantés en LeLisp, avec des performances très satisfaisantes.

« God gave us the integers. All the rest is man's work. » Leopold Kronecker

À l'époque Vuillemin en avait fait une implantation en LeLisp, mais il en existe une en Haskell présentée dans cette vidéo. Tu peux commencer par la vidéo, qui présente d'abord une autre bibliothèque Haskell basée sur une approche par intervalle en base 2 à la Cauchy¹, puis décrit plus en détail l'approche par fractions continues.

Le code Haskell est assez court (cf le lien au-dessus). Il utilise des listes plutôt que des continuations car il tire partie de l'évaluation paresseuse de Haskell. Mais avec la bibliothèque Sequence de c-cube (qui a une approche par continuation) qui vient de sortir en version 1.0 combinée avec la bibliothèque Zarith, on doit pouvoir faire cela facilement en OCaml.

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

Merci.

De rien. La prochaine fois que tu veux calculer une entropie de mot passe, si tu n'as pas en tête les puissances de 2, tu sors ton python et tu fais :

>>> import math
>>> math.log(143 * 304 * 1977 * 143 * 304, 2)
41.76469485617316

voilà, l'entropie avec tes listes est de 41.76. ;-)

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.

L'entropie est de l'ordre de 40 bits.

143 ~ 2^7, 1977 ~ 2^11 et 304 ~ 2^8, d'où un couple adjectif+nom donne une entropie de l'ordre de 15 (=7 + 8) bits, deux tels couples donnent une entropie de 30, plus les 11 pour le verbe, on arrive aux alentours de 40 (du même ordre que dans le xkcd : 4 parmi 2^11 possibilités soit 4 * 11 = 44 bits d'entropie).

Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.