Math, nombres premiers : théorème de Wilson

[case]

1 chiffre(s) : 0 ms
2 chiffre(s) : 0 ms
3 chiffre(s) : 0 ms
4 chiffre(s) : 0 ms
5 chiffre(s) : 1 ms
6 chiffre(s) : 13 ms
7 chiffre(s) : 124 ms
8 chiffre(s) : 1239 ms
9 chiffre(s) : 12275 ms
10 chiffre(s) : 123303 ms

[Ollivier]

2 minutes pour 10 chiffres... Ouh, le fiasco !

[Mindphazer]

1 chiffre(s) : 0 ms
2 chiffre(s) : 0 ms
3 chiffre(s) : 0 ms
4 chiffre(s) : 0 ms
5 chiffre(s) : 2 ms
6 chiffre(s) : 16 ms
7 chiffre(s) : 138 ms
8 chiffre(s) : 1246 ms
9 chiffre(s) : 12441 ms
10 chiffre(s) : 124904 ms

[Ollivier]

Pour enfoncer un peu plus le clou, confirmation du fiasco...

Cependant, je vois une optimisation :
- "a" est parfois égal à zéro, quand p non premier avec une boucle For croissante plutôt que décroissante. (c'est de tête pour l'instant)

Code : Tout sélectionner

Procedure isPrime(p)
 Protected a = p - 1
 Protected i
 Protected q = p - 2
 For i = 2 to q
  a * i
  a % p
  If a = 0
   ProcedureReturn 0
  EndIf
 next
 a + 1
 ProcedureReturn Bool(a = p)
EndProcedure

[Ollivier]

Ensuite, il y a le théorème du Père Forateur,, soyons patient, je suis très occupé. Je vous ai mis l'optimisation par la détection du zéro pour les nombres composites (= nombres non premiers) : il reste l'optimisation pour les nombres premiers. Car les nombres premiers (au moins de tête, donc à vérifier) semblent présenter une harmonique propre. Et, de tête, je suis incapable de pondre un algo de détection d'une harmonique, mais il y a du potentiel à vérifier.

[Ar-S]

Code : Tout sélectionner

Procedure isPrime(p)
 Protected a = p - 1
 Protected i
 Protected q = p - 2
 For i = 2 to q
  a * i
  a % p
  If a = 0
   ProcedureReturn 0
  EndIf
 next
 a + 1
 ProcedureReturn Bool(a = p)
EndProcedure

donne

Code : Tout sélectionner

1 chiffre(s) :  0 ms
2 chiffre(s) :  0 ms
3 chiffre(s) :  0 ms
4 chiffre(s) :  0 ms
5 chiffre(s) :  0 ms
6 chiffre(s) :  5 ms
7 chiffre(s) :  45 ms
8 chiffre(s) :  463 ms
9 chiffre(s) :  3771 ms
10 chiffre(s) : 45344 ms

[Mindphazer]

Avec ton optimisation, ça donne ça :

Code : Tout sélectionner

1 chiffre(s) : 	0 ms
2 chiffre(s) : 	0 ms
3 chiffre(s) : 	0 ms
4 chiffre(s) : 	0 ms
5 chiffre(s) : 	1 ms
6 chiffre(s) : 	9 ms
7 chiffre(s) : 	83 ms
8 chiffre(s) : 	674 ms
9 chiffre(s) : 	397 ms
10 chiffre(s) : 	101 ms

C'est plutôt radicalement différent des résultats obtenus avec le premier algo

[Ollivier]

C'est assez étrange cette différence de vitesse entre le résultat d'ArS et le résultat de MindPhazer sur la valeur à 10 chiffres.
En tout cas, merci déjà à vous trois de vous intéresser à cette étrange formule mathématique et de retourner les résultats. Ça m'aide à déterminer si c'est valable ou pas de réfléchir à ce casse-tête.

Pour bien situer le contexte, cet algo n'a pas besoin de mémoire à la base pour vérifier si un nombre (par opposition à une suite de nombres consécutifs) est premier ou pas.

Et l'astuce qui se démarque du théorème initial, c'est en considérant que (pour C <> 0) :


(a * b) % C = [(a % C) * (b % C)] % C (illustr.1)


Ça ne caresse pas le simple à 1ère vue, mais le restant d'une division entière, est la face cachée de l'opération de division (entière) qui ouvre des portes à bon nombre d'optimisations en tout genre, grâce à cette égalité ci-dessus.

On peut simplifier une louchette :

(a * b) %C = [(a %C) * b] %C (illustr.2)

Autrement dit si le nombre a est un très (trop) grand nombre, l'illustration 2 nous montre qu'on peut bypasser le calcul qui va gonfler le nombre a.

(avec f(x) = (x * b) %C )

On a f(a) = f(a %C)

Que l'on traite le grand nombre ou, seulement le modulo de ce grand nombre, le résultat sera le même.

C'est cette même astuce qui permet de calculer pi à fond les ballons.

Pour les nombres composites (nombres non premiers), j'ai considéré ceci :

0 * b = 0
0 % C = 0 (toujours pour C <> 0)

Donc si un restant est nul durant les calculs intermédiaires, il restera nul indéfiniment et donc fixera, à l'avance, l'état composite du nombre à vérifier.

Pour optimiser les nombres qui s'avéreront premiers, c'est une autre paire de manche. Je parle d'harmonique : c'est le fait que le restant final de la division soit détecté plus tôt dans le test, durant les calculs intermédiaires. MAIS est-ce que c'est possible ? Une résonnance dans un tunnel, qui a section régulière, ça existe. Mais dans ce calcul ici, la représentation imaginable ressemble à un tuba, une trompette ou un mégaphone. On sait que ça amplifie, donc qu'il y a résonnance, mais comment la détecter ?

Là, même intuitivement, je reste un peu à poil... Peut-être en démarrant par le début et par la fin, tout en comparant les 2 séries de restants qui se créent, mais là, on entre dans un aspect qui alloue de la mémoire...

[Ollivier]

@MindPhazer !

Code : Tout sélectionner

 n = pow(10, i) - 7

Là, non plus, tu ne pouvais pas le dire que je me suis encore piné !



Je viens d'insérer la méthode naïve (tests par divisions) et cette dernière méthode trouve les facteurs des composites plus tôt.

Pour les nombres premiers, seuls certains présentent une harmonique, d'autres non. Ça douche tout espoir d'aller plus vite...

[Mindphazer]

Là, non plus, tu ne pouvais pas le dire que je me suis encore piné

Heuuuuuuuuuuu

[Ollivier]

Je plaisante. Trop habitué, je me pine sur des détails que tous les habitués connaissent. Mais si un nouveau venu débarque, il ne va rien comprendre, ou peut-être croire que c'est le compilo qui est foireux. D'où ces avoeux explicites, pour bien tirer le vrai du faux. Et lâche comme je suis, je me suis servi d'une pauvre âme innocente, MindPhazer.

Je trouve bien d'avoir décortiqué un tout petit peu ce sujet. Ainsi, on a 3 chemins pour chercher des nombres premiers :
- le cribles d'Ératosthène
- la méthode naïve
- le théorème de Wilson.

Peut-être devrais-je m'arrêter au théorème de Wilson pour les simplifications de division et de racines carrées. Pas besoin de mémoire. Pas besoin de nombres premiers. Juste besoin de temps...

[Ollivier]

Il n'y a pas que moi qui me pine dans la vie : la preuve.

[Mindphazer]

pauvre âme innocente, MindPhazer.

Je te laisse l'entière responsabilité de tes propos

[Ollivier]

pauvre âme innocente, MindPhazer.

Je te laisse l'entière responsabilité de tes propos

J'y peux rien : une âme innocente et immaculée, ce n'est pas assez anti-clérical. J'ai voulu avouer, qu'en respectant le sujet, les yeux évidés de conscience, pauvre de tout reproche, j'ai pris le "premier". Et c'est bien ce "premier" pris, qui est pauvre de tout reproche.