Calcul d'une décomposition en fractions égyptiennes
-
Approximation :
- algorithme glouton ;
- algorithme glouton à dénominateurs impairs
la décomposition existe, mais on n'a pas prouvé que l'algo termine.
- Résolution de conflits :
- par découpage
on remplace 2/y par 1/y + 1/(y+1) + 1/(y(y+1)),
la preuve de terminaison est compliquée ;
- par mariages
on remplace 2/y par 2/(y+1) + 2/(y(y+1)), ce qui
diminue la suite des termes selon l'ordre lexicographique.
- Décomposition binaire
- écriture binaire
avec une décomposition de période b,
le début non répétitif donne des fractions 1/2a
et la séquence répétitive des fractions 1/2a(2b-1) ;
- Bezout binaire
si (x2k mod y)<2k+1, par exemple y<2k+1,
on cherche r, s tels que
x 2k = s y + r. Alors l'écriture binaire permet de
représenter r/2k et s/2k comme
somme d'inverses de puissances de 2.
Et x/y = s/2k + r/2k y.
NB: tous les dénominateurs sont pairs.
- Fractions continues
- Gloutonnes réverses
- Force brute
- Petits numérateurs
Page de D. Eppstein