Les fractions continues constituent une notion plutôt intéressant en mathématiques. C’est une façon d’écrire les nombres. Dans cet article, je vais expliquer dans les grandes lignes la notion mathématique et dans un second temps, nous allons implémenter en Python une classe permettant de représenter une fraction continue et d’en obtenir sa valeur fractionnaire.
Fractions continues du point de vue mathématique
Un exemple en partant d’une équation
Partons de l’équation : $$x^2-x-1=0,$$ que l’on peut facilement résoudre à l’aide de la théorie des équations du second degré. On trouve alors deux solutions notées:$$\varphi = \frac{1+\sqrt5}{2}>0$$et$$\overline{\varphi}=\frac{1-\sqrt5}{2}<0.$$
Partons de cette équation pour arriver à l’écriture:$$x^2=x+1$$et, en supposant que \(x>0\) et en divisant les deux membres par \(x\):$$x = 1 + \frac{1}{x}.$$Cette dernière égalité signifie donc que:$$\varphi=1+\frac{1}{\varphi}$$ car nous avons supposé \(x>0\) et que la seule solution strictement positive est \(\varphi\).
En remplaçant le \(\varphi\) de droite par ce à quoi il est égal, à savoir \(\displaystyle 1+\frac{1}{\varphi}\), on a l’égalité:$$\varphi=1+\frac{1}{1+\frac{1}{\varphi}}.$$On voit alors que l’on peut répéter cette action une infinité de fois pour arriver à:$$\varphi=1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{\cdots}}}}.$$Cette dernière écriture de \(\varphi\) est appelée sa fraction continue. Dans le cas présent, la fraction continue est infinie, mais c’est parce que \(\varphi\) n’est pas rationnel : il ne s’écrit pas sous la forme \(\displaystyle\frac{p}{q}\), où p et q sont deux entiers. En effet, on arrive à montrer le résultat suivant :
Une écriture en fraction continue finie représente un nombre rationnel.
Ce résultat va être utile pour notre classe Python future.
Obtenir la fraction continue finie d’un nombre rationnel
Posons:$$x=\frac{15\;872}{7\;355}.$$Appliquons l’algorithme d’Euclide aux numérateur et dénominateur:
15 872 = 2 x 7 355 + 1 162 7 355 = 6 x 1 162 + 383 1 162 = 3 x 383 + 13 383 = 29 x 13 + 6 13 = 2 x 6 + 1 6 = 6 x 1 + 0
De la première ligne, on peut écrire:$$\frac{15\;872}{7\;355}=2+\frac{1\;162}{7\;355}.$$Mais de la deuxième ligne, on peut écrire:$$\frac{7\;355}{1\;162}=6+\frac{383}{1\;162}$$donc:$$\frac{15\;872}{7\;355}=2+\frac{1}{6+\frac{383}{1\;162}}.$$Par un raisonnement similaire, en continuant ainsi, on arrive à:$$\frac{15\;872}{7\;355}=2+\frac{1}{6+\frac{1}{3+\frac{1}{29+\frac{1}{2+\frac{1}{6}}}}}.$$L’écriture d’une telle fraction continue est allégée en écrivant:$$\frac{15\;872}{7\;355}=[2,6,3,29,2,6].$$Les nombres entre les crochets ne sont autres que les quotients successifs dans l’algorithme d’Euclide.
Nous voyons bien que pour un nombre rationnel, la fraction continue ne peut être que finie dans la mesure où l’algorithme d’Euclide est lui-même fini.
Pour une fraction continue infinie, comme \(\varphi\), on adoptera la notation suivante:$$\varphi=[\overline{1}].$$ On surmonte d’une barre ce qui se répète à l’infini. Cela peut donc être aussi:$$[1,4,\overline{7,3}] = 1+\frac{1}{4+\frac{1}{7+\frac{1}{3+\frac{1}{7+\frac{1}{3+\cdots}}}}}.$$
Fractions continues : implémentation en Python
Nous allons ici créer une classe Frac_cont.
Le constructeur
Cette classe devra admettre une instance de type list ou de type Fraction, en ayant au préalable importé le module fractions. En effet, je veux:
- à partir d’une liste, obtenir la fraction correspondante;
- à partir d’une fraction, obtenir la liste correspondante.
Mais si l’instance est une liste, il faut aussi voir s’il y a répétition d’une séquence (comme pour \(\varphi\)). Il me faut alors penser à créer une autre classe d’objet représentant cette répétition. Je vais nommer cette classe Rep qui va faire en sorte de retourner une liste composée d’un certain nombre de répétitions de la séquence (par exemple Rep([1] , 100).liste() retournera une liste de 100 “1”.
class Frac_cont():
def __init__(self , instance):
if isinstance(instance,list):
if isinstance(instance[-1] , Rep):
N = instance[-1].liste()
instance.pop()
instance.extend( N )
self.ma_liste = instance
self.fraction = None
if isinstance(instance,Fraction):
self.fraction = instance
self.ma_liste = NoneLa ligne 3 signifie que si instance est de type Rep alors on construit une liste N constituée d’un certain nombre de fois la séquence à répéter, on enlève le dernier élément de l’instance (l’objet de type Rep) à l’aide de la méthode pop, et on le remplace par la liste N.
À ce stade, il est normal de ne pas trop bien comprendre où je veux en venir. Il faut avoir une vue globale de la classe.
Une méthode pour convertir une liste en fraction
def simplify(self):
if self.ma_liste is not None:
counter = 0
for i in self.ma_liste[::-1]:
if i == 0:
print('Error: number must be different from 0.')
break
if counter == 0:
result = Fraction(i,1)
counter += 1
else:
result = Fraction(i,1) + Fraction(1,result)
return result
else:
print('The instance of object Frac_cont must be a list.')Je commence cette méthode par vérifier si mon instance de classe n’est pas une fraction (auquel cas la méthode retourne une erreur, en anglais pour faire plus class(e)…).
La ligne 4 boucle sur la liste mise à l’envers. En effet, pour calculer la fraction, je dois partir de la liste depuis la fin vers le début. La logique se trouve en ligne 13 : à chaque étape, je dois inverser la fraction déjà obtenue à l’étape précédente et je dois lui ajouter le nombre de la liste sur lequel je suis.
Une méthode pour retourner le nombre décimal correspondant à une liste
def decimal(self):
return float( self.simplify() )Rien de bien sorcier ici. Une fois la méthode simplify implémentée, il suffit de retourner le flottant correspondant à la fraction trouvée.
Une méthode pour trouver la liste correspondant à une fraction
def liste(self):
if self.fraction is not None:
L = []
f = self.fraction
a , b = f.numerator , f.denominator
if a < b:
a, b = b, a
while b != 0:
a, b , q = b, a % b , a // b
L += [ q ]
return L
else:
print('The instance of object Frac_cont must be a Fraction.')La ligne 2 sert à vérifier que l’instance est bien une fraction (si tel n’est pas le cas, on retourne un message d’erreur en anglais).
Dans cette méthode, on se sert de l’algorithme d’Euclide (lignes 5 à 11).
Le bilan
Et voilà ! Notre classe est prête. Nous allons la tester… On entre d’abord une liste pour en avoir sa fraction:
>>> Frac_cont([2,3,1,1,9,1,1,48]).simplify()
15625/6842
Maintenant, partons d’une fraction pour en avoir son développement en fraction continue:
>>> Frac_cont( Fraction(63529,1252) ).liste()
[50, 1, 2, 1, 7, 13, 3]
Testons maintenant avec une liste où une séquence est répétée:
>>> Frac_cont( Rep([1]) ).decimal()
1.6180339985218033
qui correspond bien à une valeur approchée du nombre d’or \(\varphi\).
Fractions continues en Python : le programme complet
Trouvez le programme complet, y compris la classe Rep(), ci-dessous:
