>> 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):

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

[invite7863222222222]

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

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

[Médiat]

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

[A voir en vidéo sur Futura]

[SPH]

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.

[invite4ef352d8]

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]

(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]

[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]

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 !!

[invite4ef352d8]

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]

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 :

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

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

[invite7863222222222]

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.

[invite7863222222222]

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]

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...

[invite7863222222222]

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 !

[SPH]

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 !

Non, le résultat n'est pas 3.
Puisque l'on doit reporter le nombre 11, on tombe entre 2^3 et 2^4.

Ce n'est donc pas une histoire de modulo car ca ne calcul que la marque à partir de laquelle recommence le repère !

J'ai pris l'exemple de 3^3 sur une regle de 0 à 4 pour te montrer que ta formule ne fonctionne pas.
Elle fonctionnait au premier exemple parce que le report etait un chiffre sans virgule.

Le vrai résultat de mon second exemple n'est pas 3 mais 3.xxxxxxxxxxxxxxx

[invite7863222222222]

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 !

bon oublie mes messages, je vais reprendre les deux exemples car effectivement ce n'est pas correct.

[invite7863222222222]

ca ne calcul que la marque à partir de laquelle recommence le repère !

Le problème c'est cela. Ta règle commence à 0 ou à 2^0 ?
La premier case va de [0 à 2^0] ou de [2^0 à 2^1] ?

La formule n*(ln3)/ln2) s'applique que si la case 0 représente [2^0 à 2^1] (=[1 à 2]) mais pas [0 à 2^0] (=[0 à 1]).

Donc je suppose que ta regle commence à 1 pour que la formule n*(ln(3)/ln(2)) puisse marcher.
Mais ce n'est pas génant puisque pour un nombre entier k, on aura jamais k^n inférieur à 1.

3^3 = 27 et ca se trouve à la case numéro 3*ln(3)/ln(2)=4,75488750216346854436.

on a 5 cases :
case 0 : de 1 à 2
case 1 : de 2 à 4
case 2 : de 4 à 8
case 3 : de 8 à 16
case 4 : de 16 à 32
27 se trouve donc sur la case 4 -> c'est bon.

La formule que je te propose avec ces règles est :
E(4.75...) modulo 5. Et ca te donne bien 4.

Maintenant voyons pour 3^2.

Tu as deux cases :
case 0 : de 1 à 2
case 1 : de 2 à 4
3^2 = 9 ca dépasse de ta règle mais imaginons que ta règle était plus grande et je te propose la règle suivante :

case 0 : de 1 à 2
case 1 : de 2 à 4
case 2 : de 4 à 8 ----> on revient à la case 0
case 3 : de 8 à 16 ----> on revient à la case 1
case 4 : de 16 à 32 ----> on revient à la case 0
case 5 : de 32 à 64 ----> on revient à la case 1
...
9 se trouverait donc sur la case numero 3 donc on revient à la case 1.
Et la formule E(3.169925) modulo 2 = 1 fonctionne encore.

Cette fois ci, avec ces conventions, je pense que tout est bon, la formule est donc bien :

E(n*ln(3)/ln(2)) modulo (le nombre de case)

[SPH]

Le problème c'est cela. Ta règle commence à 0 ou à 2^0 ?
La premier case va de [0 à 2^0] ou de [2^0 à 2^1] ?

La formule n*(ln3)/ln2) s'applique que si la case 0 représente [2^0 à 2^1] (=[1 à 2]) mais pas [0 à 2^0] (=[0 à 1]).

Donc je suppose que ta regle commence à 1 pour que la formule n*(ln(3)/ln(2)) puisse marcher.
Mais ce n'est pas génant puisque pour un nombre entier k, on aura jamais k^n inférieur à 1.

3^3 = 27 et ca se trouve à la case numéro 3*ln(3)/ln(2)=4,75488750216346854436.

on a 5 cases :
case 0 : de 1 à 2
case 1 : de 2 à 4
case 2 : de 4 à 8
case 3 : de 8 à 16
case 4 : de 16 à 32
27 se trouve donc sur la case 4 -> c'est bon.

Grrrr, c'est ma faute car je n'aurais jamais dut parler de "CASES" mais plutot de "GRADUATIONS"

On a donc plus précisement ca :


3^3 = 27 et ca se trouve à la case numéro 3*ln(3)/ln(2)=4,75488750216346854436.

on a 5 GRADUATIONS :
"0" : représentant le chiffre 1
"1" : représentant le chiffre 2
"2" : représentant le chiffre 4
"3" : représentant le chiffre 8
"4" : représentant le chiffre 16
27 se trouve AU DELA DE la graduation "4"

[Médiat]

E(n*ln(3)/ln(2)) modulo (le nombre de case)

Tu as de la chance qu'on ne te rétorque pas :

Hey, arrete de planer !!!!!!

Car ta réponse est celle que je donnais au message #11

[SPH]

Tu as de la chance qu'on ne te rétorque pas :
Car ta réponse est celle que je donnais au message #11

Tu me fais rire

Jreeman est tres méthodique, lui !
Deviens donc comme lui en développant ta soit disant méthode avec les 2 exemples du dessus. Tu verras alors qu'elle ne marche pas et que tu t'es trop vite avancé...

[invite7863222222222]

ok donc si tu as n graduations, la formule n*ln(3)/ln(2) te donne la graduation inférieure qui est le plus proche de ton nombre.

Alors tu as (n-1) intervalles et donc ca fait partie entiere de ln(3)/ln(2) modulo (n-1).

Qaund tu as deux graduations, tu n'as donc qu'une seule possibilité pour la borne inférieure la plus proche de ton nombre, c'est 0, donc la formule doit toujours te renvoyer 0, ce qui est le cas, car k modulo 1, ca donne toujours 0.

[Médiat]

Tu verras alors qu'elle ne marche pas et que tu t'es trop vite avancé...

Quand on est incapable d'énoncer son besoin on ne se permet pas de commenter les réponses qui répondent parfaitement à la question posée, ce n'est que de ta faute si elle est mal posée.
Il y a encore peu tu ignorais tout des logarithmes et du modulo, tiens : tu me hurler de rire .

[Gwyddon]

Bonjour,

On se calme s'il vous plaît, on se calme...

Je te prie donc SPH de lire les réponses attentivement et de faire l'effort d'être poli, ce qui n'est pas toujours le cas dans cette discussion (message #12 et message #24).

Je demande aussi à Mediat de ne pas laisser les mots dépasser sa pensée.

Pour la modération,

G

[SPH]

Bonjour,

On se calme s'il vous plaît, on se calme...

Je te prie donc SPH de lire les réponses attentivement et de faire l'effort d'être poli, ce qui n'est pas toujours le cas dans cette discussion (message #12 et message #24).

Je demande aussi à Mediat de ne pas laisser les mots dépasser sa pensée.

Pour la modération,

G

Alors la, tu commences a m'agacer toi !! NE RETOURNE PAS la situation en faveur d'un mec qui répond tjr d'une facon tres hazardeuse sans developper un seul calcul !!!

Gonflé lui !!!!!!!!!!

[Gwyddon]

Bonjour,

Donc acte, malgré des avertissements répétés tu t'entêtes dans l'affrontement, et tu oses les insultes en privé. Je ferme donc cette discussion puisque il est impossible que la sérénité s'y installe, ce qui est fort dommage.

Pour la modération,

Gwyddon