Exponentiation modulo : portabilité & optimisations GCC
Bonjour,
J'utilise l'algorithme d'exponentiation modulo sur les entiers suivant :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
| unsigned int power(unsigned int a, unsigned int b, unsigned int n)
{
unsigned int r = 1;
while (b > 0) {
if (b % 2)
r = r * a % n;
a = a * a % n;
b /= 2;
}
return r;
} |
Ecris de cette manière, cette fonction a un problème : si n utilise plus de la moitié des bits d'un unsigned int, le résultat des multiplications ne tiendra pas sur un unsigned int et le modulo ne sera calculé que sur la partie basse du produit.
Une solution rapide est de passer par des entiers plus grands :
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
| unsigned int power(unsigned int a, unsigned int b, unsigned int n)
{
unsigned int r = 1;
while (b > 0) {
if (b % 2)
r = static_cast<unsigned long long>(r) * a % n;
a = static_cast<unsigned long long>(a) * a % n;
b /= 2;
}
return r;
} |
Je sais par ailleurs que cette modification ne devrait pas en principe poser de problème sur les x86 : le résultat d'une multiplication de nombres 32bits est toujours sur 64bits, qui plus est déjà dans les registres correspondant au dividende du modulo à calculer. Seulement avec les options d'optimisation courante, GCC génère un appel à la fonction de la librairie standard pour le calcul du modulo sur les long long, et ne profite donc pas de cette opportunité.
Mes questions sont les suivantes :
- Comment s'assurer de la portabilité d'une telle fonction ? En particulier comment s'assurer que les résultats des calculs seront corrects quelle que soit la taille des types (conforme au standard) sur l'architecture ciblée ?
- Comment faire pour que malgré tout, GCC produise un code optimal ? Quelles options de compilation utiliser ?
