------art_84524_28191180.1186047815015
Content-Type: text/plain; charset=ISO-2022-JP
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

むらたです.

On 8/1/07, Yusuke ENDOH <mame / tsg.ne.jp> wrote:
> ただ閾値を大きくとったのには理由があります。Karatsuba のアルゴリズムは
> 中途半端な長さの bignum に対して、逆に遅くなるからです。
(snip)
> 1 回あたりの速度劣微々たるものですが、65536**65536 のような超でかい
> bignum を to_s する場合より、10000000000000 程度の数字を to_s することの
> 方が直感的には多です。
> どのくらいの数字で逆転するのかは (面倒だったので) 調べてません。

KARATSUBA_DIGITS を 1024, 512, 256, 128 と変せて時間を計測しました;

鴣磔澑芦 Ж 亀涯教騎匡閙鷸 辣鈿閙齔鶉夂辣鈿鶇桶梓原凱鴣磔澣渦  Ж 亀涯教騎匡閙鷸 辣鈿閙齔鶉夂辣鈿鶇臼訓怯軒鴣磔濂偽  Ж 亀涯教騎匡閙鷸 辣鈿閙齔鶉夂辣鈿鶇臼寛鬼庚鴣磔澑恩  Ж 亀涯教騎匡閙鷸 辣鈿閙齔鶉夂辣鈿鶇桶攻葦
以上の結果から,256桁と128桁の間で逆転していることが分かります.
で提案ですが,KARATSUBA_DIGITS を 256 にして,big2str_table の
エントリ数を 16 から 64 に増やすというのはどうでしょう?

[ruby-dev:31312] で遠藤さんが行った変更も含む新しいパッチを添付しました.
テーブルのエントリ数のために MAX_BIG2STR_TABLE_ENTRIES を定義しました.

--
Kenta Murata
OpenPGP FP  A26 35D7 4F98 3498 0810 E0D5 F213 966F E9EB 0BCC

------art_84524_28191180.1186047815015
Content-Type: application/octet-stream; name="bignum_karatsuba.patch"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="bignum_karatsuba.patch"
X-Attachment-Id: f_f4v28hzh

SW5kZXg6IGJpZ251bS5jCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09
PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIGJpZ251bS5jCSjjg6rjg5Pjgrjjg6fjg7Mg
MTI4NTkpCisrKyBiaWdudW0uYwko5L2c5qWt44Kz44OU44O8KQpAQCAtNjM1LDYgKzYzNSw5NCBA
QAogfQogCiBjb25zdCBjaGFyIHJ1YnlfZGlnaXRtYXBbXSA9ICIwMTIzNDU2Nzg5YWJjZGVmZ2hp
amtsbW5vcHFyc3R1dnd4eXoiOworc3RhdGljIGlubGluZSBpbnQKK2JpZzJzdHJfbm9ybWFsKFZB
TFVFIHgsIGxvbmcgaiwgaW50IGJhc2UsIGludCBoYmFzZSwgY2hhciAqcywgaW50IHRyaW0pCit7
CisgICAgbG9uZyBpID0gUkJJR05VTSh4KS0+bGVuOworICAgIEJESUdJVCAqZHMgPSBCRElHSVRT
KHgpOworCisgICAgd2hpbGUgKGkgJiYgaiA+IDEpIHsKKyAgICAgICBsb25nIGsgPSBpOworICAg
ICAgIEJESUdJVF9EQkwgbnVtID0gMDsKKworICAgICAgIHdoaWxlIChrLS0pIHsKKyAgICAgICAg
ICAgbnVtID0gQklHVVAobnVtKSArIGRzW2tdOworICAgICAgICAgICBkc1trXSA9IChCRElHSVQp
KG51bSAvIGhiYXNlKTsKKyAgICAgICAgICAgbnVtICU9IGhiYXNlOworICAgICAgIH0KKyAgICAg
ICBpZiAodHJpbSAmJiBkc1tpLTFdID09IDApIGktLTsKKyAgICAgICBrID0gU0laRU9GX0JESUdJ
VFM7CisgICAgICAgd2hpbGUgKGstLSkgeworICAgICAgICAgICBzWy0tal0gPSBydWJ5X2RpZ2l0
bWFwW251bSAlIGJhc2VdOworICAgICAgICAgICBudW0gLz0gYmFzZTsKKyAgICAgICAgICAgaWYg
KCF0cmltICYmIGogPCAxKSBicmVhazsKKyAgICAgICAgICAgaWYgKHRyaW0gJiYgaSA9PSAwICYm
IG51bSA9PSAwKSBicmVhazsKKyAgICAgICB9CisgICAgfQorICAgIHJldHVybiBqOworfQorCisj
ZGVmaW5lIEtBUkFUU1VCQV9ESUdJVFMgMTI4CisjZGVmaW5lIE1BWF9CSUcyU1RSX1RBQkxFX0VO
VFJJRVMgNjQKK3N0YXRpYyBWQUxVRSBiaWcyc3RyX3RhYmxlWzM3XVtNQVhfQklHMlNUUl9UQUJM
RV9FTlRSSUVTXTsKKworc3RhdGljIFZBTFVFIGJpZ3NxcihWQUxVRSB4KTsKK3N0YXRpYyB2b2lk
IGJpZ2Rpdm1vZChWQUxVRSB4LCBWQUxVRSB5LCBWQUxVRSAqZGl2cCwgVkFMVUUgKm1vZHApOwor
CitzdGF0aWMgaW5saW5lIGludAorYmlnMnN0cl9rYXJhdHN1YmEoVkFMVUUgeCwgaW50IG4sIGlu
dCBiYXNlLCBpbnQgaGJhc2UsIGNoYXIgKnMsIGludCB0cmltKQoreworICAgIGxvbmcgaSwgaiwg
aywgYnNfbGVuLCBzaWduID0gUkJJR05VTSh4KS0+c2lnbjsKKyAgICB2b2xhdGlsZSBWQUxVRSB0
ID0gYmlnMnN0cl90YWJsZVtiYXNlXVswXSwgdDI7CisgICAgVkFMVUUgKmFzLCAqYnMsIHEsIHI7
CisKKyAgICBqID0gUkJJR05VTSh0KS0+bGVuOworICAgIGZvciAoaT0wOyBqIDw9IFJCSUdOVU0o
eCktPmxlbjsgaSsrKSBqICo9IDI7CisKKyAgICBhcyA9IEFMTE9DQV9OKFZBTFVFLCBpKTsKKwor
ICAgIGZvciAoaT0wLGo9MTsgOyBpKyssaio9MikgeworICAgICAgIGFzW2ldID0gdDsKKyAgICAg
ICBpZihiaWcyc3RyX3RhYmxlW2Jhc2VdW2kgKyAxXSkgeworICAgICAgICAgICB0MiA9IGJpZzJz
dHJfdGFibGVbYmFzZV1baSArIDFdOworICAgICAgIH0KKyAgICAgICBlbHNlIHsKKyAgICAgICAg
ICAgdDIgPSBiaWdzcXIodCk7CisgICAgICAgICAgIGlmKGkgKyAxIDwgTUFYX0JJRzJTVFJfVEFC
TEVfRU5UUklFUykgeworICAgICAgICAgICAgICAgYmlnMnN0cl90YWJsZVtiYXNlXVtpICsgMV0g
PSB0MjsKKyAgICAgICAgICAgICAgIHJiX2dsb2JhbF92YXJpYWJsZSgmYmlnMnN0cl90YWJsZVti
YXNlXVtpICsgMV0pOworICAgICAgICAgICB9CisgICAgICAgfQorICAgICAgIGlmKFJCSUdOVU0o
eCktPmxlbiA8IFJCSUdOVU0odDIpLT5sZW4pIGJyZWFrOworICAgICAgIHQgPSB0MjsKKyAgICB9
CisKKyAgICBic19sZW4gPSBqICogMjsKKyAgICBicyA9IEFMTE9DQV9OKFZBTFVFLCBic19sZW4p
OworICAgIGJzWzBdID0geDsKKyAgICBSQklHTlVNKHgpLT5zaWduID0gMTsKKyAgICBmb3IgKDsg
aj4wOyBpLS0sIGovPTIpIHsKKyAgICAgICBmb3IgKGs9MDsgazxic19sZW47IGsrPWoqMikgewor
ICAgICAgICAgICBiaWdkaXZtb2QoYnNba10sIGFzW2ldLCAmcSwgJnIpOworICAgICAgICAgICBi
c1trXSA9IHE7CisgICAgICAgICAgIGJzW2sgKyBqXSA9IHI7CisgICAgICAgfQorICAgIH0KKyAg
ICBSQklHTlVNKHgpLT5zaWduID0gc2lnbjsKKworICAgIGogPSAwOworICAgIHdoaWxlKFJCSUdO
VU0oYnNbal0pLT5sZW4gPT0gMSAmJiBCRElHSVRTKGJzW2pdKVswXSA9PSAwKSBqKys7CisgICAg
Zm9yIChpPWJzX2xlbi0xOyBpPmo7IGktLSkgeworICAgICAgIGsgPSBiaWcyc3RyX25vcm1hbCgK
KyAgICAgICAgICAgYnNbaV0sIEtBUkFUU1VCQV9ESUdJVFMsIGJhc2UsIGhiYXNlLAorICAgICAg
ICAgICBzICsgbiAtIEtBUkFUU1VCQV9ESUdJVFMsIFFmYWxzZSk7CisgICAgICAgbiAtPSBLQVJB
VFNVQkFfRElHSVRTIC0gazsKKyAgICB9CisgICAgbiA9IGJpZzJzdHJfbm9ybWFsKGJzW2pdLCBu
LCBiYXNlLCBoYmFzZSwgcywgdHJpbSk7CisKKyAgICByZXR1cm4gbjsKK30KKwogVkFMVUUKIHJi
X2JpZzJzdHIwKHgsIGJhc2UsIHRyaW0pCiAgICAgVkFMVUUgeDsKQEAgLTY0Miw3ICs3MzAsNiBA
QAogICAgIGludCB0cmltOwogewogICAgIHZvbGF0aWxlIFZBTFVFIHQ7Ci0gICAgQkRJR0lUICpk
czsKICAgICBsb25nIGksIGosIGhiYXNlOwogICAgIFZBTFVFIHNzOwogICAgIGNoYXIgKnM7CkBA
IC02ODksMjkgKzc3NiwxNiBAQAogI2VuZGlmCiAKICAgICB0ID0gcmJfYmlnX2Nsb25lKHgpOwot
ICAgIGRzID0gQkRJR0lUUyh0KTsKICAgICBzcyA9IHJiX3N0cl9uZXcoMCwgaisxKTsKICAgICBz
ID0gUlNUUklORyhzcyktPnB0cjsKIAogICAgIHNbMF0gPSBSQklHTlVNKHgpLT5zaWduID8gJysn
IDogJy0nOwotICAgIHdoaWxlIChpICYmIGogPiAxKSB7Ci0JbG9uZyBrID0gaTsKLQlCRElHSVRf
REJMIG51bSA9IDA7Ci0KLQl3aGlsZSAoay0tKSB7Ci0JICAgIG51bSA9IEJJR1VQKG51bSkgKyBk
c1trXTsKLQkgICAgZHNba10gPSAoQkRJR0lUKShudW0gLyBoYmFzZSk7Ci0JICAgIG51bSAlPSBo
YmFzZTsKLQl9Ci0JaWYgKHRyaW0gJiYgZHNbaS0xXSA9PSAwKSBpLS07Ci0JayA9IFNJWkVPRl9C
RElHSVRTOwotCXdoaWxlIChrLS0pIHsKLQkgICAgc1stLWpdID0gcnVieV9kaWdpdG1hcFtudW0g
JSBiYXNlXTsKLQkgICAgbnVtIC89IGJhc2U7Ci0JICAgIGlmICghdHJpbSAmJiBqIDwgMSkgYnJl
YWs7Ci0JICAgIGlmICh0cmltICYmIGkgPT0gMCAmJiBudW0gPT0gMCkgYnJlYWs7Ci0JfQorICAg
IGlmIChSQklHTlVNKHgpLT5sZW4gPiBSQklHTlVNKGJpZzJzdHJfdGFibGVbYmFzZV1bMF0pLT5s
ZW4gKiA0KSB7CisgICAgICAgaiA9IGJpZzJzdHJfa2FyYXRzdWJhKHQsIGosIGJhc2UsIGhiYXNl
LCBzLCB0cmltKTsKICAgICB9CisgICAgZWxzZSB7CisgICAgICAgaiA9IGJpZzJzdHJfbm9ybWFs
KHQsIGosIGJhc2UsIGhiYXNlLCBzLCB0cmltKTsKKyAgICB9CiAgICAgaWYgKHRyaW0pIHt3aGls
ZSAoc1tqXSA9PSAnMCcpIGorKzt9CiAgICAgaSA9IFJTVFJJTkcoc3MpLT5sZW4gLSBqOwogICAg
IGlmIChSQklHTlVNKHgpLT5zaWduKSB7CkBAIC03MjcsNiArODAxLDIyIEBACiAgICAgcmV0dXJu
IHNzOwogfQogCitzdGF0aWMgdm9pZAoraW5pdF9iaWcyc3RyX3RhYmxlKHZvaWQpCit7CisgICAg
aW50IGksIGo7CisgICAgVkFMVUUgdjsKKworICAgIGZvciAoaT0wOyBpPDM3OyBpKyspIHsKKyAg
ICAgICB2ID0gcmJfYmlnX3BvdyhyYl9pbnQyYmlnKGkpLCBJTlQyRklYKEtBUkFUU1VCQV9ESUdJ
VFMpKTsKKyAgICAgICBiaWcyc3RyX3RhYmxlW2ldWzBdID0gdjsKKyAgICAgICByYl9nbG9iYWxf
dmFyaWFibGUoJmJpZzJzdHJfdGFibGVbaV1bMF0pOworICAgICAgIGZvciAoaj0xOyBqIDwgTUFY
X0JJRzJTVFJfVEFCTEVfRU5UUklFUzsgaisrKSB7CisgICAgICAgICAgIGJpZzJzdHJfdGFibGVb
aV1bal0gPSBRZmFsc2U7CisgICAgICAgfQorICAgIH0KK30KKwogVkFMVUUKIHJiX2JpZzJzdHIo
VkFMVUUgeCwgaW50IGJhc2UpCiB7CkBAIC0yMzQ0LDQgKzI0MzQsNiBAQAogICAgIHJiX2RlZmlu
ZV9tZXRob2QocmJfY0JpZ251bSwgInRvX2YiLCByYl9iaWdfdG9fZiwgMCk7CiAgICAgcmJfZGVm
aW5lX21ldGhvZChyYl9jQmlnbnVtLCAiYWJzIiwgcmJfYmlnX2FicywgMCk7CiAgICAgcmJfZGVm
aW5lX21ldGhvZChyYl9jQmlnbnVtLCAic2l6ZSIsIHJiX2JpZ19zaXplLCAwKTsKKworICAgIGlu
aXRfYmlnMnN0cl90YWJsZSgpOwogfQo------art_84524_28191180.1186047815015--