BigInt 타입의 Swift 구현

BigInt.swift

//
//  BigInt.swift
//  EulerKit
//
//  Created by soooprmx on 2015. 6. 2..
//  Copyright (c) 2015년 sooop. All rights reserved.
//

import Foundation

/* 큰수의 덧셈과 곱셈을 위한 BigInt 
    1. 실제 데이터는 UInt64 타입으로 저장한다.
    2. 몇자리 수인지를 가늠하는 정보가 있다.
    3. 데이터 케리어가 몇 개인지 가늠하는 정보가 있다. 
    4. 데이터를 문자열로 표시할 수 있다. 
    5. 일반 정수를 가지고 초기화 가능
    6. 문자열로부터 초기화 가능
*/


public struct BigInt: Printable, Equatable, Comparable {
    
    static let unitSize:Int = 8
    static let unitLimit:UInt64 = 1_0000_0000
    
    let data:[UInt64]
    let numberOfDigits:Int
    
    public init(data:[UInt64], numberOfDigits:Int){
        self.data = data
        self.numberOfDigits = numberOfDigits
    }
    
    public init(str:String){
        let length = (str as NSString).length
        self.init(data: parseString(str), numberOfDigits:length)
    }
    
    public init(int:Int){
        let length = Int(ceil(log10(Double(int))))
        let value = UInt64(abs(int))
        self.init(data:[value], numberOfDigits:length)
    }
    
    public var description: String {
        var result = ""
        for i in 0..<self.numberOfDigits {
            result += "\(self.data[self.numberOfDigits - i - 1])"
        }
        return result
    }
    
    private var numberOfCells:Int {
        return (self.numberOfDigits / BigInt.unitSize) + 1
    }
    
    func __add(another: BigInt) -> BigInt {
        let maxLength = self.numberOfCells <? another.numberOfCells
        var dataArray = [UInt64]()
        var flag:UInt64 = 0
        for i in 0..<maxLength {
            let l = i >= self.numberOfCells ? 0 : self.data[i]
            let r = i >= another.numberOfCells ? 0 : another.data[i]
            var k = l + r + flag
            if k >= BigInt.unitLimit {
                flag = k / BigInt.unitLimit
                k = k % BigInt.unitLimit
            } else {
                flag = 0
            }
            dataArray.append(k)
        }
        if flag > 0 {
            dataArray.append(flag)
        }
        
        let numberOfDigitInResult = (dataArray.count - 1) * BigInt.unitSize + Int(log10(Double(dataArray.last!)))
        return BigInt(data: dataArray, numberOfDigits: numberOfDigitInResult)
    }
}

public func +(lhs:BigInt, rhs:BigInt) -> BigInt {
    return lhs.__add(rhs)
}

public func ==(lhs:BigInt, rhs:BigInt) -> Bool {
    if lhs.numberOfDigits != rhs.numberOfDigits {
        return false
    }
    for i in 0..<lhs.numberOfCells {
        if lhs.data[i] != rhs.data[i] {
            return false
        }
    }
    return true
}

public func <(lhs:BigInt, rhs:BigInt) -> Bool {
    if lhs.numberOfDigits < rhs.numberOfDigits {
        return true
    } else if lhs.numberOfDigits > rhs.numberOfDigits {
        return false
    }
    for i in 0..<lhs.numberOfCells {
        if lhs.data[i] < rhs.data[i] {
            return true
        } else if lhs.data[i] > rhs.data[i] {
            return false
        }
    }
    return false
}


infix operator <? {}
func <?<T:Comparable>(l:T, r:T) -> T {
    if l >= r {
        return l
    }
    return r
}


private func parseString(str:String) -> [UInt64] {
    
    let numbers = Array(str.unicodeScalars).map{ return UInt64($0.value) - 48}
    
    let unitSize = 8
    let length = numbers.count
    let numberOfCell = (length / unitSize) + 1
    
    var currentPosition:Int
    var level:UInt64 = 1
    var dataArray:Array<UInt64> = []
    var k:UInt64 = 0
    
    mainLoop: for i in 0..<numberOfCell {
        for j in 0..<8 {
            currentPosition = length - (i * unitSize) - j - 1
            if currentPosition < 0 {
                dataArray.append(k)
                break mainLoop
            }
            k = k + numbers[currentPosition] * level
            level *= 10
        }
        dataArray.append(k)
        k = 0
        level = 1
    }
    
    return dataArray
}

BigInt2.swift

// 큰 수를 Int 값을 계수로 하는 큰 다항식으로보고 계산한다.
// 특히 곱셈의 경우 매우 빠른 속도 향상이 있다. 

struct BigInt: CustomStringConvertible { 
    // Swift 2.0 에서는 Printable이 CustomStringConvertible로 변경됨

    static let UNIT = 100000000 // 8자리씩 끊어서 이용함. 32비트에서는 4자리로.
    let unit_count = 8
    typealias NumberBucket = (Int, Int)
    
    let data: [NumberBucket]


    init(_ buckets: [NumberBucket]) {
        data = BigInt.roundUp(buckets)
    }


    init(var _ intValue:Int) {
        var level = 0
        var temp = [NumberBucket]()

        while intValue > 0 {
            temp.append((intValue % BigInt.UNIT, level))
            level += 1
            intValue = intValue / BigInt.UNIT
        }

        data = temp
    }


    init(_ strValue:String) {
        var level = 0
        var temp = [NumberBucket]()
        let u = Array(strValue.utf8).map{ Int($0) - 48 }
        let l = u.count
        for a in 0...l/unit_count {
            var d = 0
            for b in 0..<unit_count {
                let c = l - (unit_count * a + unit_count - b - 1) - 1
                if c < 0 {
                    continue
                }
                d = d * 10 + u[c]
            }
            temp.append((d, level))
            level += 1
        }
        data = temp
    }


    var description: String {
        let d = data.sort{ $0.1 > $1.1 }
        return "(d[0].0)" + "".join(d[1..<d.count].map{String(format:"%04d", $0.0)})
        // return "".join(d.map{String($0)})
    }


    static func roundUp(buckets:[NumberBucket]) -> [NumberBucket] {
        let maxKey = buckets.map{ $0.1 }.reduce(buckets[0].1){ $0 > $1 ? $0 : $1 }
        var result = [NumberBucket]()
        var flag = 0
        for k in 0...maxKey {
            var s = buckets.filter{ $0.1 == k }.map{ $0.0 }.reduce(flag, combine: +)
            if s >= BigInt.UNIT {
                flag = s / BigInt.UNIT
                s = s % BigInt.UNIT
            } else {
                flag = 0
            }
            result.append((s, k))
        }
        if flag > 0 {
            result.append((flag, maxKey+1))
        }
        return result
    }


    static func multiplyNumberBucket(l:NumberBucket, _ r:NumberBucket) -> [NumberBucket] {
        let x = l.0 * r.0
        let y = l.1 + r.1
        if x < BigInt.UNIT {
            return [(x, y)]
        }
        return [(x % BigInt.UNIT, y), (x / BigInt.UNIT, y+1)]
    }    
    
    func add(target:BigInt) -> BigInt {
        return BigInt(data + target.data)
    }

    func multiply(target:BigInt) -> BigInt {
        var result = [NumberBucket]()
        for a in data {
            for b in target.data {
                result += BigInt.multiplyNumberBucket(a, b)
            }
        }
        return BigInt(result)
    }
}

func +(lhs:BigInt, rhs:BigInt) -> BigInt {
    return lhs.add(rhs)
}

func *(lhs:BigInt, rhs:BigInt) -> BigInt {
    return lhs.multiply(rhs)
}


timeit{
    let s = "3710728753390210279..." // 숫자는 개행문자로 붙여서 하나의 문자열로 만들어 둠.
    let ns = s.componentsSeparatedByString("n")
    let c = ns.map{BigInt($0)}.reduce(BigInt(1), combine:+)
    print(c.description[0..<10])
}
// 5537376230
// time: 0.0170680284500122 ms

Numbers.swift

func factorial(n:Int) -> Int {
        if n < 2 {
            return 1
        }
        return n * factorial(n-1)
}

// 주어진 리스트의 n(n=0,1,2,3...)번째 사전식 순열을 구하는 함수
func perm<T>(n:Int, list:[T]) -> [T] {
    let l = list.count
    if l <= 1 {
        return list
    }

    func divmod(a:Int, b:Int) -> (Int, Int) {
        return (a / b, a % b)
    }
    
    if list.count == 1 {
        return list
    }
    
    let (q, r) = divmod(n, factorial(list.count - 1))
    return [list[q]] + perm(r, Array(list[0..<q]) + Array(list[(q+1)..<list.count]))
}

// 문자열의 n 번째 순열을 구하는 함수 

func perm(n:Int, var list:String) -> String {
    let l = (list as NSString).length

    if l < 2 {
        return list
    }
    
    func divmod(a:Int, b:Int) -> (Int, Int) {
        return (a / b, a % b)
    }
    
    let (q, r) = divmod(n, factorial(list.count - 1)
    let n = String(list.removeAtIndex(advance(list.startIndex, q)))
    return n + perm(r, list)
}