3

Does anyone know a mechanism to calculate at compile-time the LCM (Least Common Multiple) and/or GCD (Greatest Common Denominator) of at least two number in C (not C++, I know that template magic is available there)?

I generally use GCC and recall that it can calculate certain values at compile-time when all inputs are known (ex: sin, cos, etc...).

I'm looking for how to do this in GCC (preferably in a manner that other compilers could handle) and hope the same mechanism would work in Visual Studio.

4 Answers 4

6

I figured it out afterall...

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

Note, depending on how large your integers go, you may need to include more intermediate steps (i.e. GCD_9, GCD_10, etc...).

I hope this helps!

7
  • It looks like an interesting solution... do you have any idea how large of arguments it'll take before you need to add more recursion? I'll have to test this out tonight...
    – harningt
    Sep 16, 2008 at 21:28
  • The worst case scenario is for two consecutive fibbonacci numbers (See 'Running Time' section of en.wikipedia.org/wiki/Euclidean_algorithm). For 32-bit unsigned integers, this results in 45 intermediate steps. Unfortunately, MSVC craps out on my machine at 13 steps.
    – Kevin
    Sep 16, 2008 at 21:58
  • It might be possible to extend this to 45 steps if you have a lot of memory on your build machine OR if change a setting in MSVC to add more heap space.
    – Kevin
    Sep 16, 2008 at 21:59
  • And last thing to remember is that things usually progress much quicker. 8 steps was enough for all my random examples. Depending on the numbers you need, 8 steps may be enough.
    – Kevin
    Sep 16, 2008 at 22:00
  • Would changing this to use sequences of something like: #define GCD_1(a,b) ( ((b) != 0) ? GCD_2((b), (a) % (b)) : (a) ) could help MSVC due to reduced operation-stack. I'd also suspect that GCD_last should throw some sort of error...
    – harningt
    Sep 17, 2008 at 0:15
2

Partly based on Kevin's answer, here's a macro-sequence that has compile-time failure for constant-values and run-time errors otherwise.

It could also be configured to pull in a non-compile time function if failure is not an 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)

Beware expanding this too large, even if it would terminate early, since the compiler has to fully plug in everything before even evaluating.

2
  • Errr... this is giving me the original problem I had: error C2124: divide or mod by zero :-(. On what compiler did you test it?
    – Kevin
    Sep 17, 2008 at 4:58
  • After replacing '(a) % (b)' wih '(a) % ((b)+!(b))' I was able to get this to compile. However, the presence of the assert function call does not allow MSVC 2005 to optimize the calculation. The disassembly is full of test and jump calls. :( [but if you remove the assert call, everything works.]
    – Kevin
    Sep 17, 2008 at 5:12
1

I realize your only interested in a C implementation but I thought I'd comment on C++ and template metaprogramming anyway. I'm not completely convinced that it is possible in C++ as you need well defined initial conditions in order to terminate the recursive expansion.

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

This may be possible with C++0x however not %100 certain though.

1
-1
 int gcd(int n1,int n2){
       while(n1!=n2){
        if(n1 > n2) n1 -= n2;
        else n2 -= n1;
    }
    return n1;
}
int lcm(int n1, int n2){
    int total =n1*n2;
    return total/gcd(n1,n2);
}
1
  • 4
    @markSchulman This doesn't answer the question. They're asking for a compile-time solution. Nov 20, 2021 at 17:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.