Время компиляции LCM / GCD в C

Question

Кто-нибудь знает механизм для вычисления во время компиляции LCM (наименьшего общего кратного) и / или GCD (наибольший общий знаменатель) как минимум из двух чисел в C ( не в C ++ *) 1004 *, я знаю, что там есть шаблонная магия)?

Обычно я использую GCC и напоминаю, что он может вычислять определенные значения во время компиляции, когда известны все входные данные (например, sin, cos и т. Д.).

Я ищу, как это сделать в GCC (желательно способом, который могут обрабатывать другие компиляторы), и надеюсь, что тот же механизм будет работать в Visual Studio.

Answer 1

Я понял это в конце концов ...

#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;
}

Обратите внимание: в зависимости от размера целых чисел вам может понадобиться добавить несколько промежуточных шагов (т. Е. GCD_9, GCD_10 и т. Д.).

Надеюсь, это поможет!

Answer 2

Частично на основе ответа Кевина, вот макропоследовательность, которая имеет ошибку времени компиляции для постоянных значений и ошибки времени выполнения в противном случае.

Он также может быть настроен на включение функции времени некомпиляции, если сбой не возможен.

#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)

Остерегайтесь слишком большого расширения, даже если оно завершится рано, так как компилятор должен полностью подключить все, прежде чем даже выполнить оценку.

Answer 3

Я понимаю, что вы заинтересованы только в реализации на C, но я все равно прокомментировал бы C ++ и шаблонное метапрограммирование. Я не совсем уверен, что это возможно в C ++, так как вам нужны четко определенные начальные условия для прекращения рекурсивного расширения.

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);
}

Это может быть возможно с C ++ 0x, но не с уверенностью 100%.