Swift – 큰 수의 덧셈과 곱셈 구현하기

프로젝트 오일러의 몇몇 문제는 큰 수의 덧셈이나 곱셈의 계산이 필요한 경우가 있다. 파이썬이나 하스켈과 같이 정수타입이 기본적으로 바이트 크기의 제약이 없는 언어에서는 이는 별다른 문제가 되지 않지만, 그외의 언어에서는 좀 까다로운 문제가 된다.  예를 들어 50자리 숫자 100개의 합을 계산하는 문제 같은 경우에 파이썬에서는 50자 짜리 숫자 문자열을 int 타입으로 캐스팅해서 합해버리면 그만이지만, Swift와 같은 언어로 이렇게 풀 수는 없다. 해당 문제의 풀이에서는 손으로 덧셈을 해 나가는 방식을 코드로 구현해서 풀었는데, 이후로도 큰 수를 계산해야 하는 문제가 자주 나온다.

수가 크면 클수록 한자리씩 계산하여 덧셈이나 곱셈을 구현하는 방식의 알고리듬은 점점 불리해진다. (그리고 손으로 계산하는 식으로 덧셈, 곱셈을 만드는 것은 상당히 귀찮고 코드도 그리 깔끔하게 작성하기도 어렵다.) 따라서 이러한 큰 수를 계산하기 위한 BigNumber 타입을 작성해보도록 하자.

접근

큰 수를 만들기 위한 기본적인 접근 방법은, 10진수 값을 하나의 다항식으로 보는 것이다. 10진수로 표기된 임의의 수는 10이라는 값을 가진 여러 항의 합이며, 각 자리 숫자는 해당 항의 계수가 된다. 예를 들어 234는 (2 * 100 ) + (3 * 10) + (4 * 1) 이고 이는 다시 2  \times 10^{2} + 3 \times 10^{1} + 4 \times 10^{0} 으로 표현된다. 어떤 수를 이렇게 다항식으로 표현할 수 있다면 큰 수의 덧셈과 곱셈은 단일 항에 대한 다항식들의 덧셈과 곱셈이 될 것이다. 즉 같은 항끼리 더한 후 정리하는 방식으로 간단하게 값을 정리할 수 있을 것이다.

항의 표현

10의 값을 항으로 두는 경우에는 자리 수 만큼의 항이 필요하다. 예를 들어 50자리 숫자라면 10이라는 항이 최대 10^49까지 사용되어 항을 50개씩 쓰게 된다. 이 경우 덧셈은 100개의 항에 대해서 같은 차수 항을 더하고 정리하는 작업을 해야 한다. 하지만 항의 단위 크기를 늘린다면 항의 개수 자체가 줄어들기 때문에 계산을 반복해야하는 횟수를 쉽게 줄일 수 있을 것이다.

여기서는 항의 크기, 즉 단위를 10,000 으로 잡겠다. 즉 0~9999 까지의 계수를 가질 수 있는 항의 집합으로 큰 수를 표현하고자 한다. 이 항을 A라 하면 1,234,567,987,654 는 네자리씩 끊어져서 1 \times A^{3} + 2345 \times A^{2} + 6798 \times A^{1} + 7654 \times A^{0}으로 표현될 것이다.  이렇게 각 항을 표현하는 노드 타입을 아래와 같이 정의해보겠다. 노드를 정의하기 위해서는 현재 노드의 차수와 계수값이 필요하다. 그리고 노드의 한계값 또한 정의되어야 한다.

struct Node {
  static let unitSize = 10_000
  let level : Int
  let value : Int
  
  init(value: Int, level: Int = 0) {
    self.value = value
    self.level = level
  }
}

항의 덧셈과 곱셈

다항식의 합과 곱을 계산하는 과정에서는 각 차수의 항의 합과 곱을 계산한 후 그 결과로 생성된 항들을 정리한다. 따라서 각 항은 다른 항과 더하거나 곱하는 계산을 수행할 수 있어야 한다. 이를 구현해보자.

extension Node {
  func add(_ otherNode: Node?) -> [Node?] {
    guard let other = otherNode else { return [ nil, self] }
    // 만약 차수가 다른 노드라면 별도의 계산은 필요하지 않다. 
    guard other.level == self.level else { return [other, self] }
    // 차수가 같은 노드라면 계수를 더한다. 
    // 만약 계수가 항의 크기를 넘어서면 올림이 발생한다. 
    var value = self.value + other.value
    var upFlag = 0
    if value >= Node.unitSize {
      upFlag = value / Node.unitSize
      value = value % Node.unitSize
    }
    return [Node(value: upFlag, level: self.level + 1), Node(value: value, level: self.level)]
  }

  func multiply(_ otherNode: Node?) -> [Node?] {
    // nil 을 곱하는 것은 0을 곱한 것과 같다고 본다. 
    guard let other = otherNode else { return Node(value: 0) }
    // 두 항의 곱의 결과의 차수는 두 항의 차수의 합과 같다.
    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
    }
    return [Node(value: upFlag, level: level + 1), Node(value: value, level: level)]
  }
}

큰 수 타입의 정의

이제 각 항을 표현하는 타입을 만들었으니, 이를 이용해서 큰 수 타입을 정의해보자. 큰 수 타입은 기본적으로 정수(Int)와 문자열로부터 생성할 수 있으며, 내부적으로는 10,000 을 단위항으로 하는 다항식으로 구현된다. 즉 10,000 진법 짜리 수인 셈이다.

struct BigNumber {
  var nodes: [Node]
  
  init(integer value: Int) {
    var nodes: [Nodes] = []
    var value = integer
    var level = 0
    while value > 0 {
      let v = value % Node.unitSize
      nodes.append(Node(value: v, level: level))
      level += 1
      value = valul / Node.unitSize
    }
    self.nodes = nodes
  }
}     

문자열로부터는 어떻게 정수를 생성할 수 있을까? 쉽게 생각한다면 문자열을 거꾸로 뒤집고, 앞에서부터 4개씩 끊어나가면서, 각 마디를 다시 뒤집어서 항으로 변환하고 담아낼 수 있다. 대신에 여기서는 인덱스를 사용해서 뒤에서부터 4칸씩 앞으로 전진하면서 마디를 끊어내고 이를 Node로 변환해서 다항식을 만들 예정이다.

extension BigNumber {
  init(string str: String) {
    var tempNodes : [Node] = []
    let nodeLength = 4
    var level = 0
    while true {
      var startPos = str.count - nodeLength * (level + 1)
      // 마디의 시작위치가 0보다 작아서는 안된다.
      let endPos: Int = (startPos < 0) ? str.count % nodeLength : 4
      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) {
        nodes.append(Node(value: n, level: level))
        level += 1
      }
      if startPos == 0 {
        break
      }
    self.nodes = tempNodes
  }
}

노드의 집합으로부터 정의

계산 과정에서는 다항식을 정리해서 노드의 집합으로부터 결과 값을 만들어내는 동작이 필요하다. 이를 위해서 노드 배열을 통한 초기화 과정을 정의할 필요가 있다.

extension BigNumber {
  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.nodeSize {
        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
  }
}

문자로 변환하기

큰 수를 다항식으로 다루는 것은 내부적인 로직이며, 계산의 결과가 올바른지 등을 확인하려면 어떤 식으로든 표현하는 방식이 필요하다. 그리고 이때의 표현방식은 10진수 숫자들로 이루어진 문자열이면 괜찮을 것 같다. 문자로 표현하기 위해서는 다음과 같은 과정을 거친다.

  1. 각 노드는 4자리 숫자로 표현된다.
  2. 그런데 노드의 값이 3자리 이하인 경우가 있으므로 각 노드는 0채워서 4자리로 표시해야 한다.
  3. 전체 자리수가 4의 배수가 아닌 경우, 최고차항의 계수가 0으로 패딩이 일어나는데, 이 부분은 제외해야 한다.
  4. 그외 0의 처리

이 때, 2의 경우 포맷을 이용한 문자열을 만들면 좋은데, 이 동작은 String.init(format:,_:)을 써야하고 이는 Foundation 이 필요하다.

extension BigNumber: CustomStringConvertible {
  var description: String {
    let s = nodes.sorted{ $0.level > $1.level }
             .map{ String(format: "%04d", $0.value) }
             .joined(seperator: "")
    // 앞의 0 처리
    if let i = s.characters.index(where: { $0 != "0" }) {
        return (i < s.endIndex) ? s[i..<s.endIndex] : "0"
    }
    return s
  }
}

만약 Foundation을 사용하지 않으려면 다음과 같이 문자열의 내삽과 부분문자열 추출을 통해서 패딩을 적용할 수 있다.

let s = nodes.sorted{ $0.level > $1.level }
        .map{ 
           let x = "000\($0.value)"
           return x[x.index(x.endIndex, offsetBy:-4)..<x.endIndex]
        }.joined(separator: "")

덧셈 구현

두 BigNumber를 더하는 기능을 구현해보도록 하겠다. + 연산자를 사용하면 된다. 연산자 함수는 이제 각 타입에서 static 메소드로 만들면 자동으로 해석되도록 개선됐다.(Swift 3)

extension BigNumber {
  static func + (left: BigNumber, right: BigNumber) -> BigNumber {
    // 덧셈은 두 다항식의 항을 모두 합쳐서 정리해버리면 끝!
    return BigNumber(nodes: left.nodes + right.nodes)
  }
}

곱셈 구현

다항식의 곱셈은 곱해지는 식의 각 항끼리 모두 곱한다음, 그 합을 정리하면 된다. 이중 루프를 돌면서 항끼리 곱하는 방법도 있지만, 조금 더 엘레강스하게(?) 하기 위해서 식에 항 하나를 곱하는 메소드를 하나 정의해보자. 그러면 이들을 모아서 쉽게 항들을 정리할 수 있다.

extension BigNumber {
  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.flatMap{ $0 })
  }
}

이전에 글자 기반의 BigInt 를 작성했을 때, 손으로 하는 곱셈을 구현했던 것에 비해서 놀라운 수준으로 처리가 간단하고, 실제로 수행속도 또한 매우 빠르다는 것을 알 수 있다.

소스코드

전체 소스코드는 아래와 같다.