San Vu Ngoc - IRMAR

Initialisations¶

In [1]:
%matplotlib inline
# inline can be replaced by notebook to get interactive plots
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as img
import matplotlib.cm as cm
import matplotlib.colors as colors
In [2]:
plt.rcParams['figure.figsize'] = (20.0, 12.0) # set figures display bigger

Reste de la division de i par j¶

In [3]:
n=100
R = np.zeros((n,n))
for i in range(1, n):
        for j in range(0, n):
            R[i,j] = j % i + 1  # on ajoute 1 pour pouvoir faire 
                                # une échelle de couleurs logarithmique
In [4]:
plt.imshow(R, interpolation='none', cmap=cm.Spectral, norm=colors.LogNorm(1,n))
plt.colorbar()
Out[4]:
<matplotlib.colorbar.Colorbar at 0x7f26f63ff700>
In [5]:
Top = R[1:20,::]
plt.imshow(Top, interpolation='nearest', cmap=cm.Spectral, norm=colors.LogNorm(1,n))
Out[5]:
<matplotlib.image.AxesImage at 0x7f26edbd5780>

Algorithme d'Euclide pour le pgcd¶

Euclide1521.svg

On fait ici le cas $a\geq 0$ et $b\geq 0$. À adapter pour le cas général !

L'algorithme est récursif. Il suffit de programmer deux étapes, qui correspondent à l'initialisation et l'hérédité dans le principe de récurrence.

  1. l'initialisation: En fait, en programmation récursive on appelle plutôt ça la terminaison: c'est ce qui permet d'assurer que le programme ne va pas tourner indéfiniment: "Si b=0, alors le pgcd(a,b) est a"

  2. l'hérédité: Pour calculer pgcd(a,b), avec $a\geq b$, on se ramène à des entiers "plus petits" grâce à la formule pgcd(a,b) = pgcd(b,r) où r est le reste de la division euclidienne de a par b.

    Si jamais $a<b$ ce n'est pas grave car la méthode ci-dessus va appeler la fonction pgcd(b,a) ! (et ensuite, le problème ne se posera plus car $r<b$).

Important: Pour utiliser une méthode récursive, il faut démontrer que la notion de "plus petits" utilisée dans l'hérédité finit bien par aboutir à l'étape de terminaison en un nombre fini d'itérations...
Ici on sait que $r<b\leq a$. Donc $\min(b,r)\leq \min(a,b) - 1$. Donc au pire au bout de $N$ étapes avec $N=\min(a,b)$, on sait que le "reste" $r$ sera nul.

In [6]:
def pgcd (a,b):
    if b == 0:
        return a  
    else:
        return pgcd(b, a % b)
In [7]:
pgcd(7,123)
Out[7]:
1
In [8]:
pgcd(600,124)
Out[8]:
4
In [9]:
pgcd(12,0), pgcd(0,0), pgcd(0,12)
Out[9]:
(12, 0, 12)
In [10]:
pgcd(1234,2022)
Out[10]:
2

La version 'originale' d'Euclide avec seulement des soustractions¶

In [11]:
def pgcdEuclide (a,b):
    if b == 0:
        return a  
    elif a < b:
        return pgcdEuclide (b,a)
    else:
        return pgcdEuclide(b, a - b)
In [12]:
pgcdEuclide(600,124)
Out[12]:
4
In [13]:
pgcdEuclide(1234,2020), pgcdEuclide(0,12), pgcdEuclide(0,0)
Out[13]:
(2, 12, 0)

Version non récursive¶

Les algorithmes récursifs sont très pratiques lorsqu'on peut raisonner par récurrence. Mais, en python, ils ne sont pas optimisés, il demandent davantage de mémoire (mémoire de pile ou stack) et ne sont donc pas adaptés pour un grand nombre d'itérations (en gros supérieur à 1000).

(Pour le pgcd ce n'est pas très grave car l'algorithme d'Euclide est très efficace: peu d'itérations même pour des entiers très grands, cf. ci-dessous. Il faudrait des nombres avec plus de 200 chiffres pour que ça plante...)

In [14]:
pgcd(9896667081063042353430215182058733503146666634384944373401765774819916952466570536757090685909051250971877555701522243102171464782938632257729627142425602168458229597715225909882920542638682441199086679, 16013143712502213357018698163653060025603471927161902106364041769343651616369837753524801567948803360284511232110892962053473043906000050639883022618085781173913128777782344520942246774419401664791597285)
Out[14]:
1
In [15]:
a=410615886307971260333568378719267105220125108637369252408885430926905584274113403731330491660850044560830036835706942274588569362145476502674373045446852160486606292497360503469773453733196887405847255290082049086907512622059054542195889758031109222670849274793859539133318371244795543147611073276240066737934085191731810993201706776838934766764778739502174470268627820918553842225858306408301661862900358266857238210235802504351951472997919676524004784236376453347268364152648346245840573214241419937917242918602639810097866942392015404620153818671425739835074851396421139982713640679581178458198658692285968043243656709796000
a
Out[15]:
410615886307971260333568378719267105220125108637369252408885430926905584274113403731330491660850044560830036835706942274588569362145476502674373045446852160486606292497360503469773453733196887405847255290082049086907512622059054542195889758031109222670849274793859539133318371244795543147611073276240066737934085191731810993201706776838934766764778739502174470268627820918553842225858306408301661862900358266857238210235802504351951472997919676524004784236376453347268364152648346245840573214241419937917242918602639810097866942392015404620153818671425739835074851396421139982713640679581178458198658692285968043243656709796000
In [16]:
b=664390460366960072280217847866028384244163512452783259405579765542621214161219257396449810982999820391132226802809465132446349331994409434926019045342723749188530316994678473551320635101099619382973181622585687336939784373527897555489486841726131733814340129175622450421605101025897173235990662770203756438786517530547101123748849140252686120104032647025145598956675902135010566909783124959436469825558314289701354227151784602865710780624675107056569822820542846660321813838896275819753281371491809004412219124856375121694811728724213667814577326618521478357661859018967313354840178403197559969056510791709859144173304364898001
b
Out[16]:
664390460366960072280217847866028384244163512452783259405579765542621214161219257396449810982999820391132226802809465132446349331994409434926019045342723749188530316994678473551320635101099619382973181622585687336939784373527897555489486841726131733814340129175622450421605101025897173235990662770203756438786517530547101123748849140252686120104032647025145598956675902135010566909783124959436469825558314289701354227151784602865710780624675107056569822820542846660321813838896275819753281371491809004412219124856375121694811728724213667814577326618521478357661859018967313354840178403197559969056510791709859144173304364898001
In [17]:
pgcd(a,b)

---------------------------------------------------------------------------
RecursionError                            Traceback (most recent call last)
/tmp/ipykernel_55354/3477558028.py in <module>
----> 1 pgcd(a,b)

/tmp/ipykernel_55354/2671587030.py in pgcd(a, b)
      3         return a
      4     else:
----> 5         return pgcd(b, a % b)

... last 1 frames repeated, from the frame below ...

/tmp/ipykernel_55354/2671587030.py in pgcd(a, b)
      3         return a
      4     else:
----> 5         return pgcd(b, a % b)

RecursionError: maximum recursion depth exceeded in comparison
In [ ]:
def pgcdI (a,b):  # version "itérative"
    while b != 0:
        (a, b) = (b, a % b)
    return a
In [ ]:
pgcdI(1234,2020), pgcdI(12,18), pgcdI(7,123), pgcdI(0,12)
In [ ]:
pgcdI(a,b)
In [ ]:
a,b

Question: d'ou viennent ces nombres ??¶

Images¶

Tracé du pgcd¶

Rappel: on a tracé la semaine dernière la relation "i divise j". Maintenant on regarde le "graphe" de "pgcd(i,j)".

In [18]:
def GCD (n):
    T = np.zeros((n,n))
    for i in range(0, n):
        for j in range(0, n):
            T[i,j] = pgcdI(j,i)
    return T
In [19]:
plt.imshow(GCD(100), interpolation='none', cmap=cm.Spectral)
plt.colorbar()
#img.imsave('pgcd-log1000.png', GCD(1000), cmap=cm.Spectral)

---------------------------------------------------------------------------
NameError                                 Traceback (most recent call last)
/tmp/ipykernel_55354/904313813.py in <module>
----> 1 plt.imshow(GCD(100), interpolation='none', cmap=cm.Spectral)
      2 plt.colorbar()
      3 #img.imsave('pgcd-log1000.png', GCD(1000), cmap=cm.Spectral)

/tmp/ipykernel_55354/437753363.py in GCD(n)
      3     for i in range(0, n):
      4         for j in range(0, n):
----> 5             T[i,j] = pgcdI(j,i)
      6     return T

NameError: name 'pgcdI' is not defined

Nombre d'itérations de l'algorithme d'Euclide¶

On compte le nombre de divisions euclidiennes

In [20]:
def pgcdIter (a,b):
    r = a % b
    if r == 0:
        return 1
    else:
        return 1 + pgcdIter(b,r)
    
def pgcdIterI (a,b):  # version "itérative"
    n = 0
    while b != 0:
        (a, b) = (b, a % b)
        n = n + 1
    return n
In [21]:
pgcdIter(100,1), pgcdIterI(100,1)
Out[21]:
(1, 1)
In [22]:
pgcdIter(1234,2020), pgcdIterI(1234,2020)
Out[22]:
(9, 9)
In [23]:
def ITER (n):
    T = np.zeros((n,n))
    for i in range(1, n-1):
        for j in range(1, n-1):
            T[i,j] = pgcdIter(j,i)
    return T
In [24]:
%matplotlib notebook
plt.rcParams['figure.figsize'] = (12.0, 7.0) # set figures display bigger
plt.imshow(ITER(100), interpolation='none', cmap=cm.gist_earth)
plt.colorbar()
Out[24]:
<matplotlib.colorbar.Colorbar at 0x7f26ed898640>
In [25]:
100/62
Out[25]:
1.6129032258064515

On note ici quelques couples (i,j) où le nombre de divisions effectués par l'algo semble élevé...

(55,89) (13,21) (34,55) (610, 987)

Que sont ces nombres ???

In [26]:
ar=ITER(1000)
%matplotlib inline
plt.rcParams['figure.figsize'] = (20.0, 12.0) # set figures display bigger
plt.imshow(ar, cmap=cm.gist_earth)
plt.colorbar()
#img.imsave('image1000.png', ar, cmap=cm.gist_earth)
Out[26]:
<matplotlib.colorbar.Colorbar at 0x7f26ed8d8a00>
In [27]:
plt.imshow(ITER(1000), cmap=cm.Spectral)
plt.colorbar()
#img.imsave('image1000-2.png', ar, cmap=cm.Spectral)
Out[27]:
<matplotlib.colorbar.Colorbar at 0x7f26ee200190>
In [29]:
Top = ar[1:200,::]
plt.imshow(Top, interpolation='nearest', cmap=cm.gist_earth)
Out[29]:
<matplotlib.image.AxesImage at 0x7f26ee1056c0>
In [30]:
pgcdIter(546,337)
Out[30]:
12
In [31]:
pgcdIter(377,610)
Out[31]:
14
In [32]:
pgcdIter(55,89)
Out[32]:
10
In [ ]: