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

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

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

(réservé)

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.

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

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

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 :

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

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

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