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 Cauchy1, 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.
j'ai d'ailleurs été étonné que l'orateur ait du expliquer à son auditoire ce qu'était une suite de Cauchy. :-o ↩
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.
[^] # Re: Il faut bien lire ce qu'on lit!
Posté par kantien . En réponse au journal Le retour de la vengeance de la virgule flottante. Évalué à 8.
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é :
À 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 Cauchy1 , 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.0combinée avec la bibliothèque Zarith, on doit pouvoir faire cela facilement en OCaml.j'ai d'ailleurs été étonné que l'orateur ait du expliquer à son auditoire ce qu'était une suite de Cauchy. :-o ↩
Sapere aude ! Aie le courage de te servir de ton propre entendement. Voilà la devise des Lumières.