8000 Merge pull request #773 from afonsograca/feature/karatsuba-multiplica… · i-stack/swift-algorithm-club@9bdce27 · GitHub
[go: up one dir, main page]
Skip to content

Commit 9bdce27

Browse files
richard-ashrichard-ash
authored
Merge pull request kodecocodes#773 from afonsograca/feature/karatsuba-multiplication
[Swift 4.2] Update Karatsuba Multiplication
2 parents 7c7f69e + 6536cd7 commit 9bdce27

File tree

10 files changed

+460
-26
lines changed

10 files changed

+460
-26
lines changed

‎.travis.yml

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -48,6 +48,7 @@ script:
4848
- xcodebuild test -project ./Treap/Treap/Treap.xcodeproj -scheme Tests | xcpretty -f `xcpretty-travis-formatter`
4949
- xcodebuild test -project ./Palindromes/Test/Test.xcodeproj -scheme Test | xcpretty -f `xcpretty-travis-formatter`
5050
- xcodebuild test -project ./Ternary\ Search\ Tree/Tests/Tests.xcodeproj -scheme Tests | xcpretty -f `xcpretty-travis-formatter`
51+
- xcodebuild test -project ./Karatsuba\ Multiplication/Tests/Tests.xcodeproj -scheme Tests | xcpretty -f `xcpretty-travis-formatter`
5152

5253
after_success:
5354

‎Karatsuba Multiplication/KaratsubaMultiplication.playground/Contents.swift

Lines changed: 7 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -1,10 +1,7 @@
11
//: Playground - noun: a place where people can play
22

33
import Foundation
4-
// last checked with Xcode 9.0b4
5-
#if swift(>=4.0)
6-
print("Hello, Swift 4")
7-
#endif
4+
85
precedencegroup ExponentiativePrecedence {
96
higherThan: MultiplicationPrecedence
107
lowerThan: BitwiseShiftPrecedence
@@ -18,8 +15,8 @@ func ^^ (radix: Int, power: Int) -> Int {
1815

1916
// Long Multiplication - O(n^2)
2017
func multiply(_ num1: Int, by num2: Int, base: Int = 10) -> Int {
21-
let num1Array = String(num1).characters.reversed().map { Int(String($0))! }
22-
let num2Array = String(num2).characters.reversed().map { Int(String($0))! }
18+
let num1Array = String(num1).reversed().map { Int(String($0))! }
19+
let num2Array = String(num2).reversed().map { Int(String($0))! }
2320

2421
var product = Array(repeating: 0, count: num1Array.count + num2Array.count)
2522

@@ -38,14 +35,14 @@ func multiply(_ num1: Int, by num2: Int, base: Int = 10) -> Int {
3835

3936
// Karatsuba Multiplication - O(n^log2(3))
4037
func karatsuba(_ num1: Int, by num2: Int) -> Int {
41-
let num1Array = String(num1).characters
42-
let num2Array = String(num2).characters
38+
let num1String = String(num1)
39+
let num2String = String(num2)
4340

44-
guard num1Array.count > 1 && num2Array.count > 1 else {
41+
guard num1String.count > 1 && num2String.count > 1 else {
4542
return multiply(num1, by: num2)
4643
}
4744

48-
let n = max(num1Array.count, num2Array.count)
45+
let n = max(num1String.count, num2String.count)
4946
let nBy2 = n / 2
5047

5148
let a = num1 / 10^^nBy2

‎Karatsuba Multiplication/KaratsubaMultiplication.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>

‎Karatsuba Multiplication/KaratsubaMultiplication.swift

Lines changed: 32 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -19,27 +19,48 @@ func ^^ (radix: Int, power: Int) -> Int {
1919
return Int(pow(Double(radix), Double(power)))
2020
}
2121

22+
// Long Multiplication - O(n^2)
23+
func multiply(_ num1: Int, by num2: Int, base: Int = 10) -> Int {
24+
let num1Array = String(num1).reversed().map { Int(String($0))! }
25+
let num2Array = String(num2).reversed().map { Int(String($0))! }
26+
27+
var product = Array(repeating: 0, count: num1Array. B41A count + num2Array.count)
28+
29+
for i in num1Array.indices {
30+
var carry = 0
31+
for j in num2Array.indices {
32+
product[i + j] += carry + num1Array[i] * num2Array[j]
33+
carry = product[i + j] / base
34+
product[i + j] %= base
35+
}
36+
product[i + num2Array.count] += carry
37+
}
38+
39+
return Int(product.reversed().map { String($0) }.reduce("", +))!
40+
}
41+
42+
// Karatsuba Multiplication - O(n^log2(3))
2243
func karatsuba(_ num1: Int, by num2: Int) -> Int {
23-
let num1Array = String(num1).characters
24-
let num2Array = String(num2).characters
25-
26-
guard num1Array.count > 1 && num2Array.count > 1 else {
27-
return num1 * num2
44+
let num1String = String(num1)
45+
let num2String = String(num2)
46+
47+
guard num1String.count > 1 && num2String.count > 1 else {
48+
return multiply(num1, by: num2)
2849
}
29-
30-
let n = max(num1Array.count, num2Array.count)
50+
51+
let n = max(num1String.count, num2String.count)
3152
let nBy2 = n / 2
32-
53+
3354
let a = num1 / 10^^nBy2
3455
let b = num1 % 10^^nBy2
3556
let c = num2 / 10^^nBy2
3657
let d = num2 % 10^^nBy2
37-
58+
3859
let ac = karatsuba(a, by: c)
3960
let bd = karatsuba(b, by: d)
4061
let adPlusbc = karatsuba(a+b, by: c+d) - ac - bd
41-
62+
4263
let product = ac * 10^^(2 * nBy2) + adPlusbc * 10^^nBy2 + bd
43-
64+
4465
return product
4566
}

‎Karatsuba Multiplication/README.markdown

Lines changed: 5 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -72,14 +72,14 @@ Here's the full implementation. Note that the recursive algorithm is most effici
7272
```swift
7373
// Karatsuba Multiplication
7474
func karatsuba(_ num1: Int, by num2: Int) -> Int {
75-
let num1Array = String(num1).characters
76-
let num2Array = String(num2).characters
75+
let num1String = String(num1)
76+
let num2String = String(num2)
7777

78-
guard num1Array.count > 1 && num2Array.count > 1 else {
79-
return num1*num2
78+
guard num1String.count > 1 && num2String.count > 1 else {
79+
return multiply(num1, by: num2)
8080
}
8181

82-
let n = max(num1Array.count, num2Array.count)
82+
let n = max(num1S BDB3 tring.count, num2String.count)
8383
let nBy2 = n / 2
8484

8585
let a = num1 / 10^^nBy2

‎Karatsuba Multiplication/Tests/KaratsubaMultiplicationTests.swift

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,17 @@
1+
//
2+
// KaratsubaMultiplicationTests.swift
3+
// Tests
4+
//
5+
// Created by Afonso Graça on 8/10/18.
6+
//
7+
8+
import XCTest
9+
10+
final class KaratsubaMultiplicationTests: XCTestCase {
11+
12+
func testReadmeExample() {
13+
let subject = karatsuba(1234, by: 5678)
14+
15+
XCTAssertEqual(subject, 7006652)
16+
}
17+
}

0 commit comments

Comments
 (0)
0