BigNumber : 큰 수의 덧셈과 곱셈
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import Foundation | |
// 큰 수 덧셈과 곱셈은 특정 단위의 다항식처럼 처리한다. | |
/*: 큰 수를 다항식처럼 다룰 때, 하나의 항을 표현하는 타입. | |
각 항은 0~9999999999 까지의 값을 가지며, 차수를 나타내는 값을 별도로 가지고 있다. | |
*/ | |
struct Node { | |
static let unitSize = 10000_00000 | |
let level : Int | |
let value : Int | |
init(value: Int, level: Int = 0) { | |
self.value = value | |
self.level = level | |
} | |
func multiply(_ other: Node) -> [Node] { | |
// 두 항의 곱의 결과의 차수는 두 항의 차수의 합과 같다. | |
let level = self.level + other.level | |
var value = self.value * other.value | |
var upFlag = 0 | |
if value >= Node.unitSize { | |
upFlag = value / Node.unitSize | |
value = value % Node.unitSize | |
} | |
if upFlag > 0 { | |
return [Node(value: upFlag, level: level + 1), Node(value: value, level: level)] | |
} | |
return [Node(value: value, level: level)] | |
} | |
} | |
struct BigNumber { | |
var nodes: [Node] | |
init(integer value: Int) { | |
var nodes: [Node] = [] | |
var value = value | |
var level = 0 | |
while value > 0 { | |
let v = value % Node.unitSize | |
nodes.append(Node(value: v, level: level)) | |
level += 1 | |
value = value / Node.unitSize | |
} | |
self.nodes = nodes | |
} | |
init(string str: String) { | |
let nodeLength = Int(log10(Double(Node.unitSize))) | |
var level = 0 | |
var tempNodes:[Node] = [] | |
while true { | |
var startPos = str.count - nodeLength * (level + 1) | |
// 마디의 시작위치가 0보다 작아서는 안된다. | |
let endPos: Int = (startPos < 0) ? str.count % nodeLength : nodeLength | |
startPos = startPos < 0 ? 0 : startPos | |
let startIndex = str.index(str.startIndex, offsetBy: startPos) | |
let endIndex = str.index(startIndex, offsetBy: endPos) | |
// 마디 끊기 | |
let p = str[startIndex..<endIndex] | |
if let n = Int(p) { | |
tempNodes.append(Node(value: n, level: level)) | |
level += 1 | |
} | |
if startPos == 0 { | |
break | |
} | |
} | |
self.nodes = tempNodes | |
} | |
init(nodes: [Node]) { | |
var tempNodes: [Node] = [] | |
let maxLevel = nodes.map{ $0.level }.max() ?? 0 | |
var upFlag = 0 | |
// 각 레벨의 노드에 대해서 계수의 합을 구한다. | |
for level in 0...maxLevel { | |
var value = nodes.filter{ $0.level == level }.map{ $0.value } | |
.reduce(0, +) + upFlag | |
if value >= Node.unitSize { | |
upFlag = value / Node.unitSize | |
value = value % Node.unitSize | |
} else { // 이 부분이 중요하다. 올림이 발생하지 않았다면, 올려진 값은 소진되었으므로 0으로 초기화한다. | |
upFlag = 0 | |
} | |
tempNodes.append(Node(value: value, level: level)) | |
} | |
// 모든 항을 처리한 후 올림이 남았는지 확인 | |
if upFlag > 0 { | |
tempNodes.append(Node(value:upFlag, level: maxLevel + 1)) | |
} | |
self.nodes = tempNodes | |
} | |
static func + (left: BigNumber, right: BigNumber) -> BigNumber { | |
// 덧셈은 두 다항식의 항을 모두 합쳐서 정리해버리면 끝! | |
return BigNumber(nodes: left.nodes + right.nodes) | |
} | |
func multiply(with node: Node) -> [Node] { | |
return self.nodes.flatMap{ $0.multiply(node) } | |
} | |
static func * (left: BigNumber, right: BigNumber) -> BigNumber { | |
let tempNodes = right.nodes.flatMap{ left.multiply(with: $0) } | |
return BigNumber(nodes: tempNodes) | |
} | |
static func * (left: BigNumber, right: Int) -> BigNumber { | |
return left * BigNumber(integer: right) | |
} | |
} | |
extension BigNumber: CustomStringConvertible { | |
var description: String { | |
var xs = nodes.sorted{ $0.level > $1.level } | |
let x = xs.removeFirst().value | |
let heading = x > 0 ? "\(x)" : "" | |
if !xs.isEmpty { | |
let remains: String = xs.map{ | |
let padding = Int(log10(Double(Node.unitSize))) - ( $0.value == 0 ? 0 : Int(log10(Double($0.value))) + 1) | |
return String(repeating:"0", count:padding) + "\($0.value)" | |
}.joined(separator: "") | |
return heading + remains | |
} | |
return heading | |
} | |
} | |
func pow(_ a: BigNumber, _ b: Int) -> BigNumber { | |
if b == 0 { return BigNumber(integer: 1) } | |
let r = pow(a, b / 2) | |
if b % 2 == 0 { | |
return r * r | |
} | |
return r * r * a | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment