[Topic] Recherche des nombres de Mersenne premiers

Recherche des nombres de Mersenne premiers [Topic] - C - Programmation

Marsh Posté le 29-01-2014 à 18:18:42    

Bonjour,

 

Étant un fervent adepte du projet GIMPS www.mersenne.org depuis 2009

 

j'ai décidé récemment d'avoir mon propre programme permettant de rechercher ces fameux nombres de Mersenne premiers, pour inscrire mon nom dans l'histoire des maths ........................ c'est pas gagné  ;)

 

L'algorithme de Lucas-Lehmer (LL) permettant de les rechercher étant très simple dans son énoncé

 

voici le pseudo-code de cet algo

 
Code :
  1. soit p un nombre entier premier
  2. soit NM = 2^p - 1 un nombre de Mersenne
  3. et S(0) = 4 le 1er élément d'une suite
  4. pour i vaut 1 jusqu’à p-2
  5. {
  6.     S(i) = (S(i-1)^2 - 2) modulo NM
  7. }
  8. si S(p-2) == 0 alors
  9.     NM est premier
  10. sinon
  11.     NM est composé


Toute la difficulté réside dans l'implémentation de cet l'algo
Les nombres étant de très grande taille, il faudra trouver un moyen de les représenter en mémoire.

 

Il faudra aussi implémenter de manière efficace les opérateurs mathématiques permettant de les manipuler (^, - et modulo)

 

Le carré étant une simple multiplication.
et le modulo est une division euclidienne dont seul le reste nous intéresse.

 

Pour la multiplication nous aurons le choix entre les différents algorithmes
- approche naïve (multiplication scolaire)
- algorithme récursif de Karatsuba (et sa généralisation: algorithme de Toom-Cook)
- algorithme de multiplication par transformée de Fourier rapide (algorithme de Schönhage-Strassen)

 

Pour la division nous aurons les algorithmes étudiés dans cette page (1)
j'ai choisi en premier :
- l'algorithme binaire dichotomique (bornage binaire du quotient puis recherche par dichotomie)

 

Voila pour l'introduction,
j'ai déjà un programme (lent) qui fonctionne

 

http://imagizer.imageshack.us/v2/xq90/706/qiv5.png

 

Il faut environ 13 minutes et 50 secondes pour prouver que 2^2203-1 est premier,

 

Je suis entrain d'essayer de booster la division par un autre algo.

 

Voila, je voudrais savoir si ça intéresse du monde ...

 

Sources:
http://fr.wikipedia.org/wiki/Nombr [...] ne_premier
Multiplication: http://fr.wikipedia.org/wiki/Algor [...] iplication
Algo de Karatsuba: http://zanotti.univ-tln.fr/enseignement/I51/TP11.html
(1) Division: http://compoasso.free.fr/primelist [...] uclide.php


Message édité par Caffrey's le 29-11-2014 à 11:18:55
Reply

Marsh Posté le 29-01-2014 à 18:18:42   

Reply

Marsh Posté le 29-01-2014 à 18:27:11    

(réservé)

Reply

Marsh Posté le 29-01-2014 à 18:31:51    

Une question peut-être naïve, hein, mais vu que c'est un sujet déjà abondamment traité, pourquoi ne pas partir sur une implémentation déjà faite et utilisée ?

 

Edit : pour la gestion de grands nombre, je voulais dire. L'algorithme ensuite devrait être assez simple à implémenter.


Message édité par theshockwave le 29-01-2014 à 18:32:34

---------------
last.fm
Reply

Marsh Posté le 29-01-2014 à 18:53:59    

Bonne remarque,

 

Le truc est que je ne sais pas si la librairie GMP implémente les bons algo avec les jeux d'instruction AVX, AVX2, (AVX-512 bientôt)

 

En fait mon travail sur l'algo LL est là aussi pour m'apprendre l'assembleur (bientôt) lorsque j'aurais un algo en C de multiplication très rapide.

 

L'idée aussi c'était que je pensais que j'aurais pu "placer" mes grands nombres en cache L3 => Erreur de ma part

 

Mais disons que pour le futur, j'aimerais maitriser tout les détails de l'implémentation sur ce calcul


Message édité par Caffrey's le 29-01-2014 à 19:06:58
Reply

Marsh Posté le 29-01-2014 à 19:20:45    

AVX, c'est encore un peu tôt pour vouloir généraliser son utilisation, non ?
les détails à propos de l'utilisation d'assembleur dans GMP sont disponibles dans la doc ici : [url]https://gmplib.org/manual/Assembly-Coding.html#Assembly-Coding[/rul]
 
Pour ce qui est des algorithmes utilisés, ils sont décrits par ici : https://gmplib.org/manual/Algorithms.html#Algorithms
 
Etant donné que c'est open source, ils n'y a pas grand chose à cacher sur ces deux sujets :)
 
Cela étant dit, donc, c'est effectivement formateur d'apprendre l'assembleur. J'ai vu en survolant la doc de GMP qu'ils utilisent des blocs ASM. Dès qu'on a un compilateur qui le permet, c'est préférable d'utiliser des intrinsics plutôt que des blocs ASM.
 
Après, ca peut aussi être intéressant de garder la lib GMP de côté au moins à titre de comparaison vis-à-vis des résultats que tu obtiens de ton côté.


---------------
last.fm
Reply

Marsh Posté le 09-04-2014 à 20:13:06    

J'ai encore bossé sur le soft depuis ce temps

 

Après avoir implémenté la multiplication avec l'algorithme de Karatsuba et la division avec l'algorithme de Burnikel et Ziegler ( http://domino.mpi-inf.mpg.de/inter [...] enDocument )

 

J'obtiens de bien meilleurs résultats a condition de pré-créer une plage mémoire continue pour toutes les variables des appels récursifs pour la multiplication(carré): k_space
et une autre plage mémoire pour la division(modulo): bz_space

 

utilisée tel que :

Code :
  1. fin_de_la_zone_utilisee = Karatsuba(debut_de_zone_utilisee_nottament_pour_le_resultat_et_les_variables, opérande1, opérande2);

avec le 1er paramètre est un pointeur sur une large zone mémoire et la valeur de retour pointe sur la fin de cette même zone, les autres paramètres doivent être des pointeurs aussi de préférence

 

J'ai gagné en vitesse approximativement d'un facteur 276 pour les exposants 4253 et 4423
et d'un facteur 553 pour les 2 exposants suivants: 9689 et 9941

 

L'exposant 44497 me semble désormais accessible en calcul dans une demi-journée

 

http://www.heberger-image.fr/data/images/43377_NMP16KBZ.jpg

 

J'avais déjà implémenté une optimisation dans un cas particulier de la division binaire-dichotomique (utilisée dans mon implémentation de Burnikel et Ziegler)
faut que j'y revienne dessus.
ensuite faut que passe le soft en 64 bits et en 2^(5+n) bits,
que je rende les opérations de base (addition, soustraction, multiplication) optimales,
que je passe Karatsuba en multithreads ...


Message édité par Caffrey's le 25-06-2014 à 18:42:26
Reply

Marsh Posté le 17-04-2014 à 17:21:19    

En passant
1- le programme en 64 bits,
2- l’algorithme de Karatsuba en multi-thread
3- et en utilisant la division rapide par (2^n-1)  ( voir http://en.wikipedia.org/wiki/Lucas [...] ality_test )

 

J’obtiens un facteur de gain de 76 à 360 par rapport au programme précédent, pour les exposants 4253,4423,9689,9941,11213 et 19937

 

Cette fois-ci je vérifie que 2^44497-1 (M27)  est premier en 77secondes
et 2^132049-1 (M30) en 21minutes et 39secondes

 

Je n'aurais un programme réellement rapide que lorsque j'aurais implémenté la multiplication avec l'algorithme de Schönhage-Strassen (FFT).


Message édité par Caffrey's le 29-12-2014 à 09:17:46
Reply

Sujets relatifs:

Leave a Replay

Make sure you enter the(*)required information where indicate.HTML code is not allowed