Licence de Mathématiques L3 Algèbre effective

pages

Français

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

Découvre YouScribe et accède à tout notre catalogue !

Je m'inscris

pages

Français

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

thieg

Langue

Français

Niveau: Supérieur, Licence, Bac+3
Licence de Mathématiques 2008--2009 L3 Algèbre effective td 2 : Inversibles modulo m, Calcul rapide de puissances Inversibles modulo m Calcul rapide de puissances Dans la suite on aura besoin de calculer des puissances modxn m avec , ,x n m entiers de grande taille. On a donc besoin d'un algorithme de calcul efficace. Exercice 6 : écrire une fonction qui rende xn en utilisant l'algorithme de calcul rapide de puissances expliqué en cours. Comparer graphiquement la vitesse de l'algorithme naïf par multiplications successives et de celui-ci. Solution > exponaif:=proc(x,n) local i,res; res:=1; for i from 1 to n do res:=res*x od; res end; exponaif := proc( ) end proc,x n local ;,i res ; ; := res 1 for to do end doi n := res ?res x res On initialise res à 1 et non à x pour que cette fonction marche quand n = 0. > exponaif(11,3),exponaif(11,0); ,1331 1 L'algorithme rapide : > exporap:=proc(x,n) if n=0 then 1 elif irem(n,2)=0 then exporap(x*x,iquo(n,2)) else x*exporap(x*x,iquo(n-1,2)) fi end; exporap ,x nproc( ) := =n 0 1if then =( )irem ,n 2

puissances modulo

then

vitesse de l'algorithme naïf par multiplications successives

vitesse de l'algorithme de l'exercice

algorithme de calcul rapide de puissances

exponaif:=proc

elif irem

Voir

Publié par

thieg

Langue

Français

Licence de Mathématiques 2008--2009

L3 Algèbre effective

td 2 : Inversibles modulo m, Calcul rapide de puissances

Inversibles modulo m

Calcul rapide de puissances

Dans la suite on aura besoin de calculer des puissances

mod

avec ,

x n m

entiers de grande

taille. On a donc besoin d’un algorithme de calcul efficace.

Exercice 6 : écrire une fonction qui rende

en utilisant l’algorithme de calcul rapide de

puissances expliqué en cours.

Comparer graphiquement la vitesse de l’algorithme naïf par multiplications successives et de

celui-ci.

Solution

exponaif:=proc(x,n)

local i,res;

res:=1;

for i from 1 to n do res:=res*x od;

res

end;

exponaif

proc

(

)

end proc

x n

local

;

i res

;

res

for

end do

res

res x

res

On initialise res à 1 et non à x pour que cette fonction marche quand n = 0.

exponaif(11,3),exponaif(11,0);

1331 1

L’algorithme rapide :

exporap:=proc(x,n)

if n=0 then 1

elif irem(n,2)=0 then exporap(x*x,iquo(n,2)) else

x*exporap(x*x,iquo(n-1,2)) fi

end;

exporap

x n

proc

(

)

then

(

)

irem

(

)

exporap

(

)

iquo

elif

then

(

)

exporap

(

)

iquo

1 2

else

end if

end proc

Les mesures :

s1:=NULL: for i to 10 do t:=time(): exponaif(11,3^i):

t:=time()-t: s1:=s1,[i,t] od: s1;

[

]

1 0.016

[

]

2 0.009

[

]

3 0

[

]

4 0

[

]

5 0.008

[

]

6 0.035

[

]

7 0.310

[

]

8 2.385

[

]

9 21.383

[

]

10 191.275

Voir