Embedded Template Library 1.0
Loading...
Searching...
No Matches
gcd.h
Go to the documentation of this file.
1
2
3/******************************************************************************
4The MIT License(MIT)
5
6Embedded Template Library.
7https://github.com/ETLCPP/etl
8https://www.etlcpp.com
9
10Copyright(c) 2024 John Wellbelove
11
12Permission is hereby granted, free of charge, to any person obtaining a copy
13of this software and associated documentation files(the "Software"), to deal
14in the Software without restriction, including without limitation the rights
15to use, copy, modify, merge, publish, distribute, sublicense, and / or sell
16copies of the Software, and to permit persons to whom the Software is
17furnished to do so, subject to the following conditions :
18
19The above copyright notice and this permission notice shall be included in all
20copies or substantial portions of the Software.
21
22THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
23IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
24FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.IN NO EVENT SHALL THE
25AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
26LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
27OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
28SOFTWARE.
29******************************************************************************/
30
31#ifndef ETL_GDC_INCLUDED
32#define ETL_GDC_INCLUDED
33
34#include "type_traits.h"
35#include "absolute.h"
36#include "static_assert.h"
37
38namespace etl
39{
40 //***************************************************************************
41 // Greatest Common Divisor.
42 // For unsigned types.
43 //***************************************************************************
44 template <typename T>
45 ETL_NODISCARD
46 ETL_CONSTEXPR14
48 gcd(T a, T b) ETL_NOEXCEPT
49 {
50 ETL_STATIC_ASSERT(etl::is_integral<T>::value, "Integral type required");
51
52 if ((a == 0 || b == 0))
53 {
54 return (a + b);
55 }
56
57 while (b != 0)
58 {
59 T t = b;
60 b = a % b;
61 a = t;
62 }
63
64 return a;
65 }
66
67 //***************************************************************************
68 // Greatest Common Divisor.
69 // For signed types.
70 //***************************************************************************
71 template <typename T>
72 ETL_NODISCARD
73 ETL_CONSTEXPR14
75 gcd(T a, T b) ETL_NOEXCEPT
76 {
77 ETL_STATIC_ASSERT(etl::is_integral<T>::value, "Integral type required");
78
79 typedef typename etl::make_unsigned<T>::type utype;
80
81 utype ua = etl::absolute_unsigned(a);
82 utype ub = etl::absolute_unsigned(b);
83
84 return static_cast<T>(gcd(ua, ub));
85 }
86
87#if ETL_USING_CPP11
88 #if ETL_HAS_INITIALIZER_LIST
89 //***************************************************************************
90 // Greatest Common Divisor.
91 // Non-recursive, using an initializer_list.
92 // Top level variadic function.
93 //***************************************************************************
94 template<typename T, typename... TRest>
95 ETL_NODISCARD
96 ETL_CONSTEXPR14
97 T gcd(T first, TRest... rest) ETL_NOEXCEPT
98 {
99 T result = first;
100
101 for (T value : {rest...})
102 {
103 result = gcd(result, value);
104
105 if (result == 1)
106 {
107 // Early termination: if the GCD is one, it will remain one
108 // no matter what other numbers are processed.
109 return 1;
110 }
111 }
112
113 return result;
114 }
115 #else
116 //***************************************************************************
117 // Greatest Common Divisor.
118 // Recursive.
119 // Top level variadic function.
120 //***************************************************************************
121 template<typename T, typename... TRest>
122 ETL_NODISCARD
123 ETL_CONSTEXPR14
124 T gcd(T a, T b, TRest... rest) ETL_NOEXCEPT
125 {
126 T gcd_ab = gcd(a, b);
127
128 if (gcd_ab == 1)
129 {
130 // Early termination: if the GCD is one, it will remain one
131 // no matter what other numbers are processed.
132 return 1;
133 }
134 else
135 {
136 return gcd(gcd_ab, rest...);
137 }
138 }
139 #endif
140#endif
141}
142
143#endif
144
is_integral
Definition type_traits_generator.h:996
make_unsigned
Definition type_traits_generator.h:1176
bitset_ext
Definition absolute.h:38
pair holds two objects of arbitrary type
Definition utility.h:164