From: matz@... (Yukihiro Matsumoto)
Date: 2000-11-02T02:30:10+09:00
Subject: [ruby-dev:11360] Re: bignum

まつもと ゆきひろです

In message "[ruby-dev:11359] Re: bignum"
    on 00/11/02, Masahiro Tanaka <masa@stars.gsfc.nasa.gov> writes:

|すでにBignumのdigit typeが変わっていますね。

かなりエンバグしちゃったみたいですがだんだん落ち着いてきてい
るようです。

|Karatsuba のアルゴリズムについてちょっと調べたところ、
|(もうご存知かも知れませんが)
|
| x = x1 + x2 * t**n
| y = y1 + y2 * t**n
|
|のかけ算をするときに、
|
| x*y = x1*y1 + (x1*y2+x2*y1) * t**n  + x2*y2 * t**(2*n)
|
|とすると乗算が4回必要になのに対して、
|
| x*y = x1*y1 + ( x1*y1 + x2*y2 - (x1-x2)*(y1-y2) ) * t**n  + x2*y2 * t**(2*n)
|
|とすると3回ですむ、ということを使ったものだそうです。

こう書いてもらえたらなんとなくわかって来たように思います。
ありがとうございます。

Knuthの本ではなんだか再帰を使ってるようなんですが、なんといっ
ても例題がMIX(要するにアセンブラ)で書いてあるんで、良く分か
んなかったのでした。新版を英語で読んだ方が良いのかも。って新
版でもMIXなのかしら。

ところでKaratsubaってなんとなく日本的な響きですがロシア(当時
はソ連か)の人みたいですね。論文は1962年に出てます。

                                まつもと ゆきひろ /:|)