#! /usr/bin/python3
#! C:\Python25\python.exe
# -*- coding: utf-8 -*-
# interet de ce programme : etude
# Bezout : PGCD(a, b) = a u + b v
# il existe alpha et beta de Z tels que PGCD(a,b) = alpha a + beta b
# premier   passage : a = b q0 + r0
# deuxieme  passage : b = r0 q1 + r1
# troisieme passage : r0 = r1 q2 + r2
# . . .
# dernier   passage : r_{n-1} = r_{n} q_{n+1} + r_{n+1} (avec r_{n+1}=0)
#

import sys
import os
import math

sin_s1u_carre_min = 2.
passage = 0

def fibonacci(nmax) :
    Usage = """
#############################################################
# Fibonacci : u(n+2) = u(n+1) + u(n)
#############################################################
"""
    print(Usage)
    u = [1, 1]
    for n in range(2, nmax) :
        u += [ u[n-2] + u[n-1] ]
    print("u=", u)
    return u
    
def division ( a, b ) :
    """ division Euclidienne """
    q = a // b
    r = a - b * q
    return ( q, r )

def bezout ( a , b ) :
    """ coefficients de Bezout """
    Principe = """
#########################################################################
# Calcul de l'identité de Bezout : PGCD = a u + b v
# J'exprime les restes successifs dans la base (a, b) :
# r0 = 1.a + 0.b = a
# r1 = 0.a + 1.b = b
# puis la boucle :
#   r0 = r1  q + r2
#   (1.a + 0.b) = q (0.a + 1.b) + r2  =>  r2 = (1.a + (-q).b)
#   . . .
#   (x.a + y.b) = q (z.a + t.b) + r2  =>  r2 = ((x-qz).a + (y-qt).b)
#########################################################################
"""
    print(Principe)
    print("a=",a,"b=",b)
    # décomposition dans la base (a, b) : r = alpha a + beta b
    r0 = [ 1 , 0 ] # = a
    r1 = [ 0 , 1 ] # = b
    for i in range(100) :
        # r0 = r1 q + r2
        ( q , r ) = division ( r0[0]*a + r0[1]*b , r1[0]*a + r1[1]*b )
        print("(q=", q, ", r=", r, end=") ")
        if r == 0 :
            print()
            print("PGCD(",a,",",b,")=",r1[0]*a + r1[1]*b, end=" ")
            print("=",r1[0],"*",a,"+",r1[1],"*",b)
            break
        # r2 = r0 - r1 q
        r2 = [ r0[0] - r1[0]*q , r0[1] - r1[1]*q ]
        print("r2=", r2)
        # bascule
        r0 = r1
        r1 = r2

def main ( ) :
    f = fibonacci(20)
    # sequence la plus longue de l'algorithme d'Euclide
    #  pour 2 nombres de Fibonacci successifs
    bezout ( f[17], f[16] )
    # PGCD :
    # bezout ( 732, 852 )
    
main ( )