狠狠撸

詳解! Decimal

筑波大学情報科学類科目等履修生?Tsukuba.rb

斎藤ただし

非常に軽い自己绍介

←ぎだがんどぅ→

1 なう！ 2

群馬　　栃木　　茨城

多倍长十进小数演算ライブラリ

Decimal

Decimalとは何か?
● 斎藤が書き起こしたプロダクト
● 多倍长十进小数演算ライブラリ
● ふつうの小数を好きな長さだけ計算できる
● 組み込みのFloatを補う
● Ruby標準添付ライブラリBigDecimalの後継を
目指す
● シンプル?高速?使いやすい?正確

decimal.rubyforge.org

Floatは不正確! (1/2)
● 超FAQ
x = 0.0
10.times { x += 0.1 }
x == 1.0 #=> false!?
● 何度「バグ報告」されてるか分からない
● 例えば
http://redmine.ruby-lang.org/issues/show/4394
● “Learn floating point numbers. What Every
Computer Scientist Should Know About Floating-
Point Arithmetic ...” by @nalsh

Floatは不正確! (2/2)
● 10進小数が有限桁の2進小数で表現できる条件
by @mrkn
● http://d.hatena.ne.jp/mrkn/20110223
● n 桁の10進小数は、それを10m倍して5nの倍数にで
きるような自然数ｍ≧ｎが存在するとき、有限桁の
2進小数で表現できる
● 0.1は、0.1 * 10 = 1 が 51 の倍数ではないので有限
桁の2進小数で表現できない
● → 十進小数演算ライブラリの存在意義

Decimalとは何でないか?
● 無限の長さの小数を計算
● 「1 / 3」の結果は正確に保持できない
● 桁数が有限なのはFloatと一緒、あくまでも「可能
な限りの(任意の)長さ」
● BigDecimalができない事ができる画期的なもの
● あくまでより良い再発明


っていうか何で
そんなことやってるの?

ちょっと俺の身の上話を
聞いてくださいよ


小学生
● 5年生の授業参観日、算数
● 円周率 π に出会う (人生初の無理数)
● 先生「…という風に、ずっとに続いていきま
す。」
● 俺「全部調べた事もないのに、なんで分かる
の?」
● 先生「大きくなったら、スウガクを勉強してく
ださい。」

「大きくなったら、スウガクを
勉強してください。」


根に持ってしまった。


中学生
● C言語に出会う
● 当然 π を計算!
● ……あれ?
● 何百桁も計算してるはずなのに出てこない
● ていうか途中から間違ってるし
● C言語の小数は「固定長」だった!
● 代わりに「多倍長整数」に出会う
● 手元で実装したり

高校生
● 多倍長「整数」の計算に必要な数式を組み立て
ては崩し
● 「いくらでも長い整数」が扱えれば「いくらで
も長い小数」も扱えるんじゃ?
● AO入試で逆質問
● 先生「んなの簡単」
● 俺「???」
● Rubyに出会う (Ruby本の出る出る詐欺未遂事件)

大学生
● Rubyにちょっかいを出し始める
● 1.8リリース、標準添付ライブラリ拡大路線
● BigDecimalが飛び込んできた!!!
● ソースを読んだり、数式で悩んだり
● ようやく「いくらでも長い小数」を計算できる
原理を理解


BigDecimalのAPIにちょっかい
● 2003年、1.8.0リリースの直前
● 前身のBigFloatとは違う性質
● なのに代わり映えしないAPI(メソッド群)
● Numeric全般も気にしないオレオレAPI
● →だいぶ変えてもらいました
● →まだ不満
● →ほぼそのまま現在に至る(1.9.2)

身の上をまとめると
● π を計算したかった
● BigDecimalには不満があった
● →なら新しく作っちゃえばいいじゃない
● ＝ Decimal !
● Decimal::Math.pi(n) #=> 小数点以下n桁のπ!


Decimal
設計上の工夫


設計上の工夫
● APIは最小限に
● 既存クラスとの親和性を高く
● 厳密さを保つ


APIは最小限に
● オレオレAPIはいらない
● クラスメソッド5個、インスタンスメソッド13個減
● 「多倍長」「十進」を生かすものは残す
● d = Decimal(“1.23”)
d.round(1, :up) #=> Decimal(1.3)
● 必要になったら後から入れる
● 後から「消す」のは大変だよね


既存クラスとの親和性を高く
● Rubyの数なんだからNumeric
● 「小数」なんだから「だいたいFloat」
● Float?他のNumericのメソッドと同じ名前では
同じ動作
● Floatを返すMath.functionも
Decimal::Math.functionとして実装
● sinとかsqrtとかlogとか
● Floatと違い、何桁でも計算できます

厳密さを保つ
● BigDecimalはFloatとの「自然な」演算が有効
● BigDecimal(“1.23”) + 0.1 #=> 通っちゃう…不正確!
● Decimalはプログラマが精度を明示しない限り
厳密さを保つ
● Floatとの演算を軒並みエラーに
● 不正確さを明示
● どうしても一緒にしたいときはDecimal#to_fして
ください

Decimal
実装上の工夫


実装上の工夫
●
コード再利用
●
省メモリ


その前に
「多倍長十進小数」の
内部構造の復習


搁耻产测碍补颈驳颈2009…


小数は
整数の組
で表せる

「314」の
「下から2桁目」
に小数点

(大きい整数, 小さい整数)

小数の計算
≒
整数の計算

復習終わり


コード再利用 (1/2)
● BigDecimalは「大きい整数」を自前で実装
● それってBignumでよくない?
● →やったらあっさりできた
● C API: rb_big_plus(), rb_big_mul(), …
● 135,334 バイト (BigDecimal)
vs 59,706 バイト (Decimal)
● 55%以上の小型化
● しかも速いし (e.g. 1.9.1 → 1.9.2)

コード再利用 (2/2)
●
つまり
●
実装のコンパクト化
●
高速化
●
同時に達成!
●
B-)


省メモリ (1/2)
●
BigDecimal インスタンス本体
typedef struct {

← いらない
VALUE obj;
U_LONG MaxPrec;
U_LONG Prec;
S_INT exponent;
short sign;
short flag;
U_LONG frac[1];
} Real;


省メモリ (2/2)
●
我がDecimal インスタンス本体

typedef struct {
VALUE inum;
long scale;
} Decimal;

●
スッキリ！


という感じで
● いろいろがんばりました
● Ruby Summer of Codeに採択&完走、賞金$5000!

● ／(^o^)＼

まとめ
● Decimalはふつうの小数をふつうに計算するた
めのライブラリです
● 既存のBigDecimalよりおいしいです (^p^
● 使ってやってください m(_ _)m


狠狠撸

詳解! Decimal

More Related Content

詳解! Decimal