[#11357] [PATCH] an analogue of `long long' — "Nobuyoshi.Nakada" <nobu.nakada@...>

なかだです。

18 messages 2000/11/01
[#11358] Re: [PATCH] an analogue of `long long' — matz@... (Yukihiro Matsumoto) 2000/11/01

まつもと ゆきひろです

[#11364] Re: [PATCH] an analogue of `long long' — EGUCHI Osamu <eguchi@...> 2000/11/02

えぐち@エスアンドイー です。

[#11440] class Character (was: Ruby I18N) — Yasushi Shoji <yashi@...>

[ruby-dev:11428] からの続きですが、threadは切りました。

14 messages 2000/11/08
[#11442] Re: class Character (was: Ruby I18N) — TAKAHASHI Masayoshi <maki@...> 2000/11/08

高橋征義です。用語について。

[#11443] Re: class Character (was: Ruby I18N) — Yasushi Shoji <yashi@...> 2000/11/08

At Wed, 8 Nov 2000 20:44:55 +0900,

[#11520] A problem of Socket methods on Windows — OKA Toshiyuki <oka@...>

岡と申します。

22 messages 2000/11/15
[#11523] Re: A problem of Socket methods on Windows — "Nobuyoshi.Nakada" <nobu.nakada@...> 2000/11/15

なかだです。

[#11528] Re: A problem of Socket methods on Windows — matz@... (Yukihiro Matsumoto) 2000/11/15

まつもと ゆきひろです

[#11532] Re: A problem of Socket methods on Windows — "Nobuyoshi.Nakada" <nobu.nakada@...> 2000/11/15

なかだです。

[#11534] Re: A problem of Socket methods on Windows — OKA Toshiyuki <oka@...> 2000/11/15

岡です。

[#11535] Re: A problem of Socket methods on Windows — "Nobuyoshi.Nakada" <nobu.nakada@...> 2000/11/15

なかだです。

[#11538] Re: A problem of Socket methods on Windows — "Nobuyoshi.Nakada" <nobu.nakada@...> 2000/11/15

なかだです。

[#11662] IO (Re: fork problem?) — Tanaka Akira <akr@...17n.org>

In article <E140cR3-0002ls-00@ev.netlab.zetabits.co.jp>,

22 messages 2000/11/28
[#11663] Re: IO (Re: fork problem?) — matz@... (Yukihiro Matsumoto) 2000/11/28

まつもと ゆきひろです

[#11664] Re: IO (Re: fork problem?) — Tanaka Akira <akr@...17n.org> 2000/11/28

In article <E140fxW-0002u9-00@ev.netlab.zetabits.co.jp>,

[#11665] Re: IO (Re: fork problem?) — Tanaka Akira <akr@...17n.org> 2000/11/28

In article <hvor93w5wb8.fsf@coulee.m17n.org>,

[#11669] Re: IO (Re: fork problem?) — Tanaka Akira <akr@...17n.org> 2000/11/29

In article <hvoofz05uwz.fsf@coulee.m17n.org>,

[#11672] Re: IO (Re: fork problem?) — matz@... (Yukihiro Matsumoto) 2000/11/29

まつもと ゆきひろです

[#11675] Re: IO (Re: fork problem?) — Koji Arai <JCA02266@...> 2000/11/30

新井です。

[#11677] Re: IO (Re: fork problem?) — matz@... (Yukihiro Matsumoto) 2000/12/01

まつもと ゆきひろです

[ruby-dev:11359] Re: bignum

From: Masahiro Tanaka <masa@...>
Date: 2000-11-01 16:53:36 UTC
List: ruby-dev #11359
田中です

>From: matz@zetabits.com (Yukihiro Matsumoto)
>Subject: [ruby-dev:11289] bignum

> 「Bignumが遅い」という苦情が来ました。gmpより10倍遅い(場合が
> ある)んだそうです。Pythonよりは速いんだけどな。

>   (a) Bignumをgmpベースに置き換える
>   (b) Bignumを書き換える
>   (c) gmpのラッパーの拡張ライブラリを書く

> 逆に(c)はむしろ簡単すぎるので(b)を考えてみました。速いのに越
> したことはないし。そこでKnuthのThe art of computer programming
> を眺めてみたのですが、数学的素養のない私には理解できませんで
> した。


すでに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回ですむ、ということを使ったものだそうです。
計算量が O(N**2) から O(N**1.58) になるんだとか。

アルゴリズムも考えたのですが、動かすところまではいっていません。

田中昌宏

In This Thread