Salut,
 
Je fais une étude sur les nombres premiers et le test de primalité de Miller-Rabin.
 
Pour mes calculs sur ordinateur, j'utilise NTL (http://www.shoup.net/ntl/) mais il paraît que GMP (http://swox.com/gmp/) donne de meilleurs résultats en terme de rapidité.  
Peut-être savez-vous si GMP est vraiment une meilleure librairie que NTL... Sauriez-vous également me dire combien de secondes prend la fonction mpz_probab_prime_p de GMP, si on lui passe, comme arguments, reps = 10 et n, un nombre premier d'un millier de chiffres ? Ceci me permettrait de comparer avec NTL (qui prend 48 secondes, sur un Athlon 1.8 Ghz, pour effectuer 10 itérations du test de Miller-Rabin, avec un nombre effectivement premier d'un millier de chiffres). Est-ce que 48 secondes vous semble être une performance satisfaisante?
 
Merci d'avance pour votre aide!!!
 
 

Mais testeuuuuuu ! Tu peux pas l'installer chez toi ?

Tu as nombre premier d'un millier de chiffres sous la main ? Celui avec lequel tu as testé...

Oui, je peux te passer un nombre premier de 1041 chiffres. Je te l'envoie demain, car je suis en déplacement(mais je rentre chez moi demain).  
Hélas, je manque de temps pour tester : il faudrait que j'installe GMP et Linux (GMP est conçu, à la base, pour fonctionner sous Linux) ce qui prend un certain temps (surtout que je n'ai presque aucune notion Linux)...
Je sais qu'il existe une version Windows de GMP mais il paraît qu'elle est excessivement compliquée à installer.
C'est pour ça que ça m'arrangerait si quelqu'un ayant déjà installé GMP pouvait faire ce petit test de rapidité pour moi...

Ok, ca marche. Tu me le donneras sous la forme d'une chaîne de caractères, ca ira. Où bien tu me dis ou en trouver un

c'est super gentil de ta part!!!  
 
Je te le passerai en chaîne de caractère, en effet, car pour en trouver un ex nihilo, c'est très difficile (comme tu le sais, plus on avance dans la série des nombres premiers, plus ils se raréfient.)
 
la probabilité de trouver aléatoirement un nombre premier de 1041 chiffres est inférieure à 1/(ln 10^1041), soit 1/2500.
 
je t'envoie un mail demain.
 
Merci encore!

Tu aurais pu avoir sous la main une url =)
Sinon, y'a pas de problème.  
 
@+

C'est bon, Evadream, je t'ai envoyé un message privé.

Ca sera du C, je trouve pas l'interface C++ très complète.  
 

C'est rapide, (5secondes), mais il ne considère pas le nombre comme être assurément un nombre premier. (athlon 2400+, 512mo).
 
int mpz_probab_prime_p (mpz_t n, int reps)  
Determine whether n is prime. Return 2 if n is definitely prime, return 1 if n is probably prime (without being certain), or return 0 if n is definitely composite.  
 
This function does some trial divisions, then some Miller-Rabin probabilistic primality tests. reps controls how many such tests are done, 5 to 10 is a reasonable number, more will reduce the chances of a composite being returned as "probably prime".  
 
Miller-Rabin and similar tests can be more properly called compositeness tests. Numbers which fail are known to be composite but those which pass might be prime or might be composite. Only a few composites pass, hence those which pass are considered probably prime.
 
Si tu veux, je peux essayer avec d'autres paramètres pour rets.
 
Edit : je viens de faire l'essai avec rets = 100 et 200, et le résultat est toujours Maybe. Cela prends repectivement 50 et 105 secondes.

Merci énormément pour ce coup de pouce!  
 
Tu pourrais me dire si le programme tournait seul (car si d'autres processus étaient en cours, le CPU devait être divisé... les anti-virus, tout particulièrement, mangent beaucoup de puissance!!) ?
 
Je veux bien que tu essayes avec 100 itérations (reps = 100) si ça ne te dérange pas... (je profite! )
 
Que singifient les lignes :
user    0m4.822s  
sys     0m0.008s ???
 
T'es sous Linux?  
 
THX

Oui, je suis sous Linux, aucun lourd process ne tournait en rond.
 
Pour time :  

PS : oui, le test de Miller-Rabin (c'est celui utilisé par la fonction de GMP) est un test "probabiliste" et non "déterministe". C'est à dire qu'il ne donne qu'une PROBABILITE de primalité, en guise de résultat. Cette probabilité varie avec le nombre d'itération (reps). Pour X itérations, on a la probabilité 1/(4^X) que le nombre testé ne soit pas premier. Donc si le test est positif avec reps = 10, on a seulement 1 chance sur 4^10 pour que le nombre testé ne soit pas premier (ce qui est très peu). Au delà de reps = 10, on peut considérer le test comme sûr.
Par contre, lorsque le test dit que le nombre est composé, c'est une certitude (et non plus une probabilité).

Ok, merci pour ces précisions

PPS : je crois que dans le cas de la fonction GMP utilisée ici, le prog ne retourne PRIME que si le nombre donné est petit ou alors de forme particulière. Dans ce cas, la primalité peut être démontrée avec certitude.
Mais peu importe, seul le "MAYBE" m'intéresse...

Merci à toi pour ta précieuse coopération!!

Pas de soucis. @++

 
Faux, ya une version déjà compilée si t'as la flegme d'installer tout ce qu'il faut :
http://www.cs.nyu.edu/exact/core/gmp/
 
T'as juste à décompresser au bon endroit.

oh cool! thanks
 
Au vu des résultats ci-dessus, je crois que je vais migrer vers GMP. En effet, là où NTL prend 48 secondes, GMP en prend 5 !  
 
GMP est donc 10 fois plus rapide que NTL !!!

leneuf22, sur la page que tu m'as donnée (http://www.cs.nyu.edu/exact/core/gmp/) ils distinguent "librairie dynamique" et "librairie statique" pour GMP. Faut que je prenne quoi? ça correspond à quoi cette distinction?

Une librairie dynamique c'est un fichier .dll sous ton windows : dans ce cas, la librairie et ton exécutable seront séparés. C'est utile par exemple si plusieurs exécutables (ou librairies dynamiques) de ton projet se servent de GMP.
 
La librairie statique de GMP, elle, peut se lier directement à ton programme, qui ainsi n'aura pas de dépendances externes : GMP se trouve alors directement dans ton exécutable (enfin plutôt les fonctions de GMP que tu utilise dans ton programme, ce que tu n'utilises pas n'est pas inclus !). Et ton exécutable est un peu plus gros dans ce cas.
 
En bref si ton truc tient dans un seul exécutable, tu peux utiliser la librairie statique.

Merci pour ces précisions!
 
Dans le lien que tu donnes, ils disent :  
"Download latest GMP and unzip to ${gmp_build}  
Copy all files under patches/4.1-static (or patches/4.1-dynamic for building DLL) to ${gmp_build}  
Open gmp.dsw (gmp.vcproj for VC++.Net) to build GMP "
 
mais à quoi correspond le dossier "${gmp_build}" ???? et "patches/4.1-static" ?
 
deuxio, ça veut dire quoi au juste "build GMP" ? je compile le projet indiqué tout bêtement?
 
(merci pour ton aide leneuf22!!!)

A ce que j'ai compris, tu veux GMP static pour VC++
Il faut donc que tu télécharges ceci : http://www.cs.nyu.edu/exact/core/g [...] -4.1.2.zip
 
Dedans t'as 3 fichier : 2 .lib, 1 .h.
Je connais pas trop VC++, mais dans le dossier d'install de VC++ tu dois avoir un dossier lib et un dossier include.
 
Tu mets le .h dans ton /include, et les 2 .lib dans /lib
Ensuite il suffit de #inclure <gmp.h> et d'ajouter gmp.lib (ou sa version debug) dans les options de ton projet.
 
Les instructions qui se trouvent sur la page que je t'ai données ne te concernent pas : il y a écrit :
 
"In the following, I assume that you want to download GMP to ${gmp_download}, build GMP at ${gmp_build}, and install GMP to ${gmp_install}"
Ce sont donc les instructions pour compiler GMP. Or le zip que je t'ai filé en lien au dessus contient la version déjà compilée.
 
Donc contente toi de décompresser les 3 fichiers au bon endroit et ça devrait aller !

OK, je vais faire ça!! merci beaucoup leneuf22!
 
PS : oui, j'utilise bien VC++ (6.0)
 
_____________

Nouvelle question :
 
Est-ce que quelqu'un sait si ça fait une grosse différence de temps d'exécution (pour le programme) quand on utilise GMP sous Win98 et WinXP ??

On m'a répondu que non sur la liste de discussion de GMP.

/!\ C'est quoi la version debug du fichier .lib de GMP? ça sert à quoi? (qu'est-ce que ça fait si j'attache cette lib plutôt que la normale ?)

Par ailleurs, j'essaye de faire marcher le code qui est à la page http://www.cppfrance.com/code.aspx?ID=24819 (un code tout simple pour calculer 2^n-1).  
Mais le prog me retourne une erreur "cannot reallocate memory) quand j'entre un "n" très grand (genre 10^80). est-ce parce que la variable n est de type "int" (integer)? Quelles lignes faudrait-il rajouter pour utiliser un n de type mpz?  
J'ai essayé mais les fonctions de multiplication ou d'élévation à la puissance refusent un troisième argument de type mpz non signé... comment faire?? bouhh... aidez-moi!

La version debug c'est pour faciliter le debogage en cas de plantage (utile quand tu développes le prog). Mais c'est souvent bien plus lent que le release.
Après pour ton 10^80, calcule la taille de ce nombre, puis lance le gestionnaire de taches, onglet performances et regarde combien tu as de mémoire de dispo. Je te laisse conclure.

Merci pour l'info sur gmpdebug.lib!
 
GMP est limité par la taille de la RAM??  
 
La plupart des autres librairies écrivent sur le disque dur quand la RAM est pleine... C'est pas le cas avec GMP?

 
Mais bon sang ici c'est pas le forum de développement consacré à GMP! Et même si GMP écrit sur le disque, il faut combien de disques de 200Go pour stocker le nombre 10^80 ?
Franchement y'a déjà un mec qui s'est fait ch*** à faire ton boulot à ta place, faudrait peut être penser un jour à te remonter les manches et à faire travailler un peu les neurones.

************ Message édité *************
 
Je voulais faire la même remarque que BlackGoddess mais mon explorateur buggait intensément (le retour du printemps?).
 
*****************************************

 
faut 81 octets sous forme de chaine, donc probablement moins sous forme de longs ?  

bien fait! ça m'apprendra à répondre autre chose que RTFM.

Nouvelle orientation pour ce sujet sur GMP :
 
Travailler avec des nombres non-signés, est-ce plus rapide qu'avec des nombres signés? (je n'utilise que les positifs mais je ne parviens pas à me décider entre les fonctions normales et les fonctions "ui" (unsigned integer)...)

C'est vraiment pas une question fondamentale. Ca te fera rien gagner en perfs, te prends pas la tête avec ce genre de question. ET puis entre nous, tu pourrais faire des tests toi même...
 
@+

Ce n'est pas une question fondamentale mais ça m'intéresse dans la mesure où je souhaite lancer des batteries de calculs très longs (ainsi la moindre seconde gagnée à chaque tour de boucle m'est précieuse).  
J'ai fait des tests et la différence est à peine percevable sur le court terme : les ui sont un peu plus rapides que les si.
 
De plus, d'après malik7934 de cppfrance.com :
"les unsigned on un bit de moins  (le bit de poids fort) donc ils sont plus courts, donc traîtés plus vite! "

[quote=990427,0,36,211307]
De plus, d'après malik7934 de cppfrance.com :
"les unsigned on un bit de moins  (le bit de poids fort) donc ils sont plus courts, donc traîtés plus vite! "[/quote]
 
Terrible

Evadream, c'est faux ce qu'affirme malik7934?  
Ton sourire vise-t-il la validité des propos ci-dessus mentionnés ou seulement leur pertinence?

S'interroger sur les différences de performances entre l'utilisation de nombre signé ou non me semble être une immense perte de temps. Ce n'est pas çà qui ne fera plus "ramer" une application ni même gagner 1% de perfs.
 
L'affirmation de malik7934 ne veut rien dire, ca dépend de l'architecture et de plein d'autres choses dont je n'ai meme  pas idée. On peut dire qu'un short sur 16 bits est traité moins efficacement qu'un int sur 32 bits avec une machine 32 bits en prenant des pincettes, mais bon ...
 
On utilise des nombres signés lorsque qu'on sait qu'on va en avoir besoin, idem pour les non signés si l'on sait que l'on va travailler avec des nombres >= 0. C'est à mon avis bien d'être rigoureux là dessus.
 
De toute façon, c'est totalement hors de propos, un entier avec gmp c'est une structure mpz_t, point barre. J'imagine qu'il y a un champ dans la structure indiquant si le nombre est signé ou pas, je doute fort que cette information soit dans le buffer qui contient effectivement le nombre.
 
Te prends pas la tête avec çà.

bon... OK, tu m'as convaincu Evadream.