Re: A propos de nombres premiers
Publié : ven. 21/oct./2016 10:13
@djes,
Tu mets bien le doigt sur le bon point. Pour traiter des plages où la portée est réduite, le traitement par bits est intéressant par rapport à la compression de la représentation des nombres.
Je crois avoir beaucoup travaillé, dans ma vie sur le sujet, pour savoir qu'on ne peut pas en attendre grand chose de plus.
La limite des algorithmes de traitements sur les nombres premiers tient beaucoup plus au fait que pour en traiter de grandes quantités, il faut dresser des mécanismes encombrants, et l'approche permettant de "plier" l'encombrement est une approche qui libère partiellement de cette limite.
Maintenant, jusqu'à prochainement, j'ai limité la portée de mon travail sur le sujet à une représentation 64 bits (donc d'une façon ou d'une autre à des nombres dans la plage 0 - 1e18).
Dans une étape prochaine, je vais m'intéresser à la méthode induite pour dépasser cette contrainte. Ce sera par l'utilisation d'une arithmétique représentative des nombres en 128, 256, 512 bits tout en utilisant le composant clef, le processeur, qui lui reste un processeur 64 bits (je pense que ce sera encore le cas pour un certain temps !). Et dans cette prochaine étape, je voudrais parvenir à dépasser la limite des 64 bits en entrenant un niveau de performances aussi canon.
Je suis en train de m'acharner en temps partiel ces jours-ci pour rédiger une version qui finalisera l'étape actuelle, et dans laquelle les performances seront je crois sensiblement améliorées, en vue de passer aux nombres représentés sur plus de 64 bits.
Entre temps mon matheux de coéquipier sur ce projet m'a donné du grain à moudre pour ajouter une touche au processus de calcul, en installant des tests rigoureux de validation des résultats. Parce que là-dedans, il faut en plus amener la preuve que les suites de premiers que donnent les programmes sont bien vraies et que le programmeur pas plus que le calculateur ne commentent d'erreur
Je mettrai ici les points intéressants dans une proche livraison de code mis à jour.
Tu mets bien le doigt sur le bon point. Pour traiter des plages où la portée est réduite, le traitement par bits est intéressant par rapport à la compression de la représentation des nombres.
Je crois avoir beaucoup travaillé, dans ma vie sur le sujet, pour savoir qu'on ne peut pas en attendre grand chose de plus.
La limite des algorithmes de traitements sur les nombres premiers tient beaucoup plus au fait que pour en traiter de grandes quantités, il faut dresser des mécanismes encombrants, et l'approche permettant de "plier" l'encombrement est une approche qui libère partiellement de cette limite.
Maintenant, jusqu'à prochainement, j'ai limité la portée de mon travail sur le sujet à une représentation 64 bits (donc d'une façon ou d'une autre à des nombres dans la plage 0 - 1e18).
Dans une étape prochaine, je vais m'intéresser à la méthode induite pour dépasser cette contrainte. Ce sera par l'utilisation d'une arithmétique représentative des nombres en 128, 256, 512 bits tout en utilisant le composant clef, le processeur, qui lui reste un processeur 64 bits (je pense que ce sera encore le cas pour un certain temps !). Et dans cette prochaine étape, je voudrais parvenir à dépasser la limite des 64 bits en entrenant un niveau de performances aussi canon.
Je suis en train de m'acharner en temps partiel ces jours-ci pour rédiger une version qui finalisera l'étape actuelle, et dans laquelle les performances seront je crois sensiblement améliorées, en vue de passer aux nombres représentés sur plus de 64 bits.
Entre temps mon matheux de coéquipier sur ce projet m'a donné du grain à moudre pour ajouter une touche au processus de calcul, en installant des tests rigoureux de validation des résultats. Parce que là-dedans, il faut en plus amener la preuve que les suites de premiers que donnent les programmes sont bien vraies et que le programmeur pas plus que le calculateur ne commentent d'erreur

Je mettrai ici les points intéressants dans une proche livraison de code mis à jour.