Fractions continues en Python

Fractions continues en Python

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 en Python
Fractions continues en Python

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 voir 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 (j’en parlerais plus tard) 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 = None

La 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

Les abonné.e.s à mathweb.fr pourront trouver le programme complet sur cette page, y compris la classe Rep().

Stéphane Pasquet
Stéphane Pasquet

Laissez votre message

Supportscreen tag