Help us understand the problem. What is going on with this article?

Swift - Introducing PONS = Protocol Oriented Number System

More than 1 year has passed since last update.

まだ荒削りですが、お披露目してもいいところまで来たので。

売り口上

これでSwiftでも

  • GMPとか外部ライブラリなしで任意精度整数(BigInt)や任意精度分数(BigRat)や任意精度浮動小数点数(BigFloat)が使えるようになります。
  • 外部依存がないので、Xcodeでなくてもswiftcがあれば使えます。もちろんOS XだけでなくてLinuxもサポート
  • その任意精度数も、四則演算以外の演算を最初からサポートしています。整数は素数判定できますし、任意精度実数は<math.h>の関数を使えます。

これだけでもかなりハッピーになれます。

でも本当のウリは、そこじゃないんですよ…

承前: 古き良きCの時代

例えばman powとしてみます。こんな答えが返ってくるでしょう。

SYNOPSIS
    #include <math.h>

    double
    pow(double x, double y);

    long double
    powl(long double x, long double y);

    float
    powf(float x, float y);

なんで全く同じことをする関数が三つあるのか?

異なった型ごとに、違う実装が必要だから。

20世紀までは仕方ないことだったのかもしれませんが、21世紀ももう1/8過ぎた2016年にこんなの付き合ってられませんよね?

で、Swiftでは、

同じpowという名前でDoubleにもFloatにも対応しています。やったね!

import Cocoa    // this is an OSX playground
let twelveTet = pow(2.0, 1.0/12)
pow(Float(twelveTet), 12)           // not exactly 2.0 but you get the point

でも、使う側でなくて作る側として、どうしたらそのような関数が書けるでしょう?

とりあえずfibってみる

とりあえずみんな大好きフィボナッチ数でも数えてみますか。前世紀脳だと、こんな感じになりますか。

勤勉なやり方

func fib(n:Int8)->Int8   { return n < 2 ? i : fib(n-2)+fib(n-1) }
func fib(n:Int16)->Int16 { return n < 2 ? i : fib(n-2)+fib(n-1) }
func fib(n:Int32)->Int32 { return n < 2 ? i : fib(n-2)+fib(n-1) }
func fib(n:Int64)->Int64 { return n < 2 ? i : fib(n-2)+fib(n-1) }
// hey, don't forget UInt(8|16|32|64)?

つまり、型シグネチャーが異なる同名の関数を、型の数だけ繰り返す、と。

やってられるか!

<T:Hoge>でどうHogeる?

幸いSwiftには総称型があります。ならこう書ける?

func fib<T>(i:T)->T { return i < 2 ? i : fib(n-2)+fib(n-1) }

残念でした。T<できたり、Tどうし+できたりって誰が保証してくれるんですか?

それを保証してくれるのが、Protocolなんですが…

func fib<T:Hoge>(i:T)->T { return i < 2 ? i : fib(n-2)+fib(n-1) }

で、Hogeプロトコルが<+をサポートしてさえすれば、これは動くはずです。

が、そのHogeってどこにあるの?

import PONS

PONSの役割は、それを提供すること。

import PONS     // make sure you have built the framework before this!

func fib<T:POInteger>(n:T)->T { // with a little better algorithm
    if n < T(2) { return n }
    var (a, b) = (T(0), T(1))
    for _ in 2...n {
        (a, b) = (b, a+b)
    }
    return b
}

ちょっとアルゴリズムを改良しました。

で、これが本当に動くのか?

let F11 = fib(11 as Int8)
let F13 = fib(13 as UInt8)
let F23 = fib(23 as Int16)
let F24 = fib(24 as UInt16)
let F46 = fib(46 as Int32)
let F47 = fib(47 as UInt32)
let F92 = fib(92 as Int64)
let F93 = fib(93 as UInt64)

動くんです。

しかし、PONSの本領はここからがはじまりです。あなたが苦労して実装した新たな整数方も受け付けてGeneric Programmingを名乗れるというものです。

でもどうやってそれを証明する?

そのためにBigInt実装しちゃいましたよ。てへぺろ。

よってこれが動きます。

let F666 = fib(666 as BigInt)

ちなみに6859356963880484413875401302176431788073214234535725264860437720157972142108894511264898366145528622543082646626140527097739556699078708088だそうです。

整数だけで許されるのは小学生までだよねー

カントールをパワハラして後世の評判を多いに下げたクロネッカーは、こうのたまいました。

整数は神の作ったものだが、他は人間の作ったものである

人間上等、というわけで我々はさまざまな数を作ってきました。有理数に実数にそして複素数。あの古き良きCですらC99で複素数をサポートしたぐらいです。それくらい数値というのは切実なわけです。

ところがSwiftは標準で複素数をサポートしていません。というわけで書いたのが

なのですが、これを書いたことでむしろ欲求不満は高まりました。

「たしかに総称型で、たしかにIntDoubleも受け入れられるけど、BigIntとかRationalとか突っ込んでも大丈夫?っつうかそれ以前に突っ込むべき数値型が見当たらないんだが」

というわけで実装しましたよ。Genericで「整数」型ならBigIntだって分子と分母に使えるRationalに…

let bq = BigInt(1).over(bn)     // (1/18446744073709551617)
bq + bq // (2/18446744073709551617)
bq - bq // (0/1)
bq * bq // (1/340282366920938463500268095579187314689)
bq / bq // (1/1)
bq.denominator == bn            // true, of course!
bq.reciprocal.numerator == bn   // so is this

そのRational含め、「実数」型なら実部と虚部に使えるComplex

let bz = bq + bq.i  // ((1/18446744073709551617)+(1/18446744073709551617).i)
bz + bz // ((2/18446744073709551617)+(2/18446744073709551617).i)
bz - bz // ((0/1)+(0/1).i)
bz * bz // ((0/1)+(2/340282366920938463500268095579187314689).i)
bz / bz // ((1/1)+(0/1).i)

動くぞ、動くぞ!

でも、整数におけるfact(orial)やfib(onacci)なようなデモを、実数とか複素数でやるにはどうしたらいいの?

<math.h>な関数が、総称型でも動くことを見せつければいい!

という気持ちでやった。後悔はしていない。

Double.sqrt(2)
Double.sqrt(2)                  // 1.414213562373095
BigRat.sqrt(2)                  // (112045541949572279837463876455/79228162514264337593543950336)
BigFloat.sqrt(2)                // 1.414213562373095048801688724198
Complex.sqrt(-2)                // (0.0+1.4142135623731.i)
Complex.sqrt(BigRat(-2))        // 112045541949572279837463876455/79228162514264337593543950336).i)

個人的に一番感動したのは、これ。

Complex.exp(Double.PI.i)        // (-1.0+1.22464679914735e-16.i) != (-1.0+0.0.i) // :(
// default 64-bit precision is still not good enough…
Complex.exp(BigRat.pi().i)      // (-(1/1)-(1/4722366482869645213696).i)
// but with 128-bit precision…
Complex.exp(BigRat.pi(128).i)   // (-(1/1)+(0/1).i) // as it should be!

128bit精度の有理数型なら e ** πi == -1 に本当になるんです!(厳密にはsin(pi) < ulpのというわけなのですが)。

すべての型別実装を、生まれる前に消し去りたい

PONSの存在意義は、 Write once, runs on every type (that conform to the protocol) が、数値型でも成立することを示すことにあります。

例えば三角関数のcossinは、(現時点において)
以下のように定義されています。

cos()
public static func cos(x:Self, precision:Int = 64)->Self {
    if let dx = x as? Double { return Self(Double.cos(dx)) }
    let px = Swift.max(x.precision, precision)
    let epsilon = Self(Double.ldexp(1.0, -px))
    let x2 = x * x
    var (r, t) = (Self(1), Self(1))
    for i in 1...px {
        t *= x2.divide(Self((2 * i - 1) * 2 * i), precision:px)
        t.truncate(px + 32)
        r += i & 1 == 1 ? -t : t
        r.truncate(px + 32)
        if t < epsilon { break }
    }
    return r.truncate(px)
}
sin()
public static func sin(x:Self, precision:Int = 64)->Self {
    if let dx = x as? Double { return Self(Double.sin(dx)) }
    let px = Swift.max(x.precision, precision)
    let epsilon = Self(Double.ldexp(1.0, -px))
    let x2 = x * x
    var r = x < 0 ? -x : x
    var t = r
    for i in 1...px {
        t *= x2.divide(Self((2 * i + 1) * 2 * i), precision:px)
        t.truncate(px + 32)
        r += i & 1 == 1 ? -t : t
        r.truncate(px + 32)
        if t < epsilon { break }
    }
    return x < 0 ? -r.truncate(px) : r.truncate(px)
}

数学者でなくとも、これはテイラー展開

sincos

をほぼそのままであることが見て取れるかと思いますが、重要なのはこれがFloatDoubleはおろか、BigRat = Rational<BigInt>でもBigFloatでもまったく変更なしに動くこと。一行目に

if let dx = x as? Double { return Self(Double.sin(dx)) }

とはありますが、これはコメントアウトしても動きます(その分Double.cosDouble.sinは遅くはなりますが)。

なんで/でなくて.divideなのか、.truncateは何をしているかとかは後日別記事で紹介する予定ですが、いずれにせよ将来Float128とか実装したとしても、サインコサインできちゃうわけです。

とりあえず使ってみるには

git clone して PONS.xcworkspace開いて、フレームワークをbuildしたらplaygroundで遊べます。Xcodeがなくともmake replすればコマンドラインから遊べます。自分のプロジェクトで使いたい場合は、ソースをまるっとコピーするだけです。

当初予定を超えて大きなプロジェクトになったので、まだまだ全然説明したりないのですが、とりあえず「なんぞこれ」はこれで伝わっているといいなあ…

Enjoy!

Dan the Protocol-Oriented Swift Programmer

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした