ext/boost/boost/pool/detail/gcd_lcm.hpp

   1 // Copyright (C) 2000 Stephen Cleary\r
   2 //\r
   3 // Distributed under the Boost Software License, Version 1.0. (See\r
   4 // accompanying file LICENSE_1_0.txt or copy at\r
   5 // http://www.boost.org/LICENSE_1_0.txt)\r
   6 //\r
   7 // See http://www.boost.org for updates, documentation, and revision history.\r
   8 \r
   9 #ifndef BOOST_POOL_GCD_LCM_HPP\r
  10 #define BOOST_POOL_GCD_LCM_HPP\r
  11 \r
  12 namespace boost {\r
  13 \r
  14 namespace details {\r
  15 namespace pool {\r
  16 \r
  17 // Greatest common divisor and least common multiple\r
  18 \r
  19 //\r
  20 // gcd is an algorithm that calculates the greatest common divisor of two\r
  21 //  integers, using Euclid's algorithm.\r
  22 //\r
  23 // Pre: A > 0 && B > 0\r
  24 // Recommended: A > B\r
  25 template <typename Integer>\r
  26 Integer gcd(Integer A, Integer B)\r
  27 {\r
  28   do\r
  29   {\r
  30     const Integer tmp(B);\r
  31     B = A % B;\r
  32     A = tmp;\r
  33   } while (B != 0);\r
  34 \r
  35   return A;\r
  36 }\r
  37 \r
  38 //\r
  39 // lcm is an algorithm that calculates the least common multiple of two\r
  40 //  integers.\r
  41 //\r
  42 // Pre: A > 0 && B > 0\r
  43 // Recommended: A > B\r
  44 template <typename Integer>\r
  45 Integer lcm(const Integer & A, const Integer & B)\r
  46 {\r
  47   Integer ret = A;\r
  48   ret /= gcd(A, B);\r
  49   ret *= B;\r
  50   return ret;\r
  51 }\r
  52 \r
  53 } // namespace pool\r
  54 } // namespace details\r
  55 \r
  56 } // namespace boost\r
  57 \r
  58 #endif\r