sqrt.cpp

(plain text)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * Compile-time square root algorithm (or how not to do a square root)
 * Shane Beasley (sbeasley@cs.uic.edu)
 **/

namespace eloi {
  template <unsigned long N, unsigned long Lo = 1, unsigned long Hi = N>
  struct Sqrt {
    enum {
      median = Lo + (Hi - Lo + 1) / 2,
      is_left = N < median * median,
      new_lo = is_left ? Lo         : median,
      new_hi = is_left ? median - 1 : Hi,
      value = Sqrt<N, new_lo, new_hi>::value
    };
  };

  template <unsigned long N, unsigned long M>
  struct Sqrt<N, M, M> { enum { value = M }; };
}

template <bool> struct enforce;
template <> struct enforce<true> { };

template <unsigned long N>
struct check {
  enum {
    x = sizeof(enforce<(eloi::Sqrt<N * N - 1>::value == N - 1)>),
    y = sizeof(enforce<(eloi::Sqrt<N * N>::value == N)>),
    z = sizeof(enforce<(eloi::Sqrt<N * N + 1>::value == N)>),
    valid = check<N - 1>::valid
  };
};

template <>
struct check<1> {
  enum { valid = true };
};

template struct check<50>;

int main () { return 0; }