Programmation niveau supérieur

[Xklr_65]

J'ai scindé l'ancien topic car le niveau s'élevait un peu trop vite. Ce premier topic était destiné à apprivoiser les fonctions algorithmiques de base, et bien qu'étant intéressant, ce qui suit est d'un niveau plus difficile.
On cherche maintenant un programme grâce auquel on peut trouver des nombres premiers. Je m'explique:
Je rentre un nombre [tex]n[/tex] quelconque, et le programme me ressort le plus petit nombre premier [tex]p[/tex] tel que [tex]p \geqslant n[/tex]

[erd]

1) Voulez-vous un programme probabiliste ou déterministe ? En d'autre terme, voulez-vous que ce programme vous ressorte tout le temps un nombre premier, ou un nombre premier sauf erreur dont la probabilité est contrôlée ?

2) Si il vous sort un nombre premier, comment saurez-vous qu'il est vraiment premier ? Autrement dit que l'algorithme ne vous ment pas... Il serait peut-être intéressant de demander une preuve de sa primalité... Car un nombre premier, ça s'achète (!). Ça s'achète même très cher. Et s'il s'agit d'en vendre, l'acheteur risque de demander un certificat d'authenticité...! (NB : tout ceci est vrai)

3) voici un algorithme qui est censé vous donner un nombre premier. Si il vous le donne bien, il vous donnera aussi une preuve qu'il a mathématiquement assez de chance d'être premier et en plus c'est l'algo le plus rapide en terme de complexité (eh oui!), mais parfois il se trompe.... Qui peut me donner un exemple où il se trompe ? Question subsidiaire : quelqu'un a-t-il une idée de la probabilité d'erreur ? Question doublement subsidiaire : Comment s'appellent les nombres où il se trompe ? Suite des questions subsidiaires : pourquoi &^ ?

Code: Tout sélectionner

fermat2 := proc(n)
  local res,p;
  res := false;
  p := n-1;
  while res=false do
    p := p+1;
    if igcd(2,p)=1 and (2 &^ (p-1) -1 mod p) = 0 then
      res := true;
    fi;
  od;
  RETURN(p);
end;


[erd]

D'après les tests que je viens de faire, il semble "juste" 10 fois plus lent que le "nextprime" de MAPLE, ce qui est tout à fait raisonnable...

Exemple de test :

Code: Tout sélectionner

N:=2^1024:t := time():fermat2(N):time()-t;t := time():nextprime(N):time()-t;

Petite optimisation :

Code: Tout sélectionner

fermat2 := proc(n)
  local res,p;
  res := false;
  p := n-1;
  while res=false do
    p := p+1;
    if type(p,odd) then
      if (2 &^ (p-1) -1 mod p) = 0 then
        res := true;
      fi;
    fi;
  od;
  RETURN(p);
end;

Maintenant, il ne semble "plus que" 5 fois plus lent que le "nextprime" de MAPLE.

[Xklr_65]

L'idée de ma question était plutôt d'utiliser quelques fonctions de Maple pour des nombres relativement petits. Je pensais à quelque chose de plus accessible comme:

Code: Tout sélectionner

nextpremier:=proc(n)
local p;
  while isprime(p)=false do
    p:=p+1;
  od;
RETURN(p);
end;


Même si il est vrai que Maple possède une fonction "nextprime" qui simplifie la question, j'essaye ici de développer une procédure qui est à mi chemin entre le 'nextprime' de Maple et le 'fermat2' de Monsieur Riboulet.

Le but de cette procédure ici est de manipuler les outils que sont le isprime et la boucle while.

L'outil 'isprime'
L'outil 'isprime' est un outil de maple pour vérifier si un nombre est premier (avec une marge d'incertitude quand on flirte avec des grands nombres).
Par exemple si on rentre

Code: Tout sélectionner

isprime(60);

Maple nous sortira false.

La boucle While
L'écriture d'une boucle while est toujours la même:

Code: Tout sélectionner

while #quelquechose à vérifier# do
#Choses à faire#
od;

Ici la condition à vérifier est que le nombre p est non premier. Si il est premier, Maple interrompt la boucle et passe à la suite. Tant que p n'est pas premier, il va effectuer les opérations indiquées (à savoir ici passer à p+1)

[lord.osiris]

Coucou, bon, je lutte pour garder les yeux ouverts, mais je tiens à dire bravo et merci aux divers participants.
De plus, je vois que certains ont pris de bonne habitudes dès le début (clap clap), d'autres moins... Comme je l'ai dit sur le "deuxieme concours de programmation", il s'agit ici de mettre à disposition de tout le monde des exemples de choses programmées (en maple, principalement, car c'est l'outil de la prépa). Et de préférence de les commenter.
Merci donc à Xklr_65 pour ses commentaires clairs et précis. Par contre, le maillon faible est ici erd : on n'a pas d'explication, et le néophyte qui lira ce que vous avez marqué est totalement en droit de se demander POURQUOI le programme 2 est exécuté plus vite que le 1 (mais surtout, qu'est ce qu'il signifie, ligne par ligne?).
Je verrai, si j'ai le temps, pour faire une page web liée au site de brizeux pour stocker vos diverses propositions à ces concours de programmation. Si l'un des élèves de brizeux m'envoie un dessin à mettre sur cette page pour l'égayer un peu, ce sera avec plaisir que j'userai de mon photoshop pour l'insérer.

Sur ce @+, mes yeux tiennent pu...

[erd]

Par contre, le maillon faible est ici erd.

Non mais je rêve...

[lord.osiris]

Héhé... Désolé, monsieur, mais force est de constater que vous n'avez fait "que" donner le code, ce qui, pour les pauvres néophytes désirant en apprendre plus en programmation, n'est malheureusement pas suffisamment "clair". En effet, s'il est toujours possible de comprendre en gros certaines lignes, pour tout le monde, force est de constater (également en école d'ingé spécialisée en info) que la notion de "variable" n'est pas vraiment innée...
Le terme "maillon faible" n'est pas ici par rapport au niveau pour la programmation (car dans ce domaine, on sait tous que sincèrement on est assez loin derrière vous, et ce pour un bon moment encore). J'espère que vous ne l'avez pas trop mal pris, et j'ose supposer que c'est le cas, et que vous continuerez à participer à ces petits "jeux ludo-éducatifs" (même si j'aime pas trop ce terme...).

Sincèrement désolé si vous l'avez mal pris, tel n'était pas le but de mon propos...

[musyk]

Je sais, je débarque ... mais j'arrive sur ce topic et je me retrouve face à des questions sans réponses, j'essaie d'y répondre : et je n'y arrive pas!

3) voici un algorithme qui est censé vous donner un nombre premier. Si il vous le donne bien, il vous donnera aussi une preuve qu'il a mathématiquement assez de chance d'être premier et en plus c'est l'algo le plus rapide en terme de complexité (eh oui!), mais parfois il se trompe.... Qui peut me donner un exemple où il se trompe ? Question subsidiaire : quelqu'un a-t-il une idée de la probabilité d'erreur ? Question doublement subsidiaire : Comment s'appellent les nombres où il se trompe ? Suite des questions subsidiaires : pourquoi &^ ?

Serait-il possible d'avoir les réponses aux questions ?!

Le && est un "et" booléen, le & tout seul ne sert à rien ... le ^ nous dit que l'opération se fait bit à bit, alors je dirais que &^ signifie que l'on additionne bit à bit .... mais bon je n'en suis pas sûre parce que là je ne voies pas ce que l'on additionnerais dans le programme bit à bit ...


De plus, pourquoi le deuxième programme est optimisé .... j'aurais eu tendance à dire que le premier l'était car il n'a qu'un "if" ...

Et que signifie "type(p,odd)" ??? !!! car c'est ce qui me semble différer avec le premier programme ( igcd, qui me semble etre équivalent à un pgcd ...)

[musyk]

On vient de me souffler que odd en anglais signifie : impair , donc je suppose que la fonction type regarde si p est impair ou non ...

Si c'est cela, alors on me souffle aussi que type(p,odd) et igcd ont la même fonction, en effet si le pgcd d'un nombre avec 2 est 1, alors ce nombre est impair.

Alors j'en déduis que c'est sans doute pour ça que le deuxième programme est optimisé : le calcul du pgcd est plus long ........................

[erd]

Serait-il possible d'avoir les réponses aux questions ?!

Donnez un exemple numérique d'abord où l'algo se trompe. Ensuite je réponds aux questions...

Le && est un "et" booléen, le & tout seul ne sert à rien ... le ^ nous dit que l'opération se fait bit à bit, alors je dirais que &^ signifie que l'on additionne bit à bit .... mais bon je n'en suis pas sûre parce que là je ne voies pas ce que l'on additionnerais dans le programme bit à bit ...

Non, non et non.

Mettons que je veuille calculer 3^10000 modulo 2. Je ne vais pas calculer 3^10000 puis regarder si le nombre est pair ou impair !!! Non, je vois que 3 est impair donc 3 modulo 2 vaut 1 puis 1^10000 vaut 1. C'est (le début de) l'idée du &^...

Keyword : iterated scaring (algorithme des puissances par carré itérés).

De plus, pourquoi le deuxième programme est optimisé .... j'aurais eu tendance à dire que le premier l'était car il n'a qu'un "if" ...

Et que signifie "type(p,odd)" ??? !!! car c'est ce qui me semble différer avec le premier programme ( igcd, qui me semble etre équivalent à un pgcd ...)

non, la différence n'est pas là...

Allez, revenons à la question initiale, je veux un exemple.

[musyk]

C'est ce qui s'appelle du chantage !

[erd]

C'est ce qui s'appelle du chantage !

Si on veut.

[musyk]

Est ce que ça a un rapport avec les flottants ? (on ne sort pas les dents si ce n'est pas ça ... parce que je pense que ce n'est pas ça : là c'est une erreur d'écriture, et non pas une erreur du programme ... mais c'est tout ce que je voies ... c'est un peu long la vérification ... )

Code: Tout sélectionner

> fermat2 := proc(n)
>   local res,p;
>   res := false;
>   p := n-1;
>   while res=false do
>     p := p+1;
>     if igcd(2,p)=1 and (2 &^ (p-1) -1 mod p) = 0 then
>       res := true;
>     fi;
>   od;
>   RETURN(p);
> end;

fermat2 := proc(n)
local res, p;
    res := false;
    p := n - 1;
    while res = false do
        p := p + 1;
        if igcd(2, p) = 1 and ((2 &^ (p - 1)) - 1) mod p = 0 then
            res := true
        fi
    od;
    RETURN(p)
end

> fermat2(19,0/383,0);

                                  19

> fermat2(19/383);
Error, (in fermat2) wrong number (or type) of parameters in function igcd


[musyk]

Ayant réinstaller maple, j'ai pu accéder à l'aide ... et voir ce que signifiait &^ ...

"To compute i^n mod m where i is an integer, it is undesirable to use this ``obvious'' syntax because the powering will be performed first over the integers (possibly resulting in a very large integer) before reduction modulo m. Rather, the inert operator &^ should be used: i &^ n mod m. In the latter form, the powering will be performed intelligently by the mod operation."

En gros, c'est ce qui est expliqué plus haut ... i^n mod m calcul puis réfléchit, et la deuxième réfléchit puis calcul ....

L'opérateur &^ réduit une expression à sa forme la plus simple ?

[erd]

i^n mod m calcul puis réfléchit, et la deuxième réfléchit puis calcul ....

Question : pour bien comprendre, écrivez les opérations opérées pour calculez 5^10 mod 3 puis 5&^10 mod 3.