recherche code multi thread java pour test de primalite
remy
vous ne connaitriez pas un bout de code multi thread
java qui ferait un test de primalité
histoire de me servir de tous les coeurs de la machine
c'est pour booster un peu le code
http://cjoint.com/data/mwlRFNicX7.htm
vu que la même implémentation en c
http://cjoint.com/data/mwlL3wfBsX.htm
c'est avérée moins rapide
à titre perso je ne m'attendais pas à un écart aussi grand
merci remy
--
http://remyaumeunier.chez-alice.fr/
Yliur
remy <re...@fctpas.fr> a écrit :
La version C est *moins* rapide ?
Quel est l'écart ?
Et pour le test, comment le fais-tu ? Ça ne devrait pas être difficile
à distribuer.
remy
> Le Tue, 22 Dec 2009 11:52:21 +0100
> remy <re...@fctpas.fr> a écrit :
>
>> bonjour
>>
>> vous ne connaitriez pas un bout de code multi thread
>> java qui ferait un test de primalité
>> histoire de me servir de tous les coeurs de la machine
>> c'est pour booster un peu le code
>>
>> http://cjoint.com/data/mwlRFNicX7.htm
>>
>> vu que la même implémentation en c
>> http://cjoint.com/data/mwlL3wfBsX.htm
>>
>> c'est avérée moins rapide
>> à titre perso je ne m'attendais pas à un écart aussi grand
>>
>>
>>
>> merci remy
>
> La version C est *moins* rapide ?
> Quel est l'écart ?
il te faut la libgmp voir avec synaptic et gcc
gcc -o jumeaux jumeaux.c -lgmp
time ./jumeaux
real 0m34.833s
user 0m34.230s
sys 0m0.000s
remy@remy-desktop:~/Bureau/cJumeaux$
javac jumeaux.java
time java jumeaux
real 0m12.011s
user 0m12.429s
sys 0m0.416s
remy@remy-desktop:~/Bureau/cJumeaux$
>
> Et pour le test, comment le fais-tu ? Ça ne devrait pas être difficile
> à distribuer.
>
disons que j'ai actuellement la flemme de coder mon propre test de
primalité donc j'utilise celui qui est fourni de base
dans gmp et biginteger ce qui si j'en crois mes lectures ils utilisent
tous les 2 un test de primalité Miller-Rabin
http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Miller-Rabin
remy
Yliur
remy <re...@fctpas.fr> a écrit :
Je n'ai pas vérifié les deux implémentations, mais c'est étrange. sur
ce genre de calculs en général ça va plus vite en C. Mais c'est
difficile à comparer en utilisant des bibliothèques externes,
peut-être que ce sont elles qui sont en cause. Enfin ce n'est pas
très important...
Par contre pour des programmes qui ont besoin de faire des calculs plus
rapides, tu pourrait ajouter -O2 dans ta compilation avec gcc et
-server dans le lancement de ta JVM.
> >
> > Et pour le test, comment le fais-tu ? Ça ne devrait pas être
> > difficile à distribuer.
> >
>
> disons que j'ai actuellement la flemme de coder mon propre test de
> primalité donc j'utilise celui qui est fourni de base
> dans gmp et biginteger ce qui si j'en crois mes lectures ils utilisent
> tous les 2 un test de primalité Miller-Rabin
>
> http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Miller-Rabin
>
>
> remy
Et tu as regardé ce qui consommait du temps exactement ?
Est-ce que ta boucle est répétée beaucoup de fois ? Tu ne pourrais pas
lancer plusieurs itérations en même temps plutôt qu'utiliser un autre
algo de test pour tes nombres premiers ?
batyann811
>
> Je n'ai pas v�rifi� les deux impl�mentations, mais c'est �trange. sur
> ce genre de calculs en g�n�ral �a va plus vite en C. Mais c'est
> difficile � comparer en utilisant des biblioth�ques externes,
> peut-�tre que ce sont elles qui sont en cause. Enfin ce n'est pas
> tr�s important...
>
Apr�s un rapide coup d'oeil sur la libgmp il semblerait que le type
mpz_t cache de l'allocation dynamique (d'ailleurs il manque les appels �
mpz_clear pour lib�rer la m�moire). Dans un cas comme �a il n'est pas
impossible que Java avec son JIT puisse s'av�rer plus efficace.
> Et tu as regard� ce qui consommait du temps exactement ?
> Est-ce que ta boucle est r�p�t�e beaucoup de fois ? Tu ne pourrais pas
> lancer plusieurs it�rations en m�me temps plut�t qu'utiliser un autre
> algo de test pour tes nombres premiers ?
>
Moi je me demande si les 2 codes font la m�me chose...
extrait du code C :
if(mpz_probab_prime_p(val1,500)>0)
{
if(mpz_probab_prime_p(val2,500)>0)
extrait du code Java :
if (val1.isProbablePrime(100))
{
if (val2.isProbablePrime(100))
Rien ne dit que les valeurs 100 en java et 500 en C vont provoquer le
m�me nombre de tests...
D'ailleurs la doc de GMP pr�cise pour ce param�tre : '5 to 10 is a
reasonable number'. Alors 500...
Bref il faut comparer ce qui est comparable.
Yliur
batyann811 <batya...@invalid.fre> a écrit :
> Yliur a écrit :
> >
> > Je n'ai pas vérifié les deux implémentations, mais c'est étrange.
> > sur ce genre de calculs en général ça va plus vite en C. Mais c'est
> > difficile à comparer en utilisant des bibliothèques externes,
> > peut-être que ce sont elles qui sont en cause. Enfin ce n'est pas
> > très important...
> >
>
> Après un rapide coup d'oeil sur la libgmp il semblerait que le type
> mpz_t cache de l'allocation dynamique (d'ailleurs il manque les
> appels à mpz_clear pour libérer la mémoire). Dans un cas comme ça il
> n'est pas impossible que Java avec son JIT puisse s'avèrer plus
> efficace.
>
> > Et tu as regardé ce qui consommait du temps exactement ?
> > Est-ce que ta boucle est répétée beaucoup de fois ? Tu ne pourrais
> > pas lancer plusieurs itérations en même temps plutôt qu'utiliser un
> > autre algo de test pour tes nombres premiers ?
> >
>
> Moi je me demande si les 2 codes font la même chose...
>
> extrait du code C :
>
> if(mpz_probab_prime_p(val1,500)>0)
> {
> if(mpz_probab_prime_p(val2,500)>0)
>
> extrait du code Java :
>
> if (val1.isProbablePrime(100))
> {
> if (val2.isProbablePrime(100))
>
> Rien ne dit que les valeurs 100 en java et 500 en C vont provoquer le
> même nombre de tests...
>
> D'ailleurs la doc de GMP précise pour ce paramètre : '5 to 10 is a
> reasonable number'. Alors 500...
>
>
> Bref il faut comparer ce qui est comparable.
Oui, j'ai eu la flemme de lire les deux codes en entier pour en tirer
quelque chose :) . Mais à part l'écart qu'il avait noté et qui
m'intriguait, il cherchait comment utiliser les différents coeurs de
sa machine. C'est à ça que je pensais dans ce paragraphe sur sa
boucle : au lieu de trouver une autre implémentation de ses
bibliothèques qui utiliserait plusieurs coeurs, il pourrait peut-être
paralléliser son algo à lui.
remy
o2 me retourne une tripotée erreur
remy@remy-desktop:~/Bureau/cJumeaux$ gcc -o2 jumeaux jumeaux.c -lgmp
jumeaux: In function `_start':
/build/buildd/glibc-2.9/csu/../sysdeps/i386/elf/start.S:65: multiple
definition of `_start'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crt1.o:/build/buildd/glibc-2.9/csu/../sysdeps/i386/elf/start.S:65:
first defined here
jumeaux:(.rodata+0x0): multiple definition of `_fp_hw'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crt1.o:(.rodata+0x0):
first defined here
jumeaux: In function `_fini':
/build/buildd/glibc-2.9/csu/../sysdeps/generic/initfini.c:109: multiple
definition of `_fini'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crti.o:/build/buildd/glibc-2.9/csu/../sysdeps/generic/initfini.c:109:
first defined here
jumeaux:(.rodata+0x4): multiple definition of `_IO_stdin_used'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crt1.o:(.rodata.cst4+0x0):
first defined here
jumeaux: In function `__data_start':
(.data+0x0): multiple definition of `__data_start'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crt1.o:(.data+0x0):
first defined here
jumeaux: In function `__data_start':
(.data+0x4): multiple definition of `__dso_handle'
/usr/lib/gcc/i486-linux-gnu/4.3.3/crtbegin.o:(.data+0x0): first defined here
jumeaux: In function `_init':
/build/buildd/glibc-2.9/build-tree/i386-libc/csu/crti.S:15: multiple
definition of `_init'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crti.o:/build/buildd/glibc-2.9/build-tree/i386-libc/csu/crti.S:15:
first defined here
/tmp/ccYYjkRp.o: In function `main':
jumeaux.c:(.text+0x0): multiple definition of `main'
jumeaux:(.text+0xb4): first defined here
/tmp/ccYYjkRp.o: In function `initPrimoriel':
jumeaux.c:(.text+0x2b7): multiple definition of `initPrimoriel'
jumeaux:(.text+0x36b): first defined here
/usr/lib/gcc/i486-linux-gnu/4.3.3/crtend.o:(.dtors+0x0): multiple
definition of `__DTOR_END__'
jumeaux:(.dtors+0x4): first defined here
collect2: ld a retourné 1 code d'état d'exécution
remy@remy-desktop:~/Bureau/cJumeaux$ gcc -O2 jumeaux jumeaux.c -lgmp
jumeaux: In function `_start':
/build/buildd/glibc-2.9/csu/../sysdeps/i386/elf/start.S:65: multiple
definition of `_start'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crt1.o:/build/buildd/glibc-2.9/csu/../sysdeps/i386/elf/start.S:65:
first defined here
jumeaux:(.rodata+0x0): multiple definition of `_fp_hw'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crt1.o:(.rodata+0x0):
first defined here
jumeaux: In function `_fini':
/build/buildd/glibc-2.9/csu/../sysdeps/generic/initfini.c:109: multiple
definition of `_fini'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crti.o:/build/buildd/glibc-2.9/csu/../sysdeps/generic/initfini.c:109:
first defined here
jumeaux:(.rodata+0x4): multiple definition of `_IO_stdin_used'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crt1.o:(.rodata.cst4+0x0):
first defined here
jumeaux: In function `__data_start':
(.data+0x0): multiple definition of `__data_start'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crt1.o:(.data+0x0):
first defined here
jumeaux: In function `__data_start':
(.data+0x4): multiple definition of `__dso_handle'
/usr/lib/gcc/i486-linux-gnu/4.3.3/crtbegin.o:(.data+0x0): first defined here
jumeaux: In function `_init':
/build/buildd/glibc-2.9/build-tree/i386-libc/csu/crti.S:15: multiple
definition of `_init'
/usr/lib/gcc/i486-linux-gnu/4.3.3/../../../../lib/crti.o:/build/buildd/glibc-2.9/build-tree/i386-libc/csu/crti.S:15:
first defined here
/tmp/ccc12Vkv.o: In function `initPrimoriel':
jumeaux.c:(.text+0x0): multiple definition of `initPrimoriel'
jumeaux:(.text+0x36b): first defined here
/tmp/ccc12Vkv.o: In function `main':
jumeaux.c:(.text+0x50): multiple definition of `main'
jumeaux:(.text+0xb4): first defined here
/usr/lib/gcc/i486-linux-gnu/4.3.3/crtend.o:(.dtors+0x0): multiple
definition of `__DTOR_END__'
jumeaux:(.dtors+0x4): first defined here
collect2: ld a retourné 1 code d'état d'exécution
remy@remy-desktop:~/Bureau/cJumeaux$
et avec
remy@remy-desktop:~/Bureau/cJumeaux$ time java -server jumeaux
nb de pas 381
qt nb premier consecutif 45
14972714672980313132367809339788888949220174742427921914701198017084278426205606579
14972714672980313132367809339788888949220174742427921914701198017084278426205606581
real 0m11.506s
user 0m11.893s
sys 0m0.416s
remy@remy-desktop:~/Bureau/cJumeaux$
>>> Et pour le test, comment le fais-tu ? Ça ne devrait pas être
>>> difficile à distribuer.
>>>
>> disons que j'ai actuellement la flemme de coder mon propre test de
>> primalité donc j'utilise celui qui est fourni de base
>> dans gmp et biginteger ce qui si j'en crois mes lectures ils utilisent
>> tous les 2 un test de primalité Miller-Rabin
>>
>> http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Miller-Rabin
>>
>>
>> remy
>
> Et tu as regardé ce qui consommait du temps exactement ?
> Est-ce que ta boucle est répétée beaucoup de fois ? Tu ne pourrais pas
> lancer plusieurs itérations en même temps plutôt qu'utiliser un autre
> algo de test pour tes nombres premiers ?
c'est pas bête comme idée je peux effectivement tester plusieurs
candidat mais si vous voyez passer un test multi thread je suis toujours
preneur
remy
remy
>
>
> Bref il faut comparer ce qui est comparable.
la mesure de temps a été faite avec les mêmes
valeurs bien sur, 500 pour le c et 500 pour java
nb de pas 381
qt nb premier consecutif 45
14972714672980313132367809339788888949220174742427921914701198017084278426205606579
14972714672980313132367809339788888949220174742427921914701198017084278426205606581
real 0m11.574s
user 0m12.025s
sys 0m0.448s
remy@remy-desktop:~/Bureau/cJumeaux$
nb de pas 381
qt nb premier consecutif 45
14972714672980313132367809339788888949220174742427921914701198017084278426205606579
14972714672980313132367809339788888949220174742427921914701198017084278426205606581
real 0m34.648s
user 0m34.302s
sys 0m0.016s
remy@remy-desktop:~/Bureau/cJumeaux$
le code fait la même chose par contre je n'ai pas libéré l'espace
parce que je fais un mpz_set(.....) c'est peut être une erreur de ma
part ,possible je ne suis plus vraiment un acro du C
par contre il me semble assez évident que les implémentations sont
différentes je pense que c'est à ce niveau que se fait la différence
puisque le programme passe le plus clair de son temps à faire des tests
de primalité ,la gestion de la mémoire pour ce test ne me parait pas
assez significative au vu des écarts mais je peux me planter
la machine et un Dual-Core avec un core charger a 100 %
processor : 0
vendor_id : GenuineIntel
cpu family : 6
model : 23
model name : Pentium(R) Dual-Core CPU E5300 @ 2.60GHz
stepping : 10
cpu MHz : 1200.000
cache size : 2048 KB
physical id : 0
siblings : 2
core id : 0
cpu cores : 2
apicid : 0
initial apicid : 0
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 13
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge
mca cmov pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm
constant_tsc arch_perfmon pebs bts pni dtes64 monitor ds_cpl vmx est tm2
ssse3 cx16 xtpr pdcm xsave lahf_lm tpr_shadow vnmi flexpriority
bogomips : 5199.88
clflush size : 64
power management:
processor : 1
vendor_id : GenuineIntel
cpu family : 6
model : 23
model name : Pentium(R) Dual-Core CPU E5300 @ 2.60GHz
stepping : 10
cpu MHz : 1200.000
cache size : 2048 KB
physical id : 0
siblings : 2
core id : 1
cpu cores : 2
apicid : 1
initial apicid : 1
fdiv_bug : no
hlt_bug : no
f00f_bug : no
coma_bug : no
fpu : yes
fpu_exception : yes
cpuid level : 13
wp : yes
flags : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov
pat pse36 clflush dts acpi mmx fxsr sse sse2 ss ht tm pbe nx lm
constant_tsc arch_perfmon pebs bts pni dtes64 monitor ds_cpl vmx est tm2
ssse3 cx16 xtpr pdcm xsave lahf_lm tpr_shadow vnmi flexpriority
bogomips : 5199.95
clflush size : 64
power management:
remy
batyann811
>
> la mesure de temps a �t� faite avec les m�mes
> valeurs bien sur, 500 pour le c et 500 pour java
Mais qui te dit que cette valeur a la m�me signification dans les 2
langages. J'ai rapidement consult� les docs des 2 API et elle ne disent
pas grand chose sur ce qu'elles font de ce param�tres. Si tu veux
vraiment savoir il faut te plonger dans les sources...
La doc de GMP conseille une valeur entre 5 et 10 alors pourquoi 500 ?
remy
> remy a écrit :
>>
>> la mesure de temps a été faite avec les mêmes
>
> langages. J'ai rapidement consulté les docs des 2 API et elle ne disent
> pas grand chose sur ce qu'elles font de ce paramètres. Si tu veux
>
> La doc de GMP conseille une valeur entre 5 et 10 alors pourquoi 500 ?
>
>
batyann811
> gcc -o2 jumeaux jumeaux.c -lgmp
gcc -o jumeaux -O2 -lgmp jumeaux.c
Yliur
remy <re...@fctpas.fr> a écrit :
> [... plein d'erreurs]
Non, pas comme ça :)
Il faut garder le -o pour créer les objets, mais ajouter -O2 (avec un O
majuscule) pour activer les optimisations lors de la compilation.
Après si c'est une bibliothèque externe qui consomme le temps de
calcul ça ne changera pas grand chose.
>
> et avec
> remy@remy-desktop:~/Bureau/cJumeaux$ time java -server jumeaux
>
> nb de pas 381
> qt nb premier consecutif 45
> 14972714672980313132367809339788888949220174742427921914701198017084278426205606579
> 14972714672980313132367809339788888949220174742427921914701198017084278426205606581
>
> real 0m11.506s
> user 0m11.893s
> sys 0m0.416s
> remy@remy-desktop:~/Bureau/cJumeaux$
Tiens, ça n'a rien changé ?
batyann811
> batyann811 a �crit :
>> remy a �crit :
>>>
>>> la mesure de temps a �t� faite avec les m�mes
>>
>> langages. J'ai rapidement consult� les docs des 2 API et elle ne
>> disent pas grand chose sur ce qu'elles font de ce param�tres. Si tu
>>
>> La doc de GMP conseille une valeur entre 5 et 10 alors pourquoi 500 ?
>>
>>
>
Je viens d'essayer ton code C avec 500, 100 et 10.
La sortie des 3 versions est la m�me mais les temps d'ex�cution n'ont
rien � voir.
500 : 15.5s
100 : 3.5s
10 : 0.9s
Moralit� ce param�tre est foutrement important.
JKB
Re: recherche code multi thread java pour test de primalite,
remy ?crivait dans fr.comp.lang.java :
> Yliur a écrit :
>> Le Tue, 22 Dec 2009 11:52:21 +0100
>> remy <re...@fctpas.fr> a écrit :
>>
>>> bonjour
>>>
>>> vous ne connaitriez pas un bout de code multi thread
>>> java qui ferait un test de primalité
>>> histoire de me servir de tous les coeurs de la machine
>>> c'est pour booster un peu le code
>>>
>>> http://cjoint.com/data/mwlRFNicX7.htm
>>>
>>> vu que la même implémentation en c
>>> http://cjoint.com/data/mwlL3wfBsX.htm
>>>
>>> c'est avérée moins rapide
>>> à titre perso je ne m'attendais pas à un écart aussi grand
>>>
>>>
>>>
>>> merci remy
>>
>> La version C est *moins* rapide ?
>> Quel est l'écart ?
>
> il te faut la libgmp voir avec synaptic et gcc
Je t'ai déjà dit de commencer par coller in -O3 sur la compilation
de la libgmp et la même chose sur ton code (encore qu'en
l'occurrence, ça ne devrait pas changer grand'chose pour ton code).
Avoir une telle différence tend à montrer qu'il y a un loup.
> gcc -o jumeaux jumeaux.c -lgmp
> time ./jumeaux
>
> real 0m34.833s
> user 0m34.230s
> sys 0m0.000s
> remy@remy-desktop:~/Bureau/cJumeaux$
>
> javac jumeaux.java
> time java jumeaux
>
> real 0m12.011s
> user 0m12.429s
> sys 0m0.416s
> remy@remy-desktop:~/Bureau/cJumeaux$
>
>
>>
>> Et pour le test, comment le fais-tu ? Ça ne devrait pas être difficile
>> à distribuer.
>>
>
> disons que j'ai actuellement la flemme de coder mon propre test de
> primalité donc j'utilise celui qui est fourni de base
> dans gmp et biginteger ce qui si j'en crois mes lectures ils utilisent
> tous les 2 un test de primalité Miller-Rabin
>
> http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Miller-Rabin
Je t'ai déjà dit aussi qu'avec le même algorithme de base, on peut
coder des choses qui ont des performances parfaitement divergentes.
JKB
--
Le cerveau, c'est un véritable scandale écologique. Il représente 2% de notre
masse corporelle, mais disperse à lui seul 25% de l'énergie que nous
consommons tous les jours.
remy
> remy a écrit :
>> batyann811 a écrit :
>>> remy a écrit :
>>>>
>>>> la mesure de temps a été faite avec les mêmes
>>>
>>> langages. J'ai rapidement consulté les docs des 2 API et elle ne
>>> disent pas grand chose sur ce qu'elles font de ce paramètres. Si tu
>>>
>>> La doc de GMP conseille une valeur entre 5 et 10 alors pourquoi 500 ?
>>>
>>>
>>
>
> Je viens d'essayer ton code C avec 500, 100 et 10.
>
> rien à voir.
>
> 500 : 15.5s
> 100 : 3.5s
> 10 : 0.9s
>
comme tu dis j'avais mis 500 parce que pour moi c' était le nombre de
recherches qui en comporte plusieurs tests mais c'est clairement pas
ça avec 10 et des très grands nombres cela semble tenir la route et le c
est plus rapide
remy
Yliur
> >> Et pour le test, comment le fais-tu ? Ça ne devrait pas être
> >> difficile à distribuer.
> >>
> >
> > disons que j'ai actuellement la flemme de coder mon propre test de
> > primalité donc j'utilise celui qui est fourni de base
> > dans gmp et biginteger ce qui si j'en crois mes lectures ils
> > utilisent tous les 2 un test de primalité Miller-Rabin
> >
> > http://fr.wikipedia.org/wiki/Test_de_primalit%C3%A9_de_Miller-Rabin
>
> Je t'ai déjà dit aussi qu'avec le même algorithme de base, on
> peut coder des choses qui ont des performances parfaitement
> divergentes.
>
> JKB
>
La deuxième partie de son message ne concernait pas les performances,
il cherchait comment paralléliser son calcul pour utiliser tous les
coeurs de sa machine.
JKB
Re: recherche code multi thread java pour test de primalite,
Le gros du calcul étant fait dans la libgmp, il faudrait aussi
regarder de près les options de compilation de ladite bibliothèque.
JKB
Le problème, vois-tu, c'est que tu viens de déplacer une discussion
d'un forum à un autre parce que ce qui t'était dit sur fsm ne te
convenait pas. Tu n'as pas l'impression de prendre les gens qui
prennent la peine de te répondre pour eds imbéciles, parfois ?
Est-ce que je ne t'avais pas dit de vérifier ce que faisaient des
routines dans les _deux_ langages, voire de les coder _toi-même_ ?
Quant à la dernière assertion, je persiste et signe.
JKB
Re: recherche code multi thread java pour test de primalite,
Un test de primalité de Miller-Rabin, c'est une façon de faire, un
algorithme. Après, tu peux l'implanter intelligemment ou de façon
particulièrement bête (sans toucher l'algorithme de base, juste en
réordonnançant les instructions ou en utilisant des variables
temporaires ou toutes autres choses) et les performances réelles en
seront affectées, et souvent assez sensiblement. Dire qu'on utilise
un tel test dans un programme écrit en C et dans un truc écrit en
Java ne présuppose absolument rien de l'optimalité des deux
routines. Tu peux avoir un code C optimisé aux petits oignons et un
code Java écrit par un programmeur aux pieds tendres. Tu peux aussi
avoir le contraire. C'est même tellement sensible que les
implantations efficaces d'une truc comme Lapack sont _différentes_
d'un processeur cible à l'autre !
Cordialement,
Yliur
JKB <knat...@koenigsberg.fr> a écrit :
Ben ok, mais je ne vois toujours pas le lien avec cette partie de la
choucroute.
batyann811
>
> Le gros du calcul étant fait dans la libgmp, il faudrait aussi
> regarder de près les options de compilation de ladite bibliothèque.
>
Et surtout lire la doc avant de s'en servir...
remy
l'on va pas s'engueuler un 23 décembre mais vois tu j'ai un contexte 2
langages avec 2 routines de tests je cherche à utiliser
la plus rapide avec une doc des plus évasives sur l'utilisation des
dites routines et toi tu me parles d'implémentation ,des différents
temps d'utilisation des threads de la jmv ou de coder ma propre routine
sur le fond tu as raison mais cela ne me permet pas d'utiliser la plus
rapide ,histoire de faire tourner le bouzin avant se soir 18h
défoncer les portes ouvertes c'est sur fcold
mon dernier test
qt nb premier consecutif 155
real 134m34.637s
user 132m52.426s
sys 0m30.410s
remy@remy-desktop:~/Bureau/cJumeaux$
qt nb premier consecutif 155
real 47m57.615s
user 47m25.126s
sys 0m0.760s
remy@remy-desktop:~/Bureau/cJumeaux$
avec 10 comme paramètre par contre
si j'augmente le paramètre la tendance s'inverse ,java est plus rapide
ben ça je ne l'avais pas vu ,un 10 semble aussi efficace qu'un 500 java
avec des résultats identiques
pour le reste si j'ai rien dans une semaine je brancherai le cerveau
histoire de gagner quelques cycles si cela ne donne rien
mais pas pour l'instant
tien d'ailleur
avec
http://cjoint.com/confirm.php?cjoint=mxkWUhVUO4
et
gcc -o jumeaux -O2 -lgmp jumeaux.c
#!/bin/bash
screen
./jumeaux
comment je fais pour rerentrer dedans
remy
> Tu n'as pas l'impression de prendre les gens qui
> prennent la peine de te répondre pour eds imbéciles, parfois ?
> Est-ce que je ne t'avais pas dit de vérifier ce que faisaient des
> routines dans les _deux_ langages, voire de les coder _toi-même_ ?
>
> Quant à la dernière assertion, je persiste et signe.
>
> JKB
>
remy
>
> comment je fais pour rerentrer dedans
>
screen -S test
./jumeaux
Ctrl-a Ctrl-d
screen -r test
remy
remy a écrit :
>
> comment je fais pour rerentrer dedans
>
screen -S test
./jumeaux
Ctrl-a Ctrl-d
screen -r test
et ne pas oublier le plus important bonne fête
remy
steph
Les deux biblioth�ques impl�mentent le m�me algorithme pour cette fonction.
Le param�tre a la m�me signification. Apr�s, les impl�mentations peuvent
diff�rer dans leur efficacit�.
Je ne vois pas ce qu'il y a de surprenant � ce que java soit plus rapide
sur un calcul long.
Le JIT a tout le temps de faire son travail et il n'est pas rare qu'un
JIT soit plus efficace qu'un compilateur.
batyann811
> Le param�tre a la m�me signification.
Tu es certain de �a ? Rien ne le dit dans la doc. C'est possible mais �
moins d'avoir regard� les sources...
steph
Il a �t� dit que "tous les 2 un test de primalit� Miller-Rabin"
Si tu ne remets pas ceci en cause, cet algorithme a besoin d'un
param�tre d'incertitude qui a la m�me signification (nombre de boucle)
dans toutes les impl�mentations.
batyann811
>
> Il a �t� dit que "tous les 2 un test de primalit� Miller-Rabin"
>
> Si tu ne remets pas ceci en cause, cet algorithme a besoin d'un
> dans toutes les impl�mentations.
Je ne remet pas �a en cause. Mais � la lecture des documentations j'ai
un doute sur le fait que le parametre soit utilis� exactement de la m�me
mani�re.
API java :
certainty - a measure of the uncertainty that the caller is willing to
tolerate: if the call returns true the probability that this BigInteger
is prime exceeds (1 - 1/2certainty). The execution time of this method
is proportional to the value of this parameter.
API C :
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�.
Bref je ne dis pas que l'utilisation des 2 param�tres n'est pas la m�me
mais � la lecture des documentations on peut avoir un doute que la
lecture des sources pourrait lever mais comme je m'en fiche un peu...
Samuel Devulder
> steph a �crit :
>>
>> Il a �t� dit que "tous les 2 un test de primalit� Miller-Rabin"
>>
>> Si tu ne remets pas ceci en cause, cet algorithme a besoin d'un
>> param�tre d'incertitude qui a la m�me signification (nombre de boucle)
>> dans toutes les impl�mentations.
>
> Je ne remet pas �a en cause. Mais � la lecture des documentations j'ai
> un doute sur le fait que le parametre soit utilis� exactement de la m�me
> mani�re.
>
> API java :
>
> certainty - a measure of the uncertainty that the caller is willing to
> tolerate: if the call returns true the probability that this BigInteger
> is prime exceeds (1 - 1/2certainty). The execution time of this method
> is proportional to the value of this parameter.
Le fait que ce soit proportionnel plaide pour un truc qui varie
lin�airement tel le nombre de tests � effectuer.
>
> API C :
> 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�.
Idem. Nombre de tests.
Le source java (open jdk 6) est dispo ici:
http://www.docjar.com/html/api/java/math/BigInteger.java.html
Il y a bien une boucle sur le nombre de tests (qui est +/- le param�tre
pass� en argument de isProbablePrime()):
885 private boolean passesMillerRabin(int iterations, Random rnd) {
../..
896 for (int i=0; i<iterations; i++) {
sam.
batyann811
>
>
> Idem. Nombre de tests.
>
> Le source java (open jdk 6) est dispo ici:
> http://www.docjar.com/html/api/java/math/BigInteger.java.html
>
> Il y a bien une boucle sur le nombre de tests (qui est +/- le param�tre
> pass� en argument de isProbablePrime()):
En lisant vite fait le code de primeToCertainty appel� par
isProbablePrime() on constate que dans certain cas (entier de plus de
100 bits) en plus du test de Miller Rabin il y a un test LucasLehmer.
En plus la conversion entre le nombre d'it�ration et le param�tre
certainty ne me semble pas si direct que �a (lignes 720 � 744).
Samuel Devulder
> En lisant vite fait le code de primeToCertainty appel� par
> isProbablePrime() on constate que dans certain cas (entier de plus de
> 100 bits) en plus du test de Miller Rabin il y a un test LucasLehmer.
>
> En plus la conversion entre le nombre d'it�ration et le param�tre
> certainty ne me semble pas si direct que �a (lignes 720 � 744).
En fait c'est un plafond sur le nombre de tests de Miller-Rabin en
fonction du nombre de bits.
On a le tableau suivant:
nb bits | max tests Miller-Rabin | Lucas-Lehmer
-----------+-------------------------+-------------
2..99 | 50 | non
100..255 | 27 | oui
256..511 | 15 | oui
512..767 | 8 | oui
768..1023 | 4 | oui
1024..inf | 2 | oui
Il y a donc un �quilibre entre les deux tests suivant le nombre de bits.
Ces param�tres doivent avoir �t� choisis pour correspondre aux exigences
de la norme X9.80 pour les algos probabilistes: erreur inf�rieure �
environ pow(2,-100) (<= 1E-30) d'apr�s
http://webstore.ansi.org/RecordDetail.aspx?sku=ANSI+X9.80%3A2005
Je me demande si le test de isProbablePrime() est fiable ou pas
finalement. Une erreur de 1E-30 c'est suffisant pour l'industrie des
cartes � puces ou financi�re, mais dans l'absolu c'est pas 0. Il doit y
avoir des nombres compos�s qui sont d�clar�s prime, mais ceux l�
arrivent avec un taux d'erreur beaucoup plus bas que celui des mat�riels
qui exploitent ces nombres, donc finalement ces erreurs ne comptent pas
vraiment dans la pratique industrielle.
Apparement la combinaison Miller-Rabin + Lucas-Lehmer est utilis�e dans
Math�matica depuis sa v2.2
(http://mathworld.wolfram.com/Rabin-MillerStrongPseudoprimeTest.html).
Ils disent que cette combinaison est connue fiable uniquement pour les
nombres plus petits que 1E16 (53 bits), mais qu'on a pas encore trouv�
de contre exemple pour les nombres plus grands.
Ca serait bien d'avoir un algo 100% exact dans BigInteger pour les tr�s
grand nombres. Ils en existe et ils sont polynomiaux en O(log12 n):
* http://crypto.cs.mcgill.ca/~stiglic/PRIMES_P_FAQ.html
* http://members.cox.net/mathmistakes/primes.htm.
sam.