BigNumber : 큰 수의 덧셈과 곱셈

BigNumber.swift

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
}