>> Les Mersennes : Ma Quete du Graal

[SPH]

Bonjour à tous,

Me revoilà après 2 années de pause mathématique.

Mais, depuis ma conjecture rédigée ici même, mes découvertes n'ont cessé de me hanter. Finalement, sur 2 ans, j'ai à de nombreuses reprises fait des calculs, griffoner des tableaux, etc...

Ces derniers jours, je sentais que j'étais au bord de découvrir quelque chose de super interessant. Puis, en me renseignant sur les logaritmes neperiens, j'ai fais un bond en avant. Ma quete etait remplis a + de 90%.

Actuellement, il me manque une formule, une seule, que je n'ai pas encore trouvé. Si je la découvre, voici ce qui se passera :

Je serais capable de prouver la primalité d'un mersenne 3000 fois plus rapidement que le test actuel. Oui, oui, j'ai bien dit 3000 fois plus rapide.

Car, meme sans cette formule, je me suis penché sur une simulation que j'ai faite en programmant ce qu'il faut mais en remplacant ma formule manquante par une autre (une quelconque; du moment que ca occupe le meme temps processeur).
J'ai donc cherché sur le net le temps de calcul d'un mersenne et j'ai trouvé cette page : http://www2.lifl.fr/~wegrzyno/Mersenne/mersenne1.html
TOUT EN BAS, il est dit que le temps de calculs (sur Pentium II 400 Mhz) de la primalité du mersenne 9689 a pris 694327 secondes.
Moi, j'ai un 2000+; donc, si les calculs avaient été fait sur 2000+, ils auraient mis 5 fois moins de temps; soit 138865 secondes
Mon test, lui, met....... 38 secondes !!!!!!!!!!!!!!!!
Je suis 3650 fois plus rapide !!
ATTENTION cependant, mon test est 50% indécis. Il recommence alors les calculs avec d'autres paramètres. Les autres 50% donnent un résultat incontestable.

Vous me direz : "3650 fois plus rapide ??". Pour les incrédules, je confirme ce chiffre. Et même, admettons qu'il soit 10 fois plus lent que ce que je simule actuellement, il sera quand meme 365 fois plus rapide !!

SANS COMPTER que j'ai découvert il y a 5 minutes que mon test pouvait etre coupé en 2 !!

===========

QUE ME MANQUE T'IL ????

Il y a quelques jours, je vous demandais ca : http://forums.futura-sciences.com/thread163011.html

C'est une histoire de cases numéroté de 0 a x et représentant le nombre 2^x
Donc :
(0) __ (1) __ (2) __ (3) __ (4) __ (5) ...... les cases
_1____2____4____8____16____32 ....... une valeur

Maintenant, vous m'avez montré comment savoir où se situait un nombre d'apparence 3^y sur mon echelle (mes boites quoi) de format 2^x.

En faisant Ln(3) / Ln(2), on a un "pas" de 1.5849625 env.
C'est à dire que 3^1 se sutie entre ma boite 1 et ma boite 2.
3 est effectivement là.

Mais voilà, j'utilise un nombre de boites fini. Et voilà le problème que je dois résoudre :

Si j'ai les boites 0; 1 et 2, tout saut se situant au delà de ma derniere boite doit etre reporté selon le logarithme népérien en debut de boite (et c'est cette formule que je n'arrive pas à concevoir !).

Concrétement :
3^0 =1; ce qui correspond exactement à 2^0
3^1 =3; ce qui correspond à une fois mon "pas" calculé plus haut; c'est à dire 1.5849625. La boite correspondante est toujours le nombre entier; ici 1
3^2 =9; soit 2 fois le "pas"; soit : 3.169925. Je n'ai pas de boite numéro 3 !
Donc, puisque le plus grand nombre dans la boite 2 et avant la boite 3 est 7, si je reporte mon 9 au debut, j'aterris à 2 qui se trouve dans la boite 1 !

Sans meme calculer combien font 3^2, j'aimerais trouver ce report grace à un logarithme népérien (ou autre)....

Voila, vous connaissez mon désarois...

[Médiat]

Dans l'autre fil, il t'avait été suggéré une méthode que tu as refusée avec l'argument (dans ce cas il y avait 1000 cases numérotées de 0 à 999):

Citation:

si je tombe a 1002 par exemple, cela correspond a un chiffre entre 2^1002 et 2^1003. Hors, cette fourchette est BEAUCOUP plus large que la fourchette 2^(1002-1000) à 2^(1003-1000) !!

mais comme la fourchette entre 2^1002 et 2^1003 est plus grande que toute la fourchette précédente (2^2003-2^2002>2^2002-2^0), il n'y a aucun moyen de reporter les nombres trop grands sur la liste précédente sans perdre cette notion de fourchette. Si tu veux une réponse, il faut que tu expliques mieux ce que tu veux faire et avec quelles contraintes

[jreeman]

Citation:

Je n'ai pas de boite numéro 3 !

c'est pas 3 modulo 2 (=1) que tu cherches tout simplement ?

[Médiat]

Citation:

Posté par jreeman

c'est pas 3 modulo 2 (=1) que tu cherches tout simplement ?

Ca c'est la solution (à peu de choses près) refusée à laquelle je faisais allusion.

PS : Au fait c'était bien les vacances

[SPH]

Citation:

Posté par jreeman

c'est pas 3 modulo 2 (=1) que tu cherches tout simplement ?

Non, car on ne fini pas à 3, mais à 3.169925

[Médiat]

Si tu te contentes de dire "ce que vous me proposez ne va pas" sans dire ce que tu veux, cela va être très difficile de t'aider.

[Ksilver]

en gros tu cherche un algorithme qui situe le reste de q^n dans la division par 2^k (ou 2^k-1 peut-etre, tu n'est pas tres claire la dessus...), par rapport aux nombres de la formes 2^i, i<k.


deux question importante :

1) qu'elles seront les ordre de grandeurs des paramétres q,n et k ? (il faut savoir approximativement lesquelles seront grand par rapport aux autres... et de combien il seront plus grand...)

2) qu'elle doit etre la compléxité de l'algoritme ? (pour etre plus performant que les testes actuelle, combien d'opération peut-ton s'autoriser à effectuer pour obenir le résultat)



Je te propose une première solution, qui n'est probablement la plus adapté :
je suppose que je suis dans le cas ou q^n est tres grand devant 2^k, dans ce cas une methode intéressante est de calcule q^n modulo 2^k par exponentiation rapide. ainsi pour obtenir le résultat, il faudrat faire ln(n) multiplication (ce qui est tres faible) sur des nombres inférieur a 2^k (ce qui a mon avi, n'est pas si faible ^^ )

[SPH]

Ok ok, je vais changer le mot "boite" par graduation et je vous réexplique avec un exemple similaire mais toutefois plus clair :

Imaginez une regle gradué de 4 numéros. Les numéros 0; 1; 2 et 3.
Comme toute regle qui se respecte, ces 4 numéros sont allignés dans l'ordre et il y a la meme distance entre 0 à 1, et 1 à 2, et 2 à 3.

On a donc ceci : 0___1___2___3
Mais pas ceci : 0__1_____2____________3
Ni ceci par exemple : 0_____1___2______3

BON, ces numéros sont le "x" de l'expression 2^x
Ce qui se cache en fait à la marque "0" est la valeur 2^0
Etc....
donc ceci :
On a la marque "0" représentant la valeur 2^0; soit 1
On a la marque "1" représentant la valeur 2^1; soit 2
On a la marque "2" représentant la valeur 2^2; soit 4
On a la marque "3" représentant la valeur 2^3; soit 8

La regle graduée de base représente TJR des valeurs du genre 2^x (et jamais des valeur style 3^x; 4^x; 0^x; 1^x; 15555^x)

BON, la graduation va de 0 (toujours) à un nombre premier (ici le nombre 3)
Ok, vous suivez ???
Cette regle sert donc à calculer la primalité de..... M(3) !! et pas 3 !
N'OUBLIEZ PAS, les numéros marqués sur la regle represente des puissances.

Voila pour cette regle graduée

===============


MAINTENANT, on va jouer à savoir où se situe un nombre de format 3^y sur cette regle au format 2^x !

J'arrete là pour vous demander si cela est BIEN COMPRIS ?

(exemple : "mais où peux bien se situer 3^1 sur cette regle ?? Pile sur une marque ?? Ou à une certaine distance entre par exemple 1 et 2 ????")


------


Pour ceux qui me demande combien d'opération cela prendra, je leur répond : très peu. Mais je précise que ce n'est pas le nombre d'opération qui comptera dans ma routine. Ce qui compte, c'est : "5 de mes opérations vont aussi vite que 1 opération du test de primalité actuel !!" ps: ceci est un exemple)

Egalement, ceux qui me demandent quelles valeurs maxi prendront les differents parametres. C'est tres simple :
La regle va de 0 a un NP > au dernier mersenne premier actuellement trouvé
http://fr.wikipedia.org/wiki/Nombre_premier_de_Mersenne
Donc, de 0 à 32 582 657 + + +
La valeur 3 de l'expression 3^y peux varier mais assez peux genre entre 3 et 1 milliieme maxi du NP en bout de regle (pour 32 582 657, mon "3" variera de 3 a 325 maxi maxi maxiiiii)

[Médiat]

Citation:

Posté par SPH

(exemple : "mais où peux bien se situer 3^1 sur cette regle ?? Pile sur une marque ?? Ou à une certaine distance entre par exemple 1 et 2 ????")

On t'a déjà répondu à cela là : http://forums.futura-sciences.com/thread163011.html

[SPH]

Bon, je continue :

Le calcul : Ln(3) / Ln(2) permet de savoir où sera, sur notre regle, notre 3^1

Ln(3) / Ln(2) = 1,5849625007211561814537389439 478

On y va :

3^1 se situe a 1,5849625007211561814537389439 478 sur la regle.
3^2 se situe a 2*1,58496250072115618145373894 39478 sur la regle.

3^2 = 3,1699250014423123629074778878 956
Cela dépasse de la règle !

Le dépassement, je souhaite le reprendre depuis la marque "0" de la regle.

Voila le probleme !!
Sans calculer ce que fait 3^2, quelle formule me permettrait de reprendre les calculs depuis le 0+report de la regle ??????????

[Médiat]

Citation:

Posté par SPH

[b]Le dépassement, je souhaite le reprendre depuis la marque "0" de la regle.

Voila le probleme !!

A cela aussi on t'a déjà répondu (2 fois), mais tu refuses ces propositions sans expliquer quelles sont tes contraintes, alors sans informations supplémentaires, je en peux que te donner la même réponse : le modulo fait exactement cela !

Pour être clair (pour la dernière fois si tu n'est pas capable de nous donner tes contraintes), si ton calcul (avec les logs et la partie entière) donne le nombre entier N pour N° de boîte, et que tu as n boîtes, la réponse est (N modulo n).

[SPH]

Citation:

Posté par Médiat

A cela aussi on t'a déjà répondu (2 fois), mais tu refuses ces propositions sans expliquer quelles sont tes contraintes, alors sans informations supplémentaires, je en peux que te donner la même réponse : le modulo fait exactement cela !

Hey, arrete de planer !!!!!!

Il n' a jamais été question de modulo dans les réponses !!

[Ksilver]

et le y du 3^y sera grand comment ?
(ou plutot le '3^y' sera quand comment, c'est plutot ca qui est intéressant)

[Médiat]

Citation:

Posté par SPH

Hey, arrete de planer !!
Il n' a jamais été question de modulo dans les réponses !!

Ca fait vraiment plaisir de perdre son temps à tenter d'aider une personne aussi mal élevé que toi, à partir de maintenant tu te démm**des sans moi.

A tout hasard :

Citation:

Posté par jreeman

c'est pas 3 modulo 2 (=1) que tu cherches tout simplement ?

Citation:

Posté par ericc

Ce serait plus facile si tu allais jusque la case 999, je te laisse chercher pourquoi

C'est au modulo que ericc faisait allusion, ce que tu semblais avoir à peu près compris (cf. ta réponse)

Adieu

[jreeman]

Citation:

Posté par SPH

Non, car on ne fini pas à 3, mais à 3.169925

Oui désolé, je voulais plutot écrire E(3.169925) modulo 2 = 3 modulo 2 = 1.

Et si tu numérotes tes cases à partir de 0 alors tu n'as plus qu'à retirer 1.

[jreeman]

Citation:

Et si tu numérotes tes cases à partir de 0 alors tu n'as plus qu'à retirer 1.

pour préciser, ca donne donc :

(E(3.169925) -1) modulo 2 = 2 modulo 2 = 0

[SPH]

Citation:

Posté par jreeman

pour préciser, ca donne donc :

(E(3.169925) -1) modulo 2 = 2 modulo 2 = 0

Voyons voir si cela fonctionnerait si nous avions 3^3 sur une regle de 0 à 4 :

X = (Ln(3) / Ln(2))*3
X = 4,7548875021634685443612168318 434
E(X) = 4
4 Modulo 2 = 0

Maintenant, avec les vrais nombres :
3^3 = 27
2^4 = 16
27 - 16 = 11
2^3 < 11 < 2^4
Donc, (Ln(3) / Ln(2))*3 ne se trouve en aucun cas sur le repere 0 mais entre le repere 3 et 4 !!

As tu compris l'énorme subtilité de ce que je cherche ?

Pas facile de trouver la bonne formule...

[jreeman]

Citation:

Posté par SPH

4 Modulo 2 = 0

non non la formule que j'ai donné était bonne pour 2 cases mais dans ton nouveau cas, tu as 5 cases : 0, 1, 2, 3, 4.

Tu dois donc faire modulo 5.

le résultat est donc ((4-1) modulo 5) = 3 et donc on a bien ce qu'on cherche !