天泣記

Ruby の Bignum の歴史をちょっと調べてみた。メモ:
2002-04-10 r2348 matz: BDIGIT などの定義を bignum.c (と marshal.c) から defines.h に移動
2007-04-25 http://yowaken.dip.jp/tdiary/20070425.html#p02 累乗が遅い
2007-04-26 http://yowaken.dip.jp/tdiary/20070426.html#p01 累乗が遅い (2) -> r12236 (2007-05-02) bigsqr の導入 (Karatsuba ではないが、因数分解を利用して 2乗を高速化)
2007-07-18 http://d.hatena.ne.jp/ku-ma-me/20070718/p2 mame: 高速 Bignum#to_s
2007-07-19 http://www.rubyist.net/~matz/20070719.html#p05 matz: 上記 (高速 Bignum#to_s) への参照
2007-07-29 [ruby-dev:31312] mame: Karatsuba の基数変換アルゴリズムで Bignum#to_s を高速化
2007-08-01 [ruby-dev:31323] mrkn: Bignum#to_s の Karatsuba 基数変換による高速化 -> mrkn&mame の議論 -> [ruby-dev:31354] r12893
2007-09-01 [ruby-dev:31689] akr: 小さな Bignum を RBignum に埋め込む -> r13330
2007-12-19 [ruby-dev:32632] mame: rb_big_mul0 と divrem を rb_thread_blocking_region で実行して、Ctrl-C を効くようにする -> r14329
2007-12-19 [ruby-dev:32629] mame: FFT を用いた乗算を実装 (未適用。理由は [ruby-dev:37435])
2008-01-17 [ruby-dev:33139] mame: オブジェクトの生成を rb_thread_blocking_region の外で行う -> r15322
2008-09-05 [ruby-dev:36169] TOYOFUKU Chikanobu: bigdivrem1 の y で、後ろの zero が連なっている部分の処理を省く。Bignum#to_s の基数が2のべき乗のときに効く。-> r19171
2008-12-12 [ruby-dev:37392] mame: bignum の乗算を Karatsuba 法などで高速化 -> r20733 (rb_thread_blocking_region で bigmul1 を呼ぶのは除去)
2008-12-14 [ruby-dev:37434] mame: bigsqr(x) がなんか遅い (bigmul0(x, x) した方が速い) -> r20739
2009-08-07 http://d.hatena.ne.jp/CanI/20090807/1249657492 BDIGITS() がループ内で繰り返し呼ばれていて遅い -> r24444
2010-02-27 r26771 rb_big_pack, rb_big_unpack の導入
2010-12-03 [ruby-list:47675] mrkn: Bignum#* を Toom3 乗法に対応させる -> r31695
2012-02-23 [ruby-core:42813] Martin Bosslet: Allow Bignum marshalling/unmarshalling from C API -> r42202, r42208 by akr (2013-07-28)
2013-05-31 r41004 いろいろいじり始めた (akr)
2013-06-10 [ruby-dev:47413] akr: Use 128 bit integer type in Bignum -> r41379
天泣記

2013-07-27 (Sat)

2013-07-31 (Wed)
