Je voudrais implémenter le test de primalité de Lucas - Lehmer. Pour cela,
j'ai besoin de calculer de nombreuses fois l'opération
s = s²-2 [2^p-1]
On trouve dans la litterature que l'elevation au carré doit se faire avec un
algo de FFT (fast fourier transformation) pour que ce soit rapide.
- Est ce que c'est cet algo qui est utilisé dans l'implémentation de
BigInteger ?
- Est il dans ce cas plus interessant de faire une multiplication ou
d'utiliser la méthode modPow (ou encore autre chose ?)
- Vu que je vais manipuler des grands nombre (sur plus de 20 Mbits), je
voudrais au maximum eviter la duplication des nombres en mémoire. Or, pour
soustraire 2 à s², je n'ai rien trouvé de mieux que l'appel à la méthode add
(ou substract), qui crée un nouveau BigInteger. Ca ne m'a pas l'air très
efficace. Comment faire autrement ?
Enfin, question subsidiaire, est ce qu'il est préferable que j'abandonne
completement BigInteger et que je recode tout de zero ?
Cette action est irreversible, confirmez la suppression du commentaire ?
Signaler le commentaire
Veuillez sélectionner un problème
Nudité
Violence
Harcèlement
Fraude
Vente illégale
Discours haineux
Terrorisme
Autre
Yves Martin
"Vincent Lascaux" writes:
Enfin, question subsidiaire, est ce qu'il est préferable que j'abandonne completement BigInteger et que je recode tout de zero ?
Non, fais confiance à Java dans un premier temps et fais des mesures de temps de calcul (en boucle pour activer la compilation just-in-time aka JIT)
Attention: sur la JVM d'IBM (1.3.1 en tout cas), la compilation JIT sur un calcul de division de BigInteger avec troncature est BUGGÉE ! Dans une boucle, les 20 premiers résultats sont justes et... ensuite ils sont faux car le JIT est passé par là !!
-- Yves Martin
"Vincent Lascaux" <nospam@nospam.org> writes:
Enfin, question subsidiaire, est ce qu'il est préferable que j'abandonne
completement BigInteger et que je recode tout de zero ?
Non, fais confiance à Java dans un premier temps et fais des mesures
de temps de calcul (en boucle pour activer la compilation
just-in-time aka JIT)
Attention: sur la JVM d'IBM (1.3.1 en tout cas), la compilation JIT
sur un calcul de division de BigInteger avec troncature est BUGGÉE !
Dans une boucle, les 20 premiers résultats sont justes et... ensuite
ils sont faux car le JIT est passé par là !!
Enfin, question subsidiaire, est ce qu'il est préferable que j'abandonne completement BigInteger et que je recode tout de zero ?
Non, fais confiance à Java dans un premier temps et fais des mesures de temps de calcul (en boucle pour activer la compilation just-in-time aka JIT)
Attention: sur la JVM d'IBM (1.3.1 en tout cas), la compilation JIT sur un calcul de division de BigInteger avec troncature est BUGGÉE ! Dans une boucle, les 20 premiers résultats sont justes et... ensuite ils sont faux car le JIT est passé par là !!
-- Yves Martin
Vincent Lascaux
Non, fais confiance à Java dans un premier temps et fais des mesures de temps de calcul (en boucle pour activer la compilation just-in-time aka JIT)
Oui, et ben là c'est très lent. Le probleme c'est que je ne sais pas à quel vitesse ca peut aller, mais je pense que faire un modulo 2^p-1 peut se faire de facon bien plus rapide à la main qu'en laissant Java faire...
-- Vincent
Non, fais confiance à Java dans un premier temps et fais des mesures
de temps de calcul (en boucle pour activer la compilation
just-in-time aka JIT)
Oui, et ben là c'est très lent. Le probleme c'est que je ne sais pas à quel
vitesse ca peut aller, mais je pense que faire un modulo 2^p-1 peut se faire
de facon bien plus rapide à la main qu'en laissant Java faire...
Non, fais confiance à Java dans un premier temps et fais des mesures de temps de calcul (en boucle pour activer la compilation just-in-time aka JIT)
Oui, et ben là c'est très lent. Le probleme c'est que je ne sais pas à quel vitesse ca peut aller, mais je pense que faire un modulo 2^p-1 peut se faire de facon bien plus rapide à la main qu'en laissant Java faire...
