From: Yusuke ENDOH <mame@...>
Date: 2008-12-14T13:01:52+09:00
Subject: [ruby-dev:37435] Re: [1.9:Feature] faster bignum multiplication by karatsuba method

遠藤です。

2008/12/12 13:02 Tadashi Saito <shiba@mail2.accsnet.ne.jp>:
> 以前[ruby-dev:32629]で書いていらっしゃったFFT版と比べてはどうなのでしょう。
> 素人考えでは、両方共桁が十分に大きい場合のより厳しい条件下では、Karatsubaから
> 切り替えれば速くなる気がします。

覚えてくれている人がいたとは。ありがとうございます。

実は私自身がもうあんまり覚えてないんですが、本当に桁が大きい場合は FFT の
方が早いはずなので、試していませんが多分その方法は有効だと思います。

ただあのパッチは、double 型が IEEE754 の倍精度であること (特に仮数部が
52bit 以上あること) を仮定しているため、そうでない変な環境で動かないので
ダメ、と言うコメントがついた記憶があります (ML でなく IRC で) 。

コンパイル時に double 型の仮数部が 52 bit 以上かどうかを判定できれば取り
込めるかもしれませんが、

- 「変な環境」でちゃんと動くかテストをするのが難しい
- Karatsuba 乗算でもまあ十分かなと思う
- 今となってはあのパッチにあまり自信がない (誤差評価をどうやったかとか
  全く覚えてない)

ので、正直なところ、私自身は作業する気がないです。

-- 
Yusuke ENDOH <mame@tsg.ne.jp>