1//! @file divisor.cpp
2//! @author ryftchen
3//! @brief The definitions (divisor) in the numeric module.
4//! @version 0.1.0
5//! @copyright Copyright (c) 2022-2025 ryftchen. All rights reserved.
6
7#include "divisor.hpp"
8
9#include <cmath>
10
11namespace numeric::divisor
12{
13//! @brief Function version number.
14//! @return version number (major.minor.patch)
15const char* version() noexcept
16{
17 static const char* const ver = "0.1.0";
18 return ver;
19}
20
21std::set<std::int32_t> Divisor::euclidean(const std::int32_t a, const std::int32_t b)
22{
23 std::int32_t x = std::abs(x: a);
24 std::int32_t y = std::abs(x: b);
25 while (y)
26 {
27 const std::int32_t temp = x % y;
28 x = y;
29 y = temp;
30 }
31 return getAllDivisors(gcd: x);
32}
33
34std::set<std::int32_t> Divisor::stein(const std::int32_t a, const std::int32_t b)
35{
36 std::int32_t x = std::abs(x: a);
37 std::int32_t y = std::abs(x: b);
38 std::int32_t gcd = 0;
39 std::int32_t c = 0;
40 while (isEven(n: x) && isEven(n: y))
41 {
42 x >>= 1;
43 y >>= 1;
44 ++c;
45 }
46
47 if (isEven(n: x))
48 {
49 x >>= 1;
50 gcd = steinRecursive(a: x, b: y) << c;
51 }
52 else
53 {
54 gcd = steinRecursive(a: y, b: x) << c;
55 }
56 return getAllDivisors(gcd);
57}
58
59bool Divisor::isEven(const std::int32_t n)
60{
61 return (n & 0b1) == 0;
62}
63
64std::int32_t Divisor::steinRecursive(std::int32_t a, std::int32_t b)
65{
66 if (a == 0)
67 {
68 return b;
69 }
70 if (b == 0)
71 {
72 return a;
73 }
74
75 while (isEven(n: a))
76 {
77 a >>= 1;
78 }
79 if (a < b)
80 {
81 b = (b - a) >> 1;
82 return steinRecursive(a: b, b: a);
83 }
84 a = (a - b) >> 1;
85 return steinRecursive(a, b);
86}
87
88std::set<std::int32_t> Divisor::getAllDivisors(const std::int32_t gcd)
89{
90 std::set<std::int32_t> divisors{};
91 for (std::int32_t i = 1; i <= std::sqrt(x: gcd); ++i)
92 {
93 if ((gcd % i) == 0)
94 {
95 divisors.emplace(args&: i);
96 if ((gcd / i) != i)
97 {
98 divisors.emplace(args: gcd / i);
99 }
100 }
101 }
102 return divisors;
103}
104} // namespace numeric::divisor
105