1<html> 2<head> 3<meta http-equiv="Content-Type" content="text/html; charset=UTF-8"> 4<title>Greatest Common Divisor and Least Common Multiple</title> 5<link rel="stylesheet" href="../../../../../doc/src/boostbook.css" type="text/css"> 6<meta name="generator" content="DocBook XSL Stylesheets V1.79.1"> 7<link rel="home" href="../index.html" title="Boost.Integer"> 8<link rel="up" href="../index.html" title="Boost.Integer"> 9<link rel="prev" href="integer.html" title="Integer Type Selection"> 10<link rel="next" href="extended_euclidean.html" title="Extended Euclidean Algorithm"> 11</head> 12<body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"> 13<table cellpadding="2" width="100%"><tr> 14<td valign="top"><img alt="Boost C++ Libraries" width="277" height="86" src="../../../../../boost.png"></td> 15<td align="center"><a href="../../../../../index.html">Home</a></td> 16<td align="center"><a href="../../../../../libs/libraries.htm">Libraries</a></td> 17<td align="center"><a href="http://www.boost.org/users/people.html">People</a></td> 18<td align="center"><a href="http://www.boost.org/users/faq.html">FAQ</a></td> 19<td align="center"><a href="../../../../../more/index.htm">More</a></td> 20</tr></table> 21<hr> 22<div class="spirit-nav"> 23<a accesskey="p" href="integer.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="extended_euclidean.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a> 24</div> 25<div class="section"> 26<div class="titlepage"><div><div><h2 class="title" style="clear: both"> 27<a name="boost_integer.gcd_lcm"></a><a class="link" href="gcd_lcm.html" title="Greatest Common Divisor and Least Common Multiple">Greatest Common Divisor and Least 28 Common Multiple</a> 29</h2></div></div></div> 30<div class="toc"><dl class="toc"> 31<dt><span class="section"><a href="gcd_lcm.html#boost_integer.gcd_lcm.introduction">Introduction</a></span></dt> 32<dt><span class="section"><a href="gcd_lcm.html#boost_integer.gcd_lcm.synopsis">Synopsis</a></span></dt> 33<dt><span class="section"><a href="gcd_lcm.html#boost_integer.gcd_lcm.gcd_function_object">GCD Function 34 Object</a></span></dt> 35<dt><span class="section"><a href="gcd_lcm.html#boost_integer.gcd_lcm.lcm_function_object">LCM Function 36 Object</a></span></dt> 37<dt><span class="section"><a href="gcd_lcm.html#boost_integer.gcd_lcm.run_time">Run-time GCD & LCM 38 Determination</a></span></dt> 39<dt><span class="section"><a href="gcd_lcm.html#boost_integer.gcd_lcm.compile_time">Compile time GCD 40 and LCM determination</a></span></dt> 41<dt><span class="section"><a href="gcd_lcm.html#boost_integer.gcd_lcm.gcd_header">Header <boost/integer/common_factor.hpp></a></span></dt> 42<dt><span class="section"><a href="gcd_lcm.html#boost_integer.gcd_lcm.demo">Demonstration Program</a></span></dt> 43<dt><span class="section"><a href="gcd_lcm.html#boost_integer.gcd_lcm.rationale">Rationale</a></span></dt> 44<dt><span class="section"><a href="gcd_lcm.html#boost_integer.gcd_lcm.gcd_history">History</a></span></dt> 45<dt><span class="section"><a href="gcd_lcm.html#boost_integer.gcd_lcm.gcd_credits">Credits</a></span></dt> 46</dl></div> 47<div class="section"> 48<div class="titlepage"><div><div><h3 class="title"> 49<a name="boost_integer.gcd_lcm.introduction"></a><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.introduction" title="Introduction">Introduction</a> 50</h3></div></div></div> 51<p> 52 The class and function templates in <boost/math/common_factor.hpp> 53 provide run-time and compile-time evaluation of the greatest common divisor 54 (GCD) or least common multiple (LCM) of two integers. These facilities are 55 useful for many numeric-oriented generic programming problems. 56 </p> 57</div> 58<div class="section"> 59<div class="titlepage"><div><div><h3 class="title"> 60<a name="boost_integer.gcd_lcm.synopsis"></a><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.synopsis" title="Synopsis">Synopsis</a> 61</h3></div></div></div> 62<pre class="programlisting"><span class="keyword">namespace</span> <span class="identifier">boost</span> 63<span class="special">{</span> 64<span class="keyword">namespace</span> <span class="identifier">integer</span> 65<span class="special">{</span> 66 67<span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span> <span class="special">></span> 68 <span class="keyword">class</span> <span class="identifier">gcd_evaluator</span><span class="special">;</span> 69<span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span> <span class="special">></span> 70 <span class="keyword">class</span> <span class="identifier">lcm_evaluator</span><span class="special">;</span> 71 72<span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span> <span class="special">></span> 73 <span class="keyword">constexpr</span> <span class="identifier">IntegerType</span> <span class="identifier">gcd</span><span class="special">(</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">b</span> <span class="special">);</span> 74<span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span> <span class="special">></span> 75 <span class="keyword">constexpr</span> <span class="identifier">IntegerType</span> <span class="identifier">lcm</span><span class="special">(</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">b</span> <span class="special">);</span> 76<span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span><span class="special">,</span> <span class="keyword">typename</span><span class="special">...</span> <span class="identifier">Args</span> <span class="special">></span> 77 <span class="keyword">constexpr</span> <span class="identifier">IntegerType</span> <span class="identifier">gcd</span><span class="special">(</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">b</span><span class="special">,</span> <span class="identifier">Args</span> <span class="keyword">const</span><span class="special">&...</span> <span class="special">);</span> 78<span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span><span class="special">,</span> <span class="keyword">typename</span><span class="special">...</span> <span class="identifier">Args</span> <span class="special">></span> 79 <span class="keyword">constexpr</span> <span class="identifier">IntegerType</span> <span class="identifier">lcm</span><span class="special">(</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">b</span><span class="special">,</span> <span class="identifier">Args</span> <span class="keyword">const</span><span class="special">&...</span> <span class="special">);</span> 80 81<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">I</span><span class="special">></span> 82<span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="identifier">I</span><span class="special">>::</span><span class="identifier">value_type</span><span class="special">,</span> <span class="identifier">I</span><span class="special">></span> 83 <span class="identifier">gcd_range</span><span class="special">(</span><span class="identifier">I</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">I</span> <span class="identifier">last</span><span class="special">);</span> 84<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">I</span><span class="special">></span> 85<span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="identifier">I</span><span class="special">>::</span><span class="identifier">value_type</span><span class="special">,</span> <span class="identifier">I</span><span class="special">></span> 86 <span class="identifier">lcm_range</span><span class="special">(</span><span class="identifier">I</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">I</span> <span class="identifier">last</span><span class="special">);</span> 87 88<span class="keyword">typedef</span> <span class="emphasis"><em>see-below</em></span> <span class="identifier">static_gcd_type</span><span class="special">;</span> 89 90<span class="keyword">template</span> <span class="special"><</span> <span class="identifier">static_gcd_type</span> <span class="identifier">Value1</span><span class="special">,</span> <span class="identifier">static_gcd_type</span> <span class="identifier">Value2</span> <span class="special">></span> 91 <span class="keyword">struct</span> <span class="identifier">static_gcd</span><span class="special">;</span> 92<span class="keyword">template</span> <span class="special"><</span> <span class="identifier">static_gcd_type</span> <span class="identifier">Value1</span><span class="special">,</span> <span class="identifier">static_gcd_type</span> <span class="identifier">Value2</span> <span class="special">></span> 93 <span class="keyword">struct</span> <span class="identifier">static_lcm</span><span class="special">;</span> 94 95<span class="special">}</span> 96<span class="special">}</span> 97</pre> 98</div> 99<div class="section"> 100<div class="titlepage"><div><div><h3 class="title"> 101<a name="boost_integer.gcd_lcm.gcd_function_object"></a><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.gcd_function_object" title="GCD Function Object">GCD Function 102 Object</a> 103</h3></div></div></div> 104<p> 105 <span class="bold"><strong>Header: </strong></span> <a href="../../../../../boost/integer/common_factor_rt.hpp" target="_top"><boost/integer/common_factor_rt.hpp></a> 106 </p> 107<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span> <span class="special">></span> 108<span class="keyword">class</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">gcd_evaluator</span> 109<span class="special">{</span> 110<span class="keyword">public</span><span class="special">:</span> 111 <span class="comment">// Types</span> 112 <span class="keyword">typedef</span> <span class="identifier">IntegerType</span> <span class="identifier">result_type</span><span class="special">;</span> 113 <span class="keyword">typedef</span> <span class="identifier">IntegerType</span> <span class="identifier">first_argument_type</span><span class="special">;</span> 114 <span class="keyword">typedef</span> <span class="identifier">IntegerType</span> <span class="identifier">second_argument_type</span><span class="special">;</span> 115 116 <span class="comment">// Function object interface</span> 117 <span class="keyword">constexpr</span> <span class="identifier">result_type</span> <span class="keyword">operator</span> <span class="special">()(</span> 118 <span class="identifier">first_argument_type</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">a</span><span class="special">,</span> 119 <span class="identifier">second_argument_type</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">b</span> <span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> 120<span class="special">};</span> 121</pre> 122<p> 123 The boost::integer::gcd_evaluator class template defines a function object 124 class to return the greatest common divisor of two integers. The template 125 is parameterized by a single type, called IntegerType here. This type should 126 be a numeric type that represents integers. The result of the function object 127 is always nonnegative, even if either of the operator arguments is negative. 128 </p> 129<p> 130 This function object class template is used in the corresponding version 131 of the GCD function template. If a numeric type wants to customize evaluations 132 of its greatest common divisors, then the type should specialize on the gcd_evaluator 133 class template. 134 </p> 135<p> 136 Note that these function objects are <code class="computeroutput"><span class="keyword">constexpr</span></code> 137 in C++14 and later only. They are also declared <code class="computeroutput"><span class="keyword">noexcept</span></code> 138 when appropriate. 139 </p> 140</div> 141<div class="section"> 142<div class="titlepage"><div><div><h3 class="title"> 143<a name="boost_integer.gcd_lcm.lcm_function_object"></a><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.lcm_function_object" title="LCM Function Object">LCM Function 144 Object</a> 145</h3></div></div></div> 146<p> 147 <span class="bold"><strong>Header: </strong></span> <a href="../../../../../boost/integer/common_factor_rt.hpp" target="_top"><boost/integer/common_factor_rt.hpp></a> 148 </p> 149<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span> <span class="special">></span> 150<span class="keyword">class</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">lcm_evaluator</span> 151<span class="special">{</span> 152<span class="keyword">public</span><span class="special">:</span> 153 <span class="comment">// Types</span> 154 <span class="keyword">typedef</span> <span class="identifier">IntegerType</span> <span class="identifier">result_type</span><span class="special">;</span> 155 <span class="keyword">typedef</span> <span class="identifier">IntegerType</span> <span class="identifier">first_argument_type</span><span class="special">;</span> 156 <span class="keyword">typedef</span> <span class="identifier">IntegerType</span> <span class="identifier">second_argument_type</span><span class="special">;</span> 157 158 <span class="comment">// Function object interface</span> 159 <span class="keyword">constexpr</span> <span class="identifier">result_type</span> <span class="keyword">operator</span> <span class="special">()(</span> 160 <span class="identifier">first_argument_type</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">a</span><span class="special">,</span> 161 <span class="identifier">second_argument_type</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">b</span> <span class="special">)</span> <span class="keyword">const</span><span class="special">;</span> 162<span class="special">};</span> 163</pre> 164<p> 165 The boost::integer::lcm_evaluator class template defines a function object 166 class to return the least common multiple of two integers. The template is 167 parameterized by a single type, called IntegerType here. This type should 168 be a numeric type that represents integers. The result of the function object 169 is always nonnegative, even if either of the operator arguments is negative. 170 If the least common multiple is beyond the range of the integer type, the 171 results are undefined. 172 </p> 173<p> 174 This function object class template is used in the corresponding version 175 of the LCM function template. If a numeric type wants to customize evaluations 176 of its least common multiples, then the type should specialize on the lcm_evaluator 177 class template. 178 </p> 179<p> 180 Note that these function objects are constexpr in C++14 and later only. They 181 are also declared <code class="computeroutput"><span class="keyword">noexcept</span></code> when 182 appropriate. 183 </p> 184</div> 185<div class="section"> 186<div class="titlepage"><div><div><h3 class="title"> 187<a name="boost_integer.gcd_lcm.run_time"></a><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.run_time" title="Run-time GCD & LCM Determination">Run-time GCD & LCM 188 Determination</a> 189</h3></div></div></div> 190<p> 191 <span class="bold"><strong>Header: </strong></span> <a href="../../../../../boost/integer/common_factor_rt.hpp" target="_top"><boost/integer/common_factor_rt.hpp></a> 192 </p> 193<pre class="programlisting"><span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span> <span class="special">></span> 194<span class="keyword">constexpr</span> <span class="identifier">IntegerType</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">gcd</span><span class="special">(</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">b</span> <span class="special">);</span> 195 196<span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span> <span class="special">></span> 197<span class="keyword">constexpr</span> <span class="identifier">IntegerType</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">lcm</span><span class="special">(</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">b</span> <span class="special">);</span> 198 199<span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span><span class="special">,</span> <span class="keyword">typename</span><span class="special">...</span> <span class="identifier">Args</span> <span class="special">></span> 200 <span class="keyword">constexpr</span> <span class="identifier">IntegerType</span> <span class="identifier">gcd</span><span class="special">(</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">b</span><span class="special">,</span> <span class="identifier">Args</span> <span class="keyword">const</span><span class="special">&...</span> <span class="special">);</span> 201 202<span class="keyword">template</span> <span class="special"><</span> <span class="keyword">typename</span> <span class="identifier">IntegerType</span><span class="special">,</span> <span class="keyword">typename</span><span class="special">...</span> <span class="identifier">Args</span> <span class="special">></span> 203 <span class="keyword">constexpr</span> <span class="identifier">IntegerType</span> <span class="identifier">lcm</span><span class="special">(</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">a</span><span class="special">,</span> <span class="identifier">IntegerType</span> <span class="keyword">const</span> <span class="special">&</span><span class="identifier">b</span><span class="special">,</span> <span class="identifier">Args</span> <span class="keyword">const</span><span class="special">&...</span> <span class="special">);</span> 204 205<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">I</span><span class="special">></span> 206<span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="identifier">I</span><span class="special">>::</span><span class="identifier">value_type</span><span class="special">,</span> <span class="identifier">I</span><span class="special">></span> 207 <span class="identifier">gcd_range</span><span class="special">(</span><span class="identifier">I</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">I</span> <span class="identifier">last</span><span class="special">);</span> 208 209<span class="keyword">template</span> <span class="special"><</span><span class="keyword">typename</span> <span class="identifier">I</span><span class="special">></span> 210<span class="identifier">std</span><span class="special">::</span><span class="identifier">pair</span><span class="special"><</span><span class="keyword">typename</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">iterator_traits</span><span class="special"><</span><span class="identifier">I</span><span class="special">>::</span><span class="identifier">value_type</span><span class="special">,</span> <span class="identifier">I</span><span class="special">></span> 211 <span class="identifier">lcm_range</span><span class="special">(</span><span class="identifier">I</span> <span class="identifier">first</span><span class="special">,</span> <span class="identifier">I</span> <span class="identifier">last</span><span class="special">);</span> 212</pre> 213<p> 214 The boost::integer::gcd function template returns the greatest common (nonnegative) 215 divisor of the two integers passed to it. <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">gcd_range</span></code> 216 is the iteration of the above gcd algorithm over a range, returning the greatest 217 common divisor of all the elements. The algorithm terminates when the gcd 218 reaches unity or the end of the range. Thus it also returns the iterator 219 after the last element inspected because this may not be equal to the end 220 of the range. The variadic version of <code class="computeroutput"><span class="identifier">gcd</span></code> 221 behaves similarly but does not indicate which input value caused the gcd 222 to reach unity. 223 </p> 224<p> 225 The boost::integer::lcm function template returns the least common (nonnegative) 226 multiple of the two integers passed to it. As with gcd, there are range and 227 variadic versions of the function for more than 2 arguments. 228 </p> 229<p> 230 Note that these functions are constexpr in C++14 and later only. They are 231 also declared <code class="computeroutput"><span class="keyword">noexcept</span></code> when 232 appropriate. 233 </p> 234</div> 235<div class="section"> 236<div class="titlepage"><div><div><h3 class="title"> 237<a name="boost_integer.gcd_lcm.compile_time"></a><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.compile_time" title="Compile time GCD and LCM determination">Compile time GCD 238 and LCM determination</a> 239</h3></div></div></div> 240<div class="note"><table border="0" summary="Note"> 241<tr> 242<td rowspan="2" align="center" valign="top" width="25"><img alt="[Note]" src="../../../../../doc/src/images/note.png"></td> 243<th align="left">Note</th> 244</tr> 245<tr><td align="left" valign="top"><p> 246 These functions are deprecated in favor of constexpr <code class="computeroutput"><span class="identifier">gcd</span></code> 247 and <code class="computeroutput"><span class="identifier">lcm</span></code> on C++14 capable 248 compilers. 249 </p></td></tr> 250</table></div> 251<p> 252 <span class="bold"><strong>Header: </strong></span> <a href="../../../../../boost/integer/common_factor_ct.hpp" target="_top"><boost/integer/common_factor_ct.hpp></a> 253 </p> 254<pre class="programlisting"><span class="keyword">typedef</span> <span class="emphasis"><em>unspecified</em></span> <span class="identifier">static_gcd_type</span><span class="special">;</span> 255 256<span class="keyword">template</span> <span class="special"><</span> <span class="identifier">static_gcd_type</span> <span class="identifier">Value1</span><span class="special">,</span> <span class="identifier">static_gcd_type</span> <span class="identifier">Value2</span> <span class="special">></span> 257<span class="keyword">struct</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">static_gcd</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">mpl</span><span class="special">::</span><span class="identifier">integral_c</span><span class="special"><</span><span class="identifier">static_gcd_type</span><span class="special">,</span> <span class="identifier">implementation_defined</span><span class="special">></span> 258<span class="special">{</span> 259<span class="special">};</span> 260 261<span class="keyword">template</span> <span class="special"><</span> <span class="identifier">static_gcd_type</span> <span class="identifier">Value1</span><span class="special">,</span> <span class="identifier">static_gcd_type</span> <span class="identifier">Value2</span> <span class="special">></span> 262<span class="keyword">struct</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">static_lcm</span> <span class="special">:</span> <span class="keyword">public</span> <span class="identifier">mpl</span><span class="special">::</span><span class="identifier">integral_c</span><span class="special"><</span><span class="identifier">static_gcd_type</span><span class="special">,</span> <span class="identifier">implementation_defined</span><span class="special">></span> 263<span class="special">{</span> 264<span class="special">};</span> 265</pre> 266<p> 267 The type <code class="computeroutput"><span class="identifier">static_gcd_type</span></code> 268 is the widest unsigned-integer-type that is supported for use in integral-constant-expressions 269 by the compiler. Usually this the same type as <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">uintmax_t</span></code>, 270 but may fall back to being <code class="computeroutput"><span class="keyword">unsigned</span> 271 <span class="keyword">long</span></code> for some older compilers. 272 </p> 273<p> 274 The boost::integer::static_gcd and boost::integer::static_lcm class templates 275 take two value-based template parameters of the <span class="emphasis"><em>static_gcd_type</em></span> 276 type and inherit from the type <code class="computeroutput"><span class="identifier">boost</span><span class="special">::</span><span class="identifier">mpl</span><span class="special">::</span><span class="identifier">integral_c</span></code>. Inherited from the base class, 277 they have a member <span class="emphasis"><em>value</em></span> that is the greatest common 278 factor or least common multiple, respectively, of the template arguments. 279 A compile-time error will occur if the least common multiple is beyond the 280 range of <code class="computeroutput"><span class="identifier">static_gcd_type</span></code>. 281 </p> 282<h4> 283<a name="boost_integer.gcd_lcm.compile_time.h0"></a> 284 <span class="phrase"><a name="boost_integer.gcd_lcm.compile_time.example"></a></span><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.compile_time.example">Example</a> 285 </h4> 286<pre class="programlisting"><span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">boost</span><span class="special">/</span><span class="identifier">integer</span><span class="special">/</span><span class="identifier">common_factor</span><span class="special">.</span><span class="identifier">hpp</span><span class="special">></span> 287<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">algorithm</span><span class="special">></span> 288<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">iterator</span><span class="special">></span> 289<span class="preprocessor">#include</span> <span class="special"><</span><span class="identifier">iostream</span><span class="special">></span> 290 291<span class="keyword">int</span> <span class="identifier">main</span><span class="special">()</span> 292<span class="special">{</span> 293 <span class="keyword">using</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">cout</span><span class="special">;</span> 294 <span class="keyword">using</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">endl</span><span class="special">;</span> 295 296 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"The GCD and LCM of 6 and 15 are "</span> 297 <span class="special"><<</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">gcd</span><span class="special">(</span><span class="number">6</span><span class="special">,</span> <span class="number">15</span><span class="special">)</span> <span class="special"><<</span> <span class="string">" and "</span> 298 <span class="special"><<</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">lcm</span><span class="special">(</span><span class="number">6</span><span class="special">,</span> <span class="number">15</span><span class="special">)</span> <span class="special"><<</span> <span class="string">", respectively."</span> 299 <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 300 301 <span class="identifier">cout</span> <span class="special"><<</span> <span class="string">"The GCD and LCM of 8 and 9 are "</span> 302 <span class="special"><<</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">static_gcd</span><span class="special"><</span><span class="number">8</span><span class="special">,</span> <span class="number">9</span><span class="special">>::</span><span class="identifier">value</span> 303 <span class="special"><<</span> <span class="string">" and "</span> 304 <span class="special"><<</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">static_lcm</span><span class="special"><</span><span class="number">8</span><span class="special">,</span> <span class="number">9</span><span class="special">>::</span><span class="identifier">value</span> 305 <span class="special"><<</span> <span class="string">", respectively."</span> <span class="special"><<</span> <span class="identifier">endl</span><span class="special">;</span> 306 307 <span class="keyword">int</span> <span class="identifier">a</span><span class="special">[]</span> <span class="special">=</span> <span class="special">{</span> <span class="number">4</span><span class="special">,</span> <span class="number">5</span><span class="special">,</span> <span class="number">6</span> <span class="special">},</span> <span class="identifier">b</span><span class="special">[]</span> <span class="special">=</span> <span class="special">{</span> <span class="number">7</span><span class="special">,</span> <span class="number">8</span><span class="special">,</span> <span class="number">9</span> <span class="special">},</span> <span class="identifier">c</span><span class="special">[</span><span class="number">3</span><span class="special">];</span> 308 <span class="identifier">std</span><span class="special">::</span><span class="identifier">transform</span><span class="special">(</span> <span class="identifier">a</span><span class="special">,</span> <span class="identifier">a</span> <span class="special">+</span> <span class="number">3</span><span class="special">,</span> <span class="identifier">b</span><span class="special">,</span> <span class="identifier">c</span><span class="special">,</span> <span class="identifier">boost</span><span class="special">::</span><span class="identifier">integer</span><span class="special">::</span><span class="identifier">gcd_evaluator</span><span class="special"><</span><span class="keyword">int</span><span class="special">>()</span> <span class="special">);</span> 309 <span class="identifier">std</span><span class="special">::</span><span class="identifier">copy</span><span class="special">(</span> <span class="identifier">c</span><span class="special">,</span> <span class="identifier">c</span> <span class="special">+</span> <span class="number">3</span><span class="special">,</span> <span class="identifier">std</span><span class="special">::</span><span class="identifier">ostream_iterator</span><span class="special"><</span><span class="keyword">int</span><span class="special">>(</span><span class="identifier">cout</span><span class="special">,</span> <span class="string">" "</span><span class="special">)</span> <span class="special">);</span> 310<span class="special">}</span> 311</pre> 312</div> 313<div class="section"> 314<div class="titlepage"><div><div><h3 class="title"> 315<a name="boost_integer.gcd_lcm.gcd_header"></a><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.gcd_header" title="Header <boost/integer/common_factor.hpp>">Header <boost/integer/common_factor.hpp></a> 316</h3></div></div></div> 317<p> 318 This header simply includes the headers <a href="../../../../../boost/integer/common_factor_ct.hpp" target="_top"><boost/integer/common_factor_ct.hpp></a> 319 and <a href="../../../../../boost/integer/common_factor_rt.hpp" target="_top"><boost/integer/common_factor_rt.hpp></a>. 320 </p> 321<p> 322 Note this is a legacy header: it used to contain the actual implementation, 323 but the compile-time and run-time facilities were moved to separate headers 324 (since they were independent of each other). 325 </p> 326</div> 327<div class="section"> 328<div class="titlepage"><div><div><h3 class="title"> 329<a name="boost_integer.gcd_lcm.demo"></a><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.demo" title="Demonstration Program">Demonstration Program</a> 330</h3></div></div></div> 331<p> 332 The program <a href="../../../../../libs/integer/test/common_factor_test.cpp" target="_top">common_factor_test.cpp</a> 333 is a demonstration of the results from instantiating various examples of 334 the run-time GCD and LCM function templates and the compile-time GCD and 335 LCM class templates. (The run-time GCD and LCM class templates are tested 336 indirectly through the run-time function templates.) 337 </p> 338</div> 339<div class="section"> 340<div class="titlepage"><div><div><h3 class="title"> 341<a name="boost_integer.gcd_lcm.rationale"></a><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.rationale" title="Rationale">Rationale</a> 342</h3></div></div></div> 343<p> 344 The greatest common divisor and least common multiple functions are greatly 345 used in some numeric contexts, including some of the other Boost libraries. 346 Centralizing these functions to one header improves code factoring and eases 347 maintenance. 348 </p> 349</div> 350<div class="section"> 351<div class="titlepage"><div><div><h3 class="title"> 352<a name="boost_integer.gcd_lcm.gcd_history"></a><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.gcd_history" title="History">History</a> 353</h3></div></div></div> 354<div class="itemizedlist"><ul class="itemizedlist" style="list-style-type: disc; "> 355<li class="listitem"> 356 24th April 2017 Moved to Jeremy Murphy's improved algorithms, added constexpr 357 and noexcept support, added compiler intrinsic support, added variadic 358 and range based versions of the algorithms. 359 </li> 360<li class="listitem"> 361 13 May 2013 Moved into main Boost.Math Quickbook documentation. 362 </li> 363<li class="listitem"> 364 17 Dec 2005: Converted documentation to Quickbook Format. 365 </li> 366<li class="listitem"> 367 2 Jul 2002: Compile-time and run-time items separated to new headers. 368 </li> 369<li class="listitem"> 370 7 Nov 2001: Initial version 371 </li> 372</ul></div> 373</div> 374<div class="section"> 375<div class="titlepage"><div><div><h3 class="title"> 376<a name="boost_integer.gcd_lcm.gcd_credits"></a><a class="link" href="gcd_lcm.html#boost_integer.gcd_lcm.gcd_credits" title="Credits">Credits</a> 377</h3></div></div></div> 378<p> 379 The author of the Boost compilation of GCD and LCM computations is Daryle 380 Walker. The code was prompted by existing code hiding in the implementations 381 of Paul Moore's rational library and Steve Cleary's pool library. The code 382 had updates by Helmut Zeisel. 383 </p> 384</div> 385</div> 386<table xmlns:rev="http://www.cs.rpi.edu/~gregod/boost/tools/doc/revision" width="100%"><tr> 387<td align="left"></td> 388<td align="right"><div class="copyright-footer">Copyright © 2001-2009 Beman 389 Dawes, Daryle Walker, Gennaro Prota, John Maddock<p> 390 Distributed under the Boost Software License, Version 1.0. (See accompanying 391 file LICENSE_1_0.txt or copy at <a href="http://www.boost.org/LICENSE_1_0.txt" target="_top">http://www.boost.org/LICENSE_1_0.txt</a>) 392 </p> 393</div></td> 394</tr></table> 395<hr> 396<div class="spirit-nav"> 397<a accesskey="p" href="integer.html"><img src="../../../../../doc/src/images/prev.png" alt="Prev"></a><a accesskey="u" href="../index.html"><img src="../../../../../doc/src/images/up.png" alt="Up"></a><a accesskey="h" href="../index.html"><img src="../../../../../doc/src/images/home.png" alt="Home"></a><a accesskey="n" href="extended_euclidean.html"><img src="../../../../../doc/src/images/next.png" alt="Next"></a> 398</div> 399</body> 400</html> 401
