8000 Merge pull request #808 from kayoslab/GCD-improvements · jerrytdev/swift-algorithm-club@545a60c · GitHub
[go: up one dir, main page]
Skip to content 8000

Commit 545a60c

Browse files
richard-ashrichard-ash
authored
Merge pull request kodecocodes#808 from kayoslab/GCD-improvements
Adds binary recursive stein algorithm to the GCD class
2 parents 24fc308 + 15f2779 commit 545a60c

File tree

6 files changed

+289
-119
lines changed

6 files changed

+289
-119
lines changed

‎GCD/GCD.playground/Contents.swift

Lines changed: 16 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -1,39 +1,21 @@
1-
//: Playground - noun: a place where people can play
2-
3-
// Recursive version
4-
func gcd(_ a: Int, _ b: Int) -> Int {
5-
let r = a % b
6-
if r != 0 {
7-
return gcd(b, r)
8-
} else {
9-
return b
10-
}
11-
}
12-
13-
/*
14-
// Iterative version
15-
func gcd(m: Int, _ n: Int) -> Int {
16-
var a = 0
17-
var b = max(m, n)
18-
var r = min(m, n)
19-
20-
while r != 0 {
21-
a = b
22-
b = r
23-
r = a % b
24-
}
25-
return b
26-
}
27-
*/
28-
29-
func lcm(_ m: Int, _ n: Int) -> Int {
30-
return m / gcd(m, n) * n // we divide before multiplying to avoid integer overflow
31-
}
32-
331
gcd(52, 39) // 13
342
gcd(228, 36) // 12
353
gcd(51357, 3819) // 57
364
gcd(841, 299) // 1
375

38-
lcm(2, 3) // 6
39-
lcm(10, 8) // 40
6+
gcd(52, 39, using: gcdRecursiveEuklid) // 13
7+
gcd(228, 36, using: gcdRecursiveEuklid) // 12
8+
gcd(51357, 3819, using: gcdRecursiveEuklid) // 57
9+
gcd(841, 299, using: gcdRecursiveEuklid) // 1
10+
11+
gcd(52, 39, using: gcdBinaryRecursiveStein) // 13
12+
gcd(228, 36, using: gcdBinaryRecursiveStein) // 12
13+
gcd(51357, 3819, using: gcdBinaryRecursiveStein) // 57
14+
gcd(841, 299, using: gcdBinaryRecursiveStein) // 1
15+
16+
do {
17+
try lcm(2, 3) // 6
18+
try lcm(10, 8, using: gcdRecursiveEuklid) // 40
19+
} catch {
20+
dump(error)
21+
}

‎GCD/GCD.playground/Sources/GCD.swift

Lines changed: 143 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,143 @@
1+
/*
2+
Finds the largest positive integer that divides both
3+
m and n without a remainder.
4+
5+
- Parameter m: First natural number
6+
- Parameter n: Second natural number
7+
- Parameter using: The used algorithm to calculate the gcd.
8+
If nothing provided, the Iterative Euclidean
9+
algorithm is used.
10+
- Returns: The natural gcd of m and n.
11+
*/
12+
public func gcd(_ m: Int, _ n: Int, using gcdAlgorithm: (Int, Int) -> (Int) = gcdIterativeEuklid) -> Int {
13+
return gcdAlgorithm(m, n)
14+
}
15+
16+
/*
17+
Iterative approach based on the Euclidean algorithm.
18+
The Euclidean algorithm is based on the principle that the greatest
19+
common divisor of two numbers does not change if the larger number
20+
is replaced by its difference with the smaller number.
21+
- Parameter m: First natural number
22+
- Parameter n: Second natural number
23+
- Returns: The natural gcd of m and n.
24+
*/
25+
public func gcdIterativeEuklid(_ m: Int, _ n: Int) -> Int {
26+
var a: Int = 0
27+
var b: Int = max(m, n)
28+
var r: Int = min(m, n)
29+
30+
while r != 0 {
31+
a = b
32+
b = r
33+
r = a % b
34+
}
35+
return b
36+
}
37+
38+
/*
39+
Recursive approach based on the Euclidean algorithm.
40+
41+
- Parameter m: First natural number
42+
- Parameter n: Second natural number
43+
- Returns: The natural gcd of m and n.
44+
- Note: The recursive version makes only tail recursive calls.
45+
Most compilers for imperative languages do not optimize these.
46+
The swift compiler as well as the obj-c compiler is able to do
47+
optimizations for tail recursive calls, even though it still ends
48+
up to be the same in terms of complexity. That said, tail call
49+
elimination is not mutually exclusive to recursion.
50+
*/
51+
public func gcdRecursiveEuklid(_ m: Int, _ n: Int) -> Int {
52+
let r: Int = m % n
53+
if r != 0 {
54+
return gcdRecursiveEuklid(n, r)
55+
} else {
56+
return n
57+
}
58+
}
59+
60+
/*
61+
The binary GCD algorithm, also known as Stein's algorithm,
62+
is an algorithm that computes the greatest common divisor of two
63+
nonnegative integers. Stein's algorithm uses simpler arithmetic
64+
operations than the conventional Euclidean algorithm; it replaces
65+
division with arithmetic shifts, comparisons, and subtraction.
66+
67+
- Parameter m: First natural number
68+
- Parameter n: Second natural number
69+
- Returns: The natural gcd of m and n
70+
- Complexity: worst case O(n^2), where n is the number of bits
71+
in the larger of the two numbers. Although each step reduces
72+
at least one of the operands by at least a factor of 2,
73+
the subtract and shift operations take linear time for very
74+
large integers
75+
*/
76+
public func gcdBinaryRecursiveStein(_ m: Int, _ n: Int) -> Int {
77+
if let easySolution = findEasySolution(m, n) { return easySolution }
78+
79+
if (m & 1) == 0 {
80+
// m is even
81+
if (n & 1) == 1 {
82+
// and n is odd
83+
return gcdBinaryRecursiveStein(m >> 1, n)
84+
} else {
85+
// both m and n are even
86+
return gcdBinaryRecursiveStein(m >> 1, n >> 1) << 1
87+
}
88+
} else if (n & 1) == 0 {
89+
// m is odd, n is even
90+
return gcdBinaryRecursiveStein(m, n >> 1)
91+
} else if (m > n) {
92+
// reduce larger argument
93+
return gcdBinaryRecursiveStein((m - n) >> 1, n)
94+
} else {
95+
// reduce larger argument
96+
return gcdBinaryRecursiveStein((n - m) >> 1, m)
97+
}
98+
}
99+
100+
/*
101+
Finds an easy solution for the gcd.
102+
- Parameter m: First natural number
103+
- Parameter n: Second natural number
104+
- Returns: A natural gcd of m and n if possible.
105+
- Note: It might be relevant for different usecases to
106+
try finding an easy solution for the GCD calculation
107+
before even starting more difficult operations.
108+
*/
109+
func findEasySolution(_ m: Int, _ n: Int) -> Int? {
110+
if m == n {
111+
return m
112+
}
113+
if m == 0 {
114+
return n
115+
}
116+
if n == 0 {
117+
return m
118+
}
119+
return nil
120+
}
121+
122+
123+
public enum LCMError: Error {
124+
case divisionByZero
125+
}
126+
127+
/*
128+
Calculates the lcm for two given numbers using a specified gcd algorithm.
129+
130+
- Parameter m: First natural number.
131+
- Parameter n: Second natural number.
132+
- Parameter using: The used gcd algorithm to calculate the lcm.
133+
If nothing provided, the Iterative Euclidean
134+
algorithm is used.
135+
- Throws: Can throw a `divisionByZero` error if one of the given
136+
attributes turns out to be zero or less.
137+
- Returns: The least common multiplier of the two attributes as
138+
an unsigned integer
139+
*/
140+
public func lcm(_ m: Int, _ n: Int, using gcdAlgorithm: (Int, Int) -> (Int) = gcdIterativeEuklid) throws -> Int {
141+
guard m & n != 0 else { throw LCMError.divisionByZero }
142+
return m / gcdAlgorithm(m, n) * n
143+
}

‎GCD/GCD.playground/playground.xcworkspace/xcshareddata/IDEWorkspaceChecks.plist

Lines changed: 8 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,8 @@
1+
<?xml version="1.0" encoding="UTF-8"?>
2+
<!DOCTYPE plist PUBLIC "-//Apple//DTD PLIST 1.0//EN" "http://www.apple.com/DTDs/PropertyList-1.0.dtd">
3+
<plist version="1.0">
4+
<dict>
5+
<key>IDEDidComputeMac32BitWarning</key>
6+
<true/>
7+
</dict>
8+
</plist>

‎GCD/GCD.playground/timeline.xctimeline

Lines changed: 0 additions & 6 deletions
This file was deleted.

‎GCD/GCD.swift

Lines changed: 0 additions & 34 deletions
This file was deleted.

0 commit comments

Comments
 (0)
0