Le type entier.

On retiendra que l'on peut tester si un résultat est considéré comme un entier par Maple:

>	type(25,integer);whattype(1515);

Notons que l'on tester la positivité stricte par l'expression:

>	type(0,posint);

la positivité au sens large par:

>	type(0,nonnegint);

Et l'on a noté que la commande "issqr" permet de détecter les carrés parfaits:

>	issqr(25);issqr(54);

Les opérations de base.

Les opérations de base sur les entiers sont "+", "-", "*", "^", "iquo", "irem", "abs" et "!" se passent pratiquement de commentaires: la division euclidienne est donc définie dans Maple comme "iquo" et "irem" ("Integer quotient" et "Integer remainder").

>

>	iquo(1515,732);irem(1515,732);732*iquo(1515,732)+irem(1515,732);

Une pause mathématique.

A ce point de la feuille, introduisons quelques possibilités supplémentaires de Maple. On peut rappeler le dernier résultat obtenu par Maple par:

>

%

Warning, premature end of input

Oh, pardon! J'ai oublié le sacro-saint ; qui indique à Maple que l'on a terminé d'entrer les données.

>

%;

Vous voyez sur cet exemple qu'il s'agit de la dernière expression que Maple a su interpréter. Il y a donc souvent risque d'ambiguïté à utiliser cet opérateur (particulièrement si vous ne travaillez pas de façon linéaire dans votre feuille). Le mieux est donc de s'abstenir de recourir à %. Il est beaucoup plus raisonnable de baptiser les expressions dont on aura un usage ultérieur:  à ce propos on notera l'usage de l'opérateur :=

>	monbazar:=2001^2-1515^3;

Il s'agit donc de l'opérateur d'affectation qui permet de stocker un résultat et de lui attribuer un nom pour pouvoir le réutiliser dans la suite de nos opérations. Il convient bien entendu de ne pas le confondre avec "=" .

Booléens et opérateurs admissibles.

Nous avons déjà introduit les valeurs booléennes (avec la fonction "type"). Il reste à parler des opérateurs booléens et des opérateurs de comparaison dont les valeurs sont naturellement booléennes.

On retiendra les opérateurs de comparaison <, <=, >,  >=,  <> et  = et les opérateurs booléens "and", "or" et " not":

>	2>3;evalb(%);machin:=3>10;evalb(machin);truc:=2=2;

Vous vous posez peut être des questions sur "evalb"? La commande qui suit:

>

?evalb;

affiche donc une fenêtre de l'aide en ligne de Maple. C'est le moment d'avoir un souvenir ému des quelques huit années passées en collège et en lycée à apprendre l'anglais...

Rappel.

Nous avons donné l'algorithme suivant. Soient a et b deux entiers, b étant strictement positif. Soit (h,k) un couple que nous allons initialiser à (a,0) . Si h est supérieur ou égal à b, nous remplaçons (h,k) par (h-b,k+1); si h est strictement inférieur à 0, nous remplaçons (h,k) par (h+b,k-1); enfin si 0<=h<b, l'algorithme est terminé et h représente le reste et k le quotient.

Division euclidienne.

Au vu de l'algorithme (il est présenté sous la forme "tant que h<0 ou h>=b"), il est naturel d'utiliser l'instruction "while":

>	div_eucl:=proc(a,b) local h,k; h:=a;k:=0; while (h<0) or (h>=b) do if h<0 then h:=h+b;k:=k-1;else h:=h-b;k:=k+1;end if; end do; return (k,h) end proc:

>	div_eucl(2001,1515);div_eucl(1515,5);

On peut aussi songer à une écriture "récursive", c'est à dire que la procédure fasse appel à elle-même:

>	div_eucl2:=proc(a,b) local quo_reste; quo_reste:=proc(x,y) global h,k;h:=x;k:=y; if h<0 then return quo_reste(h+b,k-1); elif h>=b then return quo_reste(h-b,k+1) else end if; return (k,h) end proc; return quo_reste(a,0); end proc:

>	div_eucl2(2001,1515);div_eucl2(1515,5);

Comme vous le voyez, la procédure est moins lisible mais démontre que l'on peut définir une procédure à l'intérieur d'une autre procédure et elle met en évidence l'usage de variables globales (c'est à dire dont le contenu survit à l'exécution de la prodédure: il nous faut ici garder trace des modifications successives de l'entier à diviser et de son quotient).

Enfin on peut aussi écrire:

>	div_eucl3:=proc(a,b,c) local h,k; h:=a;k:=c; if h<0 then return div_eucl3(h+b,b,k-1); elif h>=b then return div_eucl3(h-b,b,k+1) else return (k,h) end if; end proc:

>	div_eucl3(2001,1515,0);div_eucl3(1515,5,0);

L'inconvénient de cette version est alors que l'on doit mettre 0 comme "quotient" lors du premier appel.....

Dernier commentaire. On peut imposer un type aux paramêtres entrants:

>	div_eucl4:=proc(a::integer,b::posint) local h,k; h:=a;k:=0; while (h<0) or (h>=b) do if h<0 then h:=h+b;k:=k-1;else h:=h-b;k:=k+1;end if; end do; return (k,h); end proc:

>	div_eucl4(-1.,6);div_eucl4(1515,0);div_eucl4(2001,1515);

Error, invalid input: div_eucl4 expects its 1st argument, a, to be of type integer, but received -1.

Error, invalid input: div_eucl4 expects its 2nd argument, b, to be of type posint, but received 0

Rappel.

On a pgcd(a,b)=pgcd(|a|,|b|); ensuite si a>=b pgcd(a,b)=pgcd(a-b,b) et sinon pgcd(a,b)=pgcd(a,b-a) ; l'algorithme se terminant lorsque l'un des deux entiers est nul (le pgcd étant l'autre élément du couple).

Algorithme d'Euclide.

Aucun problème à l'écriture de cette procédure:

>	pgcd:=proc(a::integer,b::integer) local h,k; h:=max(abs(a),abs(b));k:=min(abs(a),abs(b)); if b>0 then return pgcd(h-k,k) else return h end if; end proc:

>	pgcd(2001,1515);pgcd(1000,29);

Algorithme "binaire".

Vous vous rappelez qu'il s'agit de

- chercher la plus grande puissance de 2 commune à a et b; diviser a et  b par cette puissance (garder cette puisssance de 2 dans le pgcd); on est alors ramené à un couple d'entiers dont l'un est impair; sans changer leur pgcd, on peut remplacer celui qui est pair par sa moitié jusqu'à ce que l'on obtienne un nombre impair. Alors pgcd(impair1,impair2)=pgcd(impair1-impair2,impair2)

si impair1 est plus grand que impair2;

et l'on continue jusqu'à ce que l'un des éléments du couple soit nul.

Notez l'existence de:

>

5 mod 2;

Bien entendu l'idéal est alors de comparer les temps de calcul de vos deux algorithmes sur des entiers un peu grands (je vous ai donné des nombres de Fermat). On pourra utiliser:

>

?time;

>	Binaire := proc(a::integer, b::integer)

>	local A, B, i;

>	A:=abs(a);

>	B:=abs(b);    i:=0;

>	while (A mod 2 = 0 and B mod 2 = 0) do

>	A := iquo(A, 2);

>	B := iquo(B, 2);         i:=i+1;

>

end do;

>	while (A <> 0) and (B <> 0) do

>	while (A mod 2 =0) or (B mod 2 =0) do

>	if (A mod 2 = 0) then A := iquo(A, 2);

>	else B := iquo(B, 2);

>

end if;

>

end do;

>	if A >= B then A := A - B;

>	else B := B - A;

>

end if;

>

end do;

>	if B = 0 then return 2^i*A;

>	else return 2^i*B;

>

end if;

>

end proc:

>	Binaire(12, 18);

>	Binaire(5, 9);

>	Binaire(21, 28);

Algorithme étendu.

Commençons par en rappeler le principe. Soient a>=b >0 deux entiers dont on cherche le pgcd et une identité de Bezout. On a introduit les suites a_i (initialisée par a_0:=a et a_1:=b), u_i (initialisée par u_0:=1 et u_1:=0) et v_i  (initialisée par v_0:=0 et v_1:=1) par les opérations suivantes: a_(i):=q_(i+1)a_(i+1)+a_(i+2); u_(i+2):=u_i - q_(i+1)a_(i+1) et v_(i+2):=v_i - q_(i+1)v_(i+1) . Alors l'identité u_i a + v_i b = a_i est toujours vérifiée.

On va donc travailler avec les données (A,U,V,B,W,Z) initialisées à (a,1,0,b,0,1) (si a>=b) que l'on remplace par (B,W,Z,A - QB,U - QW,V - QZ) où Q est le quotient (entier !) de A par B jusqu'à ce que A ou B soit nul.

>	bezout:=proc(a::integer,b::integer) local h,k,l,q,u1,u2,u3,v1,v2,v3; h:=max(abs(a),abs(b));k:=min(abs(a),abs(b));u1:=1;u2:=0;v1:=0;v2:=1; while k >0 do l:=h;h:=k;q:=iquo(l,h);k:=l-q*h; u3:=u1;u1:=u2;u2:=u3-q*u1; v3:=v1;v1:=v2;v2:=v3-q*v1; end do; return (h,u1,v1); end proc:

>	result:=bezout(2001,1515);result[2]*2001+result[3]*1515;

Comparons avec la commande ad hoc de Maple:

>	igcd(2001,1515);igcdex(2001,1515,alpha,beta);alpha;beta;

>