Compilateur LCM/GCD en C

Question

Est-ce que quelqu'un connaît un mécanisme pour calculer au moment de la compilation le LCM (Least Common Multiple) et/ou GCD (Greatest Common Denominator) d'au moins deux nombres en C (C++, je sais que la magie de modèle est disponible là)?

J'utilise généralement GCC et je rappelle qu'il peut calculer certaines valeurs à la compilation lorsque toutes les entrées sont connues (ex: sin, cos, etc ...).

Je cherche comment faire cela dans GCC (de préférence d'une manière que d'autres compilateurs pourraient gérer) et j'espère que le même mécanisme fonctionnerait dans Visual Studio.

Answer 1

I figured it out ... après tout

#define GCD(a,b) ((a>=b)*GCD_1(a,b)+(a<b)*GCD_1(b,a)) 
#define GCD_1(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_2((b), (a)%((b)+!(b)))) 
#define GCD_2(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_3((b), (a)%((b)+!(b)))) 
#define GCD_3(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_4((b), (a)%((b)+!(b)))) 
#define GCD_4(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_5((b), (a)%((b)+!(b)))) 
#define GCD_5(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_6((b), (a)%((b)+!(b)))) 
#define GCD_6(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_7((b), (a)%((b)+!(b)))) 
#define GCD_7(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_8((b), (a)%((b)+!(b)))) 
#define GCD_8(a,b) ((((!(b)))*(a)) + (!!(b))*GCD_last((b), (a)%((b)+!(b)))) 
#define GCD_last(a,b) (a) 

#define LCM(a,b) (((a)*(b))/GCD(a,b)) 


int main() 
{ 
    printf("%d, %d\n", GCD(21,6), LCM(21,6)); 
    return 0; 
} 

Remarque, selon la taille de vos entiers vont, vous devrez peut-être inclure des étapes intermédiaires (à savoir GCD_9, GCD_10, etc ...).

J'espère que cela aide!

Answer 2

Je réalise que vous êtes uniquement intéressé par une implémentation en C mais je pensais que je ferais un commentaire sur C++ et la métaprogrammation de modèles de toute façon. Je ne suis pas complètement convaincu que cela soit possible en C++ car vous avez besoin de conditions initiales bien définies pour terminer l'expansion récursive.

template<int A, int B> 
struct GCD { 
    enum { value = GCD<B, A % B>::value }; 
}; 

/* 
Because GCD terminates when only one of the values is zero it is impossible to define a base condition to satisfy all GCD<N, 0>::value conditions 
*/ 
template<> 
struct GCD<A, 0> { // This is obviously not legal 
    enum { value = A }; 
}; 

int main(void) 
{ 
    ::printf("gcd(%d, %d) = %d", 7, 35, GCD<7, 35>::value); 
} 

Cela peut cependant être possible avec C++ 0x mais pas certain à 100%.

Answer 3

En partie basé sur la réponse de Kevin, voici une macro-séquence qui a un échec à la compilation pour les erreurs de valeurs constantes et d'exécution autrement.

Il peut également être configuré pour extraire une fonction de temps de non-compilation si l'échec n'est pas une option.

#define GCD(a,b) (((a) > (b)) ? (GCD_1((a), (b))) : (GCD_1((b), (a)))) 

#define GCD_1(a,b) (((b) == 0) ? (a) : GCD_2((b), (a) % (b))) 
#define GCD_2(a,b) (((b) == 0) ? (a) : GCD_3((b), (a) % (b))) 
#define GCD_3(a,b) (((b) == 0) ? (a) : GCD_4((b), (a) % (b))) 
#define GCD_4(a,b) (((b) == 0) ? (a) : GCD_5((b), (a) % (b))) 
#define GCD_5(a,b) (((b) == 0) ? (a) : GCD_6((b), (a) % (b))) 
#define GCD_6(a,b) (((b) == 0) ? (a) : GCD_7((b), (a) % (b))) 
#define GCD_7(a,b) (((b) == 0) ? (a) : GCD_8((b), (a) % (b))) 
#define GCD_8(a,b) (((b) == 0) ? (a) : GCD_9((b), (a) % (b))) 
#define GCD_9(a,b) (assert(0),-1) 

Prenez garde cette expansion trop importante, même si elle mettrait fin au début, étant donné que le compilateur doit brancher complètement dans tout avant même d'évaluer.