Philippe.Dumas@inria.fr


http://algo.inria.fr/dumas/Maple/

Retour en page principale Table des matières Index

Maple V.4 worksheet, Maple V.5 worksheet,

Reprenons d'abord le code fourni à la page 106 à titre de comparaison.

> is149:=proc(n::posint)

    local r;

    r:=n;

    while r<>0 do

      if not member(irem(r,10,'r'),{1,4,9}) then

        RETURN(false)

      fi

    od;

    true

  end:

> tricol:=proc(N)

    local k,res,q,r,n,i;

    k:=0;

    for q from 0 by 10 while k<N do

      for r in [1, 2, 3, 7, 8, 9] do

        if is149((q+r)^2) then

          k:=k+1;

          res[k]:=q+r

        fi

      od

    od;

    [seq(res[i],i=1..N)]

  end:

> start:=time():

  tricol(10);

  time()-start;

Le calcul précédent se fonde sur la considération de résidus modulo 10. Regardons les résidus modulo 100, en mimant ce qui a été proposé à la page 106.

> S2:={1,4,9,11,14,19,41,44,49,91,94,99}:

> seq(msolve(r^2=d,100),d=S2);

> L2:=sort(map2(op,2,map(op,[%])));

Nous reprenons donc le code en recopiant sans grande réflexion.

> lazy_is149:=proc(n::posint)

    local r;

    global S2;

    r:=n;

    while r<>0 do

      if not member(irem(r,100,'r'),

          {1,4,9,11,14,19,41,44,49,91,94,99}) then

        RETURN(false)

      fi

    od;

    true

  end:

> lazy_tricol:=proc(N)

    local k,res,q,r,n,i;

    global L2;

    k:=0;

    for q from 0 by 100 while k<N do

      for r in L2 do

        if lazy_is149((q+r)^2) then

          k:=k+1;

          res[k]:=q+r

        fi

      od

    od;

    [seq(res[i],i=1..N)]

  end:

> start:=time():

  lazy_tricol(10);

  time()-start;

On ne peut pas nier que l'exécution soit plus rapide, mais le résultat est faux.

> map(x->x^2,lazy_tricol(10));

En effet nous n'avons pas tenu compte du fait que le reste dans la division par 100 peut très bien ne comporter qu'un chiffre. En général cela indique la présence d'un zéro et nous ne voulons pas de cette configuration.

Reprenons donc. Nous découpons le carré en tranches de deux chiffres décimaux. Nous ne voulons voir apparaître que les motifs qui sont dans la liste L2 et qui comporte deux chiffres, sauf pour la dernière tranche (la tranche de deux chiffres du côté des poids forts) qui peut ne comporter qu'un chiffre. Ce dernier cas se repère par le fait que le quotient suivant est nul. On aboutit donc au code suivant.

> is149_2:=proc(n::posint)

    local r,s;

    r:=n;

    while r<>0 do

      s:=irem(r,100,'r');

      if not (member(s,{11,14,19,41,44,49,91,94,99})

              or

               (member(s,{1,4,9}) and r=0)) then

        RETURN(false)

      fi

    od;

    true

  end:

> tricol_2:=proc(N)

    local k,res,q,r,n,i;

    global L2;

    k:=0;

    for q from 0 by 100 while k<N do

      for r in L2 do

        if is149_2((q+r)^2) then

          k:=k+1;

          res[k]:=q+r;      fi

      od

    od;

    [seq(res[i],i=1..N)]

  end:

> start:=time():

  tricol_2(10);

  time()-start;

Le temps de calcul a été divisé par 2 au moins, comme annoncé. On voit bien pourquoi : dans la version fournie page 106, la variable r prend six valeurs sur dix (soit un taux de 0.6), alors que dans cette nouvelle version la variable r prend vingt-quatre valeurs sur cent (soit un taux de 0.24). Or 19.417*24/60=7.77, ce qui explique le résultat obtenu. On pourrait continuer dans la même voie car les taux successifs sont les suivants.

k taux  1  0.6  2  0.24  3  0.068  4  0.0152  5  0.00176

Retour en page principale