>> Sécurité de l'état / Nombres premiers

[SPH]

2^536870912 en environ 7 min bien sur avec tous les chiffres
j ai utiliser la fft au lieu de la hartley (avec je devrai aller plus vite)

tu met combien de temps ?

Bien plus pour l'instant mais l'ecart se ressert avec l'arrivée massive de l'ASM. Et puis cela ne veux rien dire puisqu'on a pas les memes machines. J'ai un 2000+ et 512mo
-----

[invitedebe236f]

celeron 2.4 ghz 256 mo de ram et programmer en vb

bien sur 2 ^268435456 en 2 fois moins de temps
et 2^1073741824 en 2 fois plus de temps
c est lineaire

[invite3d7be5ae]

J'ai oulier de faire la conversion bit->octet.
Mais g_h, tu es sûr de ton temps?
La hartley?C'est quoi?
SPH, tu travailles avec des algos que tu as faits où ceux que l'on peut télécharger?

[invite97a92052]

Mais g_h, tu es sûr de ton temps?

Si vous me proposez un endroit ou héberger l'exécutable (29 ko), vous pourrez vous en rendre compte par vous-même...
Sinon, vous n'avez qu'à installer un compilo C et la librairie GMP, et essayer le code que j'ai donné plus haut.

Mais Pole, je ne vois pas pourquoi ça t'étonne vu que tu sembles obtenir des résultats comparables avec Java et Maple... et je ne vois vraiment pas ce qu'il y a de sorcier à mettre un 1 avec 500 000 000 zéros derrière.


Bref, sinon je ne vois pas trop l'interet de la discussion vu que l'auteur ne veut rien révéler de ce qu'il est en train de faire (ou alors j'ai rien compris à la discussion)

[erik]

celeron 2.4 ghz 256 mo de ram et programmer en vb

C'est dommage d'avoir une bécane aussi rapide et de programmer en vb, si tu veux faire un peu de calcul intensif je te conseille de choisir un autre langage (c ou c++ par exemple), tu obtiendras un gain de temps de calcul plus qu'appreciable.
Vb produit du code très lent.

[invitedebe236f]

de toute facon c est un temp estime j ai pas asser de memoire

http://craftac2.free.fr/Project1.exe

voila l executable
pour info sur amd 4000+ 1 go
2^{67 108 864} en 25 s necessite 512 mo de ram
2^{134 217 728} en 52 s necessite 1 go de ram

lancer l executable sous dos
project1 19 calcule 2^{33 554 432} 256 mo
project1 20 calcule 2^{67 108 864} 512 mo
project1 21 calcule 2^{134 217 728} 1 go
etc fichier generer resultatxx sur c:\

attention si on a pas asser de memoire ca swap sur disque et ca devient hyper lent

[SPH]

Bon, je répond a tout le monde :

C'est mon algo que j'ai concu. A la base, il permet d'utiliser le crible d'euratostene mais j'ai inséré une variante qui l'accelere beaucoup. En l'utilisant, on arrive a un overflow en quelques secondes.
Donc, mon alternative est de contourner ce bug normal en informatique. Pour cela, je commence deja par ecrire un nombre de mersenne de 10 millions de chiffres dans une banque d'octets. Et c'estexactement ce que nous sommes en train de faire : on construit bien actuellement 2^n. Quand on aura 10 millions de chiffres, on retirera 1 a ce nombre pour en faire un nombre de mersenne, puis je reprendrais mon algo et je le modifierais legerement pour qu'il puisse voir tres loin (a 10 millions de chiffres) si chaque premier est egal a notre banque. Si oui : la banque contient un NON premier, sinon, c'est un premier.
A celui qui ne comprenait pas, la, j'espere avoir ete clair.

Maintenant, a Celui qui arrive a calculer a la vitesse de la lumiere un 2^n, je suis tres surpris mais bon, quand j'en aurais fini en ASM, il se peux que j'atteigne cette vitesse.

[invitedebe236f]

hartley c est une variante de la fft
on utile pas de nombre imaginaire
les multiplication se fond differement
au final avec le resultat qu on trouve on peut le convertir facilement pour arriver au meme resultat qu une fft

l inverse d une fht est la meme fonction pas la peine de changer le signe des sinus comme dans une fft

[SPH]

je ne connais pas hartley. J'utilise une banque d'octet et je la remplis de morceaux du chiffre geant

[SPH]

Juste comme ca, pour verifier que ma routine ne bug pas, qui pourrait verifier que ce nombre est correct (2^2^16) ??
merci

[invite97a92052]

C'est OK pour moi !

[SPH]

G_H : peut tu m'envoyer un TXT contenant ton 2^2^16 ? (je veux analyser quelque chose)

[invite3d7be5ae]

Je crois que ça commence par 200 alors que ton fichier me donne 20 00.
A pars ça, ça à l'air juste.

[SPH]

Je crois que ça commence par 200 alors que ton fichier me donne 20 00.
A pars ça, ça à l'air juste.

non, il commence par 0200352993...............

[invitedebe236f]

j ai modifier la sortie fichier c est plus lisible

http://craftac2.free.fr/Project1.exe

sinon voila le resultat 16 a 20
http://craftac2.free.fr/puis2.zip

[invite3d7be5ae]

Cricri je n'arrive pas éxécuter ton programme.
Il faut faire comment?

[invite3d7be5ae]

En java, en faisant des décalages, j'arrive à 2^(2^26). Après, plus assez de mémoire pour java.

SPH, si ta multiplication est exponentiel, tu ferais mieux de passer à la multiplication à la Karatsuba où à la FFT.
A tu déjà essayais avec les plus petits nombres de Mersenne premiers?

[invitedebe236f]

sous dos ou dans demarrer executer
tu tape project1 10
ou project1 11
etc

[invitedebe236f]

faut peut etre ca si tu la pas deja

http://www.microsoft.com/downloads/d...D-CDF2D29A79D5

[SPH]

Cricri je n'arrive pas éxécuter ton programme.
Il faut faire comment?

Idem

Mon programme avance...

Sinon, a part moi, qui a deja essayé ou a envie d'essayer de concourir a la recherche du nombre de mersenne de 10 millions de chiffres ? Vous savez qu'il y a 100000$ a empocher ?

[SPH]

Bon, voila, j'ai fini mon code. Il me permet d'effectuer un crible d'eratostene a partir de 10 millions de chiffres. Je suis en train de calculer cette emplacement et demain, il sera sauvegardé sur mon diskdur. Ensuite, le crible fera apparaitre des trous dont l'un d'eux sera, esperons le, un nombre de mersenne.

[invite76e2b617]

Un nombre de Mersenne premier tu veux dire
Si ça coince, il y a toujours Lucas-Lehmer...

[erik]

Bon, voila, j'ai fini mon code. Il me permet d'effectuer un crible d'eratostene a partir de 10 millions de chiffres

Bon, il est dommage que tu ne veuilles pas expliquer plus précisement l'algo que tu met en place parce que tu fait erreur et il n'est pas possible de t'expliquer où tu te trompes sans en savoir un peu plus.
Mais déja on peut dire que :
1/ Un crible ne trouve pas des nombres premiers à partir d'une certaine valeur, mais jusqu'à une certaine valeur, c'est très différent (mais tu as peut être fait un lapsus).
2/ Pour des raisons d'espace mémoire il est impossible de faire un crible determinant les nombres premiers compris entre 2 et un nombre de 10 millions de chiffres (et un crible débute obligatoirement à 2 cf la remarque1/)

Malgré tout, je ne veux pas te décourager, mais tu t'orientes sur la mauvaise voie, renseignes toi sur les différent tests de primalité existant, je suis certain que tu pourras réutiliser certaines parties de ton code quand tu auras abandonné l'idée du crible.

[SPH]

Bon, il est dommage que tu ne veuilles pas expliquer plus précisement l'algo que tu met en place parce que tu fait erreur et il n'est pas possible de t'expliquer où tu te trompes sans en savoir un peu plus.
Mais déja on peut dire que :
1/ Un crible ne trouve pas des nombres premiers à partir d'une certaine valeur, mais jusqu'à une certaine valeur, c'est très différent (mais tu as peut être fait un lapsus).

Mon algo permet de trouver les NP a partir de 10 millions de chiffres (mon algo est en calcul la. Et il mettra apparement non pas 1 mais plutot 3 jours.)

2/ Pour des raisons d'espace mémoire il est impossible de faire un crible determinant les nombres premiers compris entre 2 et un nombre de 10 millions de chiffres (et un crible débute obligatoirement à 2 cf la remarque1/)

C'est possible mais ce sera peut etre long.

Malgré tout, je ne veux pas te décourager, mais tu t'orientes sur la mauvaise voie, renseignes toi sur les différent tests de primalité existant, je suis certain que tu pourras réutiliser certaines parties de ton code quand tu auras abandonné l'idée du crible.

Non merci, je garde le crible.

[invited6139184]

Ce sujet est certe passionnant, mais hélas, je suis de l'avis d'Erik.

Si j'ai bien compris, SPH, tu calcules un nombre de Mersenne, puis avec ton crible tu cherches à savoir s'il est premier.

Seulement, tu as à peu près autant de chances de tomber sur un premier en partant d'un Mersenne aussi grand (10^1000.10^1000 chiffres), que si tu choisisais un grand nombre de la même taille au hasard ...

Ce qui veut dire que tu pourrais t'abstenir de calculer des nombres de Mersenne, et générer aléatoirement des nombres impairs de n chiffres, et les tester ensuite (pourquoi pas dans les décimales de Pi).

Quant au crible d'Erathosthène, ce n'est evidemment pas le meilleur algorithme. Le problème de stockage devient rapidement prohibitif !

A moins que tu n'ais fait une découverte sensationnelle, je ne vois pas comment tu pourras t'en sortir.

[SPH]

Je ne sais pas si j'ai decouvert quelque chose qui n'a pas ete trouvé mais je m'en sert.
Cela me sert deja a me positionner non pas au nombre "2" mais a X (qui contient 10 millions de chiffres (actuellement en cour de calcul; actuellement a 4.9 millions de chiffres)). Puis, je serais capable de regarder un champ de nombre allant de X a X+15000000000 (pas 15 milliard de chiffre, hein !!). Dans ce champs vierge, je serais capable d'eliminer presque instantanement les NP "2" a "200000000".
Puis apres, je ne sais pas encore comment faire mais j'ai 2 alternatives qui reviennent grosso modo au meme.

[invited6139184]

Oh la la qu'est-ce que je suis bête !! Evidemment, je voulais dire "un nombre aussi grand" ( 2^n-1, quand n tend vers "beaucoup" ), et pas en nombre de chiffres !!

Quoi qu'il en soit , le problème de mémoire est bel et bien là !

As-tu lu le livre de Delahaye, "Merveilleux nombres premiers", chez Belin ?

[leg]

sans cacul il utile le crible d Erathostène

je vois que ca

bonjour cricri. on peut utiliser l'algorithme P(30) indication:je sort tous les n Premiers par familles en 1 h 40 jusqu'à 500 000 000 000 000 ! par ordre croissant avec leur position uniquement en comptant des 0 et des 1 avec les 8 premiers < ou = 31 a l'exeption de 2 , 3 et 5!

[leg]

Tiens, est-il possible d'adapter le crible d'Eratosthène pour qu'il ne porte que sur les suites 6n+1 et 6n-1, cela éliminerait pas mal de cas. A part 2 et 3, tous les premiers sont dans ces 2 suites, non ?

salut ,il y a mieux tu peux supprimer aussi 5!

[leg]

bonsoir sph, ton algo est- il en rapport avec les 8 casiers et les 8 cases ?