libjmmcg  release_579_6_g8cffd
A C++ library containing an eclectic mix of useful, advanced components.
gcd.hpp
Go to the documentation of this file.
1 #ifndef LIBJMMCG_CORE_GCD_HPP
2 #define LIBJMMCG_CORE_GCD_HPP
3 
4 /******************************************************************************
5 ** Copyright © 1993 by J.M.McGuiness, coder@hussar.me.uk
6 **
7 ** This library is free software; you can redistribute it and/or
8 ** modify it under the terms of the GNU Lesser General Public
9 ** License as published by the Free Software Foundation; either
10 ** version 2.1 of the License, or (at your option) any later version.
11 **
12 ** This library is distributed in the hope that it will be useful,
13 ** but WITHOUT ANY WARRANTY; without even the implied warranty of
14 ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 ** Lesser General Public License for more details.
16 **
17 ** You should have received a copy of the GNU Lesser General Public
18 ** License along with this library; if not, write to the Free Software
19 ** Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
20 */
21 
22 namespace jmmcg { namespace LIBJMMCG_VER_NAMESPACE {
23 
24 namespace euclid {
25 
26  /// Euclid's Greatest Common Divisor Algorithm.
27  /**
28  * This is best used for the general case of finding the gcd.
29  * The Binary method may be faster than Euclid's Algorithm.
30  *
31  * A one-liner for fun! (But it's slower, as it's got an extra jump...)
32  * for (u=x,v=y;v;r=u%v,u=v,v=r);
33  *
34  * Thanks to Knuth, et al for Euclid's Algorithm and the Binary GCD algorithm.
35  * See his book "Seminumerical Algorithms. Vol 2", pg 320.
36  *
37  * \param x A value greater that zero.
38  * \param y A value greater that zero.
39  *
40  * \see binary::gcd()
41  */
42  template<class V> constexpr inline V
43  gcd(const V x, const V y) noexcept(true) __attribute__((const));
44  template<class V> constexpr inline V
45  gcd(const V x, const V y) noexcept(true) {
46  assert(x>V{} && y>V{});
47  V u=x, v=y;
48  do {
49  const V r=u%v;
50  u=v;
51  v=r;
52  } while (v);
53  return u;
54  }
55 
56 }
57 
58 namespace binary {
59 
60  /// Binary Greatest Common Divisor Algorithm.
61  /**
62  * This method is best suited to integers.
63  *
64  * A one-liner for fun! (But it's slower, as it's got an extra jump...)
65  * for (u=x,v=y;v;r=u%v,u=v,v=r);
66  *
67  * Thanks to Knuth, et al for Euclid's Algorithm and the Binary GCD algorithm.
68  * See his book "Seminumerical Algorithms. Vol 2", pg 320.
69  *
70  * \param x A value greater that zero.
71  * \param y A value greater that zero.
72  *
73  * \see euclid::gcd()
74  */
75  template<class V> constexpr inline V
76  gcd(const V x, const V y) noexcept(true) __attribute__((const));
77  template<class V> constexpr inline V
78  gcd(const V x, const V y) noexcept(true) {
79  assert(x>V{} && y>V{});
80  V k=0, u=x, v=y;
81  for (; !(u&1) && !(v&1); ++k, (u>>=1), (v>>=1));
82  V t=u&1 ? -v : u;
83  do {
84  do {
85  t>>=1;
86  } while (!(t&1));
87  t>0 ? (u=t) : (v=-t);
88  } while ((t=u-v));
89  return u<<k;
90  }
91 
92 }
93 
94 } }
95 
96 #endif