ProblemsTemplatesEuclid, evaluated by the compiler
IntermediateTemplates

Euclid, evaluated by the compiler

Context

A fixed-point arithmetic class wants to reduce its ratio at compile time — the denominators are template parameters, so the GCD must be one too. The Euclidean algorithm is two lines; the exercise is making the compiler run them.

Task

Implement gcd_v<A, B> — the greatest common divisor as a compile-time constant. gcd_v<18, 12> == 6, checked by static_assert.

Constraints

  • gcd_v<A, B> is usable in static_assert
  • Coprime numbers give 1; gcd_v<X, X> gives X
  • Argument order does not matter
  • Recursion or constexpr — your choice

Before you code

  • Why does the Euclidean step gcd(a, b) = gcd(b, a % b) terminate?
  • Which variant is easier to read here: template recursion or a constexpr function?
  • Where does std provide this? (std::gcd, <numeric>)

Tests

  • #1Classic cases
  • #2Order and edge cases

Hints

Hint 1

gcd(a, 0) is a; otherwise gcd(a, b) = gcd(b, a % b). That is the whole algorithm.

Hint 2

A constexpr helper function with a loop keeps the variable template a one-liner.

Editorgcd-compile-time.cpp
Results

Hit Submit (or ⌘/Ctrl + ↵) — test results will show up here.