Go to Qiita Advent Calendar 2024 Top
LoginSignup
14
13

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@dankogai(Dan Kogai)

swift - PONSとAccelerateをマリアージュしたら通常の3倍の倍速くなった件

Last updated at Posted at 2016-02-25

PONSにUInt128を加えてみました。

typetree

任意精度をサポートしているのに、なぜ?

そこにAccelerateがあったから。

Accelerateは本来ヴェクター演算に用いられるライブラリ。とは言っても裸に近いライブラリで、生で食すと腹が壊れかねないので(下記コードで生っぷりの片鱗を見ることができます)、SwiftでもSurgeとか有名なラッパーが出てます。

このAccelerate、実は小さな数をまとめて処理するだけではなく、大きな数を処理する機能も入ってたりします。ただし現時点で OS X のみ。

ならば…

  • OS X では Accelerate を使って
  • それ以外では BigInt に計算代行してもらえば

安価に(128|256|512)bit固定長整数が手に入るんじゃね?

と先ほど思い立ってやってみたら実に安上がりに出来ました。とりあえずUInt128から。

共通部分
public struct UInt128 : POUInt {
    public typealias IntType = BigInt
    public static let precision = 128
    public static let allZeros = UInt128(0)
    public typealias DigitType = BigUInt.DigitType
    public var value:(DigitType, DigitType, DigitType, DigitType) = (0, 0, 0, 0)
    public init(_ d0:DigitType, _ d1:DigitType, _ d2:DigitType, _ d3:DigitType) {
        self.value = (d0, d1, d2, d3)
    }
    public init(_ u128:UInt128) {
        self.value = u128.value
    }
    public init(_ bu:BigUInt) {
        let d  = bu.digits
        switch d.count {
        case 1: value = (d[0],    0,    0,    0)
        case 2: value = (d[0], d[1],    0,    0)
        case 3: value = (d[0], d[1], d[2],    0)
        default:value = (d[0], d[1], d[2], d[3])
        }
    }
    public init(_ u:UIntMax) {
        value.0 = DigitType(u & 0xffff_ffff)
        value.1 = DigitType(u >> 32)
    }
    public init(_ u:UInt) {
        self.init(BigUInt(u))
    }
    public init(_ i:Int) {
        if i < 0 {
            fatalError("\(i) < 0")
        }
        self.init(BigUInt(i.abs))
    }
    public var inBigUInt:BigUInt {
        return BigUInt(rawValue:[value.0, value.1, value.2, value.3])
    }
    public var asBigUInt:BigUInt? {
        return self.inBigUInt
    }
    public func toUIntMax()->UIntMax {
        if value.2 != 0 || value.3 != 0 {
            fatalError("\(self) > UIntMax.max = \(UIntMax.max)")
        }
        return UIntMax(value.1)<<32 | UIntMax(value.0)
    }
    public func toIntMax()->IntMax {
        return IntMax(self.toUIntMax())
    }
    public var asUInt32:UInt32? {
        if value.1 != 0 || value.2 != 0 || value.3 != 0 {
            return nil
        }
        return value.0
    }
    public var msbAt:Int {
        return value.3 != 0 ? 96 + value.3.msbAt
            :  value.2 != 0 ? 64 + value.2.msbAt
            :  value.1 != 0 ? 32 + value.1.msbAt
            :                      value.0.msbAt
    }
    public var asSigned:IntType? {
        return self.inBigUInt.asSigned
    }
    public static let min = UInt128(0)
    public static let max = UInt128(BigUInt(1)<<128-1)
    public static func divideWithOverflow(lhs:UInt128, _ rhs:UInt128)->(UInt128, overflow:Bool) {
        return (divmod(lhs, rhs).0, false)
    }
    public static func remainderWithOverflow(lhs:UInt128, _ rhs:UInt128)->(UInt128, overflow:Bool) {
        return (divmod(lhs, rhs).1, false)
    }
}
public func ==(lhs:UInt128, rhs:UInt128)->Bool {
    let lv = lhs.value
    let rv = rhs.value
    return lv.0 == rv.0 && lv.1 == rv.1 && lv.2 == rv.2 && lv.3 == rv.3
}
public func <(lhs:UInt128, rhs:UInt128)->Bool {
    return UInt128.subtractWithOverflow(lhs, rhs).1
}
public prefix func ~(u128:UInt128)->UInt128 {
    return UInt128(~u128.value.0, ~u128.value.1, ~u128.value.2, ~u128.value.3)
}
public func &(lhs:UInt128, rhs:UInt128)->UInt128 {
    return UInt128(
        lhs.value.0 & rhs.value.0,
        lhs.value.1 & rhs.value.1,
        lhs.value.2 & rhs.value.2,
        lhs.value.3 & rhs.value.3
    )
}
public func |(lhs:UInt128, rhs:UInt128)->UInt128 {
    return UInt128(
        lhs.value.0 | rhs.value.0,
        lhs.value.1 | rhs.value.1,
        lhs.value.2 | rhs.value.2,
        lhs.value.3 | rhs.value.3
    )
}
public func ^(lhs:UInt128, rhs:UInt128)->UInt128 {
    return UInt128(
        lhs.value.0 ^ rhs.value.0,
        lhs.value.1 ^ rhs.value.1,
        lhs.value.2 ^ rhs.value.2,
        lhs.value.3 ^ rhs.value.3
    )
}

見ての通り、BigUIntが[UInt32]で持っている数値の内部表現(単なる(2**32)進法の数値)を(UInt32, UInt32, UInt32, UInt32)で持たせているだけです。

あとは、難しそうな演算はBigUIntか…

Accelerateなし
#if !os(OSX)    // slow but steady BigInt arithmetics
public extension UInt128 {
    public static func addWithOverflow(lhs:UInt128, _ rhs:UInt128)->(UInt128, overflow:Bool) {
        let (bu, overflow) = BigUInt.addWithOverflow(lhs.inBigUInt, rhs.inBigUInt)
        return (UInt128(bu), overflow || bu.digits.count > 4)
    }
    public static func subtractWithOverflow(lhs:UInt128, _ rhs:UInt128)->(UInt128, overflow:Bool) {
        let (bu, overflow) = BigUInt.subtractWithOverflow(lhs.inBigUInt, rhs.inBigUInt)
        return (UInt128(bu), overflow || bu.digits.count > 4)
    }
    public static func multiplyWithOverflow(lhs:UInt128, _ rhs:UInt128)->(UInt128, overflow:Bool) {
        let (bu, overflow) = BigUInt.multiplyWithOverflow(lhs.inBigUInt, rhs.inBigUInt)
        return (UInt128(bu), overflow || bu.digits.count > 4)
    }
    public static func divmod(lhs:UInt128, _ rhs:UInt128)->(UInt128, UInt128) {
        let (q, r) = BigUInt.divmod(lhs.inBigUInt, rhs.inBigUInt)
        return (UInt128(q), UInt128(r))
    }
}
public func <<(lhs:UInt128, rhs:UInt128)->UInt128 {
    return UInt128( lhs.inBigUInt << rhs.inBigUInt )
}
public func >>(lhs:UInt128, rhs:UInt128)->UInt128 {
    return UInt128( lhs.inBigUInt >> rhs.inBigUInt )
}

Accelerateに投げるだけ。

Accelerateあり
#else   // fast arithmetics via Accelerate.  OS X only
import Accelerate
public extension UInt128 {
    public static func addWithOverflow(lhs:UInt128, _ rhs:UInt128)->(UInt128, overflow:Bool) {
        var a = unsafeBitCast((lhs, vU128()), vU256.self)
        var b = unsafeBitCast((rhs, vU128()), vU256.self)
        var ab = vU256()
        vU256Add(&a, &b, &ab)
        let (r, o) =  unsafeBitCast(ab, (UInt128, UInt128).self)
        return (r, o != 0)
    }
    public static func subtractWithOverflow(lhs:UInt128, _ rhs:UInt128)->(UInt128, overflow:Bool) {
        var a = unsafeBitCast((lhs, vU128()), vU256.self)
        var b = unsafeBitCast((rhs, vU128()), vU256.self)
        var ab = vU256()
        vU256Sub(&a, &b, &ab)
        let (r, o) =  unsafeBitCast(ab, (UInt128, UInt128).self)
        return (r, o != 0)
    }
    public static func multiplyWithOverflow(lhs:UInt128, _ rhs:UInt128)->(UInt128, overflow:Bool) {
        var a = unsafeBitCast(lhs, vU128.self)
        var b = unsafeBitCast(rhs, vU128.self)
        var ab = vU256()
        vU128FullMultiply(&a, &b, &ab)
        let (r, o) =  unsafeBitCast(ab, (UInt128, UInt128).self)
        return (r, o != 0)
    }
    public static func divmod(lhs:UInt128, _ rhs:UInt128)->(UInt128, UInt128) {
        var a = unsafeBitCast((lhs, vU128()), vU256.self)
        var b = unsafeBitCast((rhs, vU128()), vU256.self)
        var (q, r) = (vU256(), vU256())
        vU256Divide(&a, &b, &q, &r)
        return (unsafeBitCast(q, (UInt128, UInt128).self).0, unsafeBitCast(r, (UInt128, UInt128).self).0)
    }
}
public func <<(lhs:UInt128, rhs:UInt128)->UInt128 {
    var a = unsafeBitCast((lhs, vU128()), vU256.self)
    var r = vU256()
    vLL256Shift(&a, rhs.asUInt32!, &r)
    return unsafeBitCast(r, (UInt128, UInt128).self).0
}
public func >>(lhs:UInt128, rhs:UInt128)->UInt128 {
    var a = unsafeBitCast((lhs, vU128()), vU256.self)
    var r = vU256()
    vLR256Shift(&a, rhs.asUInt32!, &r)
    return unsafeBitCast(r, (UInt128, UInt128).self).0
}
#endif

これでもう128bit符号なし整数が手に入りました。演算子はもちろんのこと、POUIntにある関数やメソッドは全て使えますし、POUInt以上のProtocolを拡張すれば、その恩恵が即座に降りてきます。

  6> (UInt128(1)<<127 - UInt128(1)).isPrime
$R2: Bool = true

  1> import PONS
  2> func fib<T:POInteger>(n:T)->T { // with a little better algorithm 
  3.     if n < T(2) { return n } 
  4.     var (a, b) = (T(0), T(1)) 
  5.     for _ in 2...n { 
  6.         (a, b) = (b, a+b) 
  7.     } 
  8.     return b 
  9. } 
 10> fib(94 as UInt128).description 
$R0: String = "19740274219868223167"
 11> fib(186 as UInt128).description 
$R1: String = "332825110087067562321196029789634457848"
 12> fib(187 as UInt128).description 
fatal error: overflow: 205697230343233228174223751303346572685 + 332825110087067562321196029789634457848: file pons/pointeger.swift, line 55
Execution interrupted. Enter Swift code to recover and continue.
Enter LLDB commands to investigate (type :help for assistance.)

で、気になる速度の方は…

2.1.1@OSX
fact(34 as UInt128) == 295232799039604140847618609643520000000
UInt128: 22692.6435500538 ops/s (0.0440671443939209s for 1000ops)
BigUInt: 3997.31625495578 ops/s (0.250167846679688s for 1000ops)
UInt128/BigUInt == 5.67696977238667

UInt128で行ける最大の階乗34!を33!で割らせるという演算で、BigUIntの6倍弱ほど速くなってます。

Accelerateの恩恵を受けられない場合でも…

2.2-dev@Linux
fact(34 as BigUInt) == 295232799039604140847618609643520000000
UInt128: 6954.48244758816 ops/s (0.143792152404785s for 1000ops)
BigUInt: 8128.55913611733 ops/s (0.12302303314209s for 1000ops)
UInt128/BigUInt == 0.85556152463572

と極端には遅くなりません。つうか通常のBigUInt(同一マシンのVM上の)Linuxの方が速いんでやんの。まあSwiftのバージョン自体見ての通りXcodeより新しいんですが。

PONSの面目躍如。まさにこういうことをするために作ったんですよ。

Enjoy!

Dan the Protocol-Oriented Swift Programmer

14
13
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
14
13

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?