Chapitre 86 : assembleur ARM 64 bits factorisation d'un nombre et threads

Voici un programme facteurthread64.s  écrit pendant la période de confinement et qui marie calculs  pour trouver un facteur d’un grand nombre  et utilisation de threads.

En effet c’est souvent un challenge qui est proposé pour découvrir les problèmes liés à la recherche d’un facteur d’un grand nombre  cad ici à un maximum de 2 puissance 64 – 1.

Pour cela, nous allons d’abord vérifier que le nombre n’est pas premier puis lancer un thread qui va chercher un petit facteur, lancer un thread qui va chercher un facteur proche de la racine carrée et enfin un thread qui va rechercher un facteur quelconque.

Dès qu’un thread aura trouvé un facteur, il sera affiché et on terminera les 2 autres threads.

Pour déterminer si un nombre est premier, j’ai utilisé le test de Fermat (voir wikipedia) qui vérifie si le calcul de x puissance (nombre-1) modulo nombre est divisible par nombre. Ici j’ai pris des valeurs de x égales à 2, 3, 5, 7, 11, 13 et 17 ce qui devrait être suffisant pour la plage des nombres de 64 bits.

Pour le calcul modulo, j’au du écrire une fonction de division d’un nombre de 128 bits par un nombre de 64 bits qui doit être améliorée.

Les 2 premières recherches d’un petit facteur ou d’un facteur proche de la racine carrée ne posent pas de problème (peut être le calcul de la racine carrée d’un nombre !!).

La 3^ième recherche d’un facteur quelconque est faite à l’aide de l’algorithme Rho de Pollard (voir wikipedia ou autres sites d’algorithmique). Là aussi il faut utiliser une division d’un nombre de 128 bits par un nombre de 64 bits si l’on veut décomposer des nombres proche de 2 puissance 63.

Après la vérification de la primalité du nombre, le programme effectue le lancement des 3 threads fils à l’aide de l’appel système Linux CLONE puis se contente d’attendre la fin d’un des threads fils. Pour cela j’utilise l’appel système WAIT4 auquel je passe les pid de chaque fils. J’ai essayé d’utiliser l’appel WAITID mais je ne suis pas arrivé à l’utiliser correctement.

Dès qu’un thread se termine, le programme maitre arrête les 2 fils restant en utilisant l’appel système TKILL et en passant leur N° de pid.

Pour de petits nombres, ce programme fonctionnait correctement après les corrections des petites erreurs habituelles. Pour de plus grands nombres ce programme ne marchait plus car certains tests s’effectuaient sur des valeurs signées (codes lt ou gt par exemples) alors qu’il faut effectuer des tests en valeurs non signées (codes lo ou hi).

Après correction, il restait une erreur résiduelle pour des nombres  dont la division 128 devait s’effectuer avec un diviseur de 64 chiffres significatifs. J’ai mis du temps à trouver où était mon erreur.

En effet l’algorithme que j’utilise compare 2 nombres de 64 bits pour voir si on peut soustraire l’un de l’autre puis décale le reste d’un bit sur la gauche. Et dans la première version, je perdais ce bit !!. Dans la nouvelle version, le décalage du reste de 64 bits nécessite l’utilisation du registre x8 pour conserver le bit le plus à gauche.

Et c’est pourquoi aux lignes 848 et 849, vous trouvez une soustraction et non pas une comparaison. La soustraction permet de gérer la retenue et de pouvoir la déduire du registre x8.

Jusqu’à maintenant, je n’ai pas trouvé de nouvelles erreurs dans ce programme qui trouve le bon résultat en quelques secondes.