ruby-dev

むらけんです．

On 8/1/07, Yusuke ENDOH <mame@tsg.ne.jp> wrote:
> 1. 私のパッチは、数千桁以下の bignum に対してはオリジナルのルーチンを
> 使うようにしています。むらけんさんのテストベンチで効果が出ないのは
> 多分このためです。十数桁でも効果があることがあるんですね。
>
> ただ閾値を大きくとったのには理由があります。Karatsuba のアルゴリズムは
> 中途半端な長さの bignum に対して、逆に遅くなるからです。

そうなんですね．アルゴリズムの性質には詳しくなかったので勉強になります．
私も試してみましたが，十数桁の Bignum に対してはオリジナルの
アルゴリズムの方が速いようですね．これは，ある桁数 N に対して，正数 M が
存在していて，N < M のときに素直に基数で割り算していく方が bigdivmod を
繰り返すより速いということなんでしょうかね？

> 2. 私のパッチは to_s が初めて呼ばれるまでテーブルを初期化しません。
> なので一回目の to_s は遅くなります。
>
> # 遠藤パッチ版
> $ ./ruby -e '(x = 65536**65536).to_s; t = Time.new; x.to_s; p(Time.now - t)'
> 8.390915
>
> # むらけんさんパッチ版
> $ ./ruby -e '(x = 65536**65536).to_s; t = Time.new; x.to_s; p(Time.now - t)'
> 10.460523
>
> もうちょっと正確には、to_s(N) が呼ばれて初めて、必要なところだけ、
> 基数 N のテーブルを初期化する感じです (要するにあまりでかくない
> bignum の to_s に迷惑をかけることはないつもり) 。
>
> # ですが、むらけんさんのパッチはぱっと見テーブルを使ってない？
> # 改善の余地があるのかも。

一応，テーブルっぽいことはやっていますが，その部分が効率よく無いとは自分で
も思っていました．そして，遠藤さんの変更部分を真剣に読ませていただきまして，
ハッシュなんて使う必要なくて，素直に配列で管理できる事に気づきました．
もう一つ，私の実装が素直に再帰を使って実装しているところを，
遠藤さんの実装はループに変換されいますね．どう見ても遠藤さんの実装のほうが
平均すると高速であるように見えます．私の実装は，基数ベキのキャッシュエントリ
数が遠藤さんの実装の2倍あるので，大きな桁数の変換を何度もやるときに有利
になったのだろうと思います．

ということで，パッチは遠藤さんのバージョンを採用していただく方向でよいと思います．

--
- Hide quoted text -
Kenta Murata
OpenPGP FP = FA26 35D7 4F98 3498 0810 E0D5 F213 966F E9EB 0BCC

Thread

Prev Next

In This Thread

Prev Next

[#31320] Import RubyGems to Ruby 1.9 — "NAKAMURA, Hiroshi" <nakahiro@...>

[#31323] Bignum#to_s の Karatsuba 基数変換による高速化 — "Kenta Murata" <muraken@...>

[#31330] Rubyアソシエーション設立のご報告 — Shugo Maeda <shugo@...>

[#31333] Invalid error message by illegal regexp — KIMURA Koichi <kimura.koichi@...>

[#31344] IO.popen with an array in trunk — sheepman <sheepman@...>

[#31345] RDoc i18n化パッチ — KURODA Hiraku <hiraku@...>

[#31349] Array#[]=(pos, length, val) and Array#[]=(range, val) — sheepman <sheepman@...>

[#31351] set_trace_func NULL pointer given — eklerni <eklerni@...>

[#31356] nmake don't have $< macro — KIMURA Koichi <kimura.koichi@...>

[#31357] invalid string for Date.parse — Yukihiro Matsumoto <matz@...>

[#31360] infinite loop at peephole optimization — "Yusuke ENDOH" <mame@...>

[#31361] retry neglects signals — "Yusuke ENDOH" <mame@...>

[#31362] typo in enum.c — Kazuhiro NISHIYAMA <zn@...>

[#31371] simultaneous exceptions dump core — "Yusuke ENDOH" <mame@...>

[#31372] jump in rescue clause in eval dumps core — "Yusuke ENDOH" <mame@...>

[#31373] jump in ensure dumps core — "Yusuke ENDOH" <mame@...>

[#31374] ARGF.each_byte yields a string — Tanaka Akira <akr@...>

[#31376] Re: [ ruby-Bugs-9490 ] Date module, step method, infinite loop if +step+ is 0 should raise an exception? — Urabe Shyouhei <shyouhei@...>

[#31377] Re: [ ruby-Patches-11719 ] add a :passive option to open-uri's open method — Urabe Shyouhei <shyouhei@...>

[#31378] Re: [ ruby-Patches-11954 ] CGI::HTTP_STATUS is incomplete — Urabe Shyouhei <shyouhei@...>

[#31379] Re: [ ruby-Bugs-10646 ] Failure parsing dates returned by WIN32OLE — Urabe Shyouhei <shyouhei@...>

[#31380] Re: [ ruby-Bugs-1823 ] NUM2UINT and rb_num2ull do not rase RangeError for negative Fixnum — Urabe Shyouhei <shyouhei@...>

[#31397] File exists - /tmp/bootstraptest.tmpwd — Tanaka Akira <akr@...>

[#31403] Re: [ ruby-Bugs-3361 ] Ruby 1.8.4 parse errors — Urabe Shyouhei <shyouhei@...>

[#31404] negative allocation size in rb_f_sprintf — Tietew <tietew+ruby-dev@...>

[#31407] [BUG] Stack consistency error (sp: 11, bp: 12) — Tanaka Akira <akr@...>

[#31416] Dir.mktmpdir — Tanaka Akira <akr@...>

[#31417] Process.euid [BUG] Segmentation fault — Tanaka Akira <akr@...>

[#31420] method `method_missing' called on terminated object (0xb7cbd6dc) (NotImplementedError) — Tanaka Akira <akr@...>

[#31424] Re: [ruby-cvs:20177] Re: Ruby:r12931 (trunk): * io.c (argf_close): always close via method. — Nobuyoshi Nakada <nobu@...>

[#31434] LP64: -0x10000000000000001 << -0x80000001 — Tanaka Akira <akr@...>

[#31437] yield [0] to {|*,v|} — Tanaka Akira <akr@...>

[#31438] /bin/sh: BASERUBY@: command not found — Tanaka Akira <akr@...>

[#31439] typo in ChangeLog — Kazuhiro NISHIYAMA <zn@...>

[#31440] yield [1] to {|v,&b| p v } — Tanaka Akira <akr@...>

[#31448] Ruby's (new) Bizarre Operator(s) — Nobuyoshi Nakada <nobu@...>

[#31462] Dir.mktmpdir for 1.8 — Tanaka Akira <akr@...>

[#31464] lambda {|a| p a }.call(1,2) — Tanaka Akira <akr@...>

[#31470] nested fiber invocation — Yukihiro Matsumoto <matz@...>

[#31472] lambda {|&b|}.call(3) — Tanaka Akira <akr@...>

[#31473] setter of $! — SASADA Koichi <ko1@...>

[#31475] lambda {|(v0,v1),v2|}.call([1],2) — Tanaka Akira <akr@...>

[#31480] trunk/test/ruby/test_proc.rb:127 — SASADA Koichi <ko1@...>

[#31481] trunk/test/test_time.rb — SASADA Koichi <ko1@...>

[#31492] SEGV: def m() yield [] end; m(&lambda {|*v| p v}) — Tanaka Akira <akr@...>

[#31502] {|(a,a)|} — Tanaka Akira <akr@...>

[#31507] {|(a)|} assigns outer local variable — Tanaka Akira <akr@...>

[#31511] trunk/test/ruby/test_eval.rb — SASADA Koichi <ko1@...>

[#31522] a, a = 1, 2 — Tanaka Akira <akr@...>

[#31525] いくつかのバグ報告と提案(5点) — eklerni <eklerni@...>

[#31531] 多重代入の*とto_ary — eklerni <eklerni@...>

[#31539] strtod の精度 — Satoshi Nakagawa <snakagawa@...>

[#31547] duck typing — "NAKAMURA, Hiroshi" <nakahiro@...>

[#31561] ignore exception message — SASADA Koichi <ko1@...>

[#31566] test_set and test_hash — Tanaka Akira <akr@...>

[#31576] test/win32ole — SASADA Koichi <ko1@...>

[#31583] Fiber reviesed — SASADA Koichi <ko1@...>

[#31592] [BUG] iseq_compile_each: unknown node: NODE_METHOD — Tanaka Akira <akr@...>

[#31603] benchmark of loops — SASADA Koichi <ko1@...>

[#31609] catch without a tag argument — Tanaka Akira <akr@...>

[#31625] IO.sysdup2, IO.sysdup, IO.sysclose — Tanaka Akira <akr@...>

[#31643] Re: [ruby-list:43915] Re: Hashへの生成順は保障されないのか？ — SASADA Koichi <ko1@...>

[#31646] Re: [ruby-cvs:20498] Ruby:r13261 (trunk): * encoding.c: provide basic features for M17N. — Tanaka Akira <akr@...>

[#31650] ungetc — Tanaka Akira <akr@...>

[#31651] rb_enc_mbclen — Tanaka Akira <akr@...>

[#31652] test/ruby/ — SASADA Koichi <ko1@...>

[#31659] each_byte and break — Tanaka Akira <akr@...>

[#31661] String#inspectで無限ループ — akira yamada / やまだあきら <akira@...>

[#31663] return in rescue in while in eval dumps core — "Yusuke ENDOH" <mame@...>

[#31665] String#slice! — WATANABE Tetsuya <Tetsuya.WATANABE@...>

[#31666] IndexError in rindex — Nobuyoshi Nakada <nobu@...>

[#31669] Re: [ ruby-Bugs-11882 ] recursive invokation of garbage_collect() in dlptr_free() — Urabe Shyouhei <shyouhei@...>

[#31671] Array#slice! — Satoshi Nakagawa <snakagawa@...>

[#31672] -Kオプションとparser->encの関係 — akira yamada / やまだあきら <akira@...>

[#31674] flush_register_windowsの"ta 0x83" — akira yamada / やまだあきら <akira@...>

[#31678] optimize empty hash space — Tanaka Akira <akr@...>

[#31679] ruby_1_8_5 undefined reference to `_RSTRING_PTR' — Masaki Suketa <masaki.suketa@...>

[#31682] mkmf.rb:310:in `method_missing': undefined method `quote' for nil:NilClass — akira yamada / やまだあきら <akira@...>

[#31684] WindowsのUnicodeファイル名 — OJ <oj@24.am>

[#31687] instance variable as formal argument — "Yusuke ENDOH" <mame@...>

[#31351] set_trace_func　NULL pointer given — eklerni <eklerni@...>