From: Kenta Murata Date: 2007-08-02T18:43:32+09:00 Subject: [ruby-dev:31339] Re: Bignum#to_s の Karatsuba 基数変換による高速化 ------=_Part_84524_28191180.1186047815015 Content-Type: text/plain; charset=ISO-2022-JP Content-Transfer-Encoding: 7bit Content-Disposition: inline むらたです． On 8/1/07, Yusuke ENDOH wrote: > ただ閾値を大きくとったのには理由があります。Karatsuba のアルゴリズムは > 中途半端な長さの bignum に対して、逆に遅くなるからです。 (snip) > 1 回あたりの速度劣化は微々たるものですが、65536**65536 のような超でかい > bignum を to_s する場合より、10000000000000 程度の数字を to_s することの > 方が直感的には多そうです。 > どのくらいの数字で逆転するのかは (面倒だったので) 調べてません。 KARATSUBA_DIGITS を 1024, 512, 256, 128 と変化させて処理時間を計測しました． $ ./ruby_1024 -e '(x = 65536**65536).to_s; s=Time.now; x.to_s; puts(Time.now-s)' 23.048639 $ ./ruby_512 -e '(x = 65536**65536).to_s; s=Time.now; x.to_s; puts(Time.now-s)' 11.716184 $ ./ruby_256 -e '(x = 65536**65536).to_s; s=Time.now; x.to_s; puts(Time.now-s)' 11.425493 $ ./ruby_128 -e '(x = 65536**65536).to_s; s=Time.now; x.to_s; puts(Time.now-s)' 23.960106 以上の結果から，256桁と128桁の間で逆転していることが分かります． そこで提案ですが，KARATSUBA_DIGITS を 256 にして，big2str_table の エントリ数を 16 から 64 に増やすというのはどうでしょう？ [ruby-dev:31312] で遠藤さんが行った変更も含む新しいパッチを添付しました． テーブルのエントリ数のために MAX_BIG2STR_TABLE_ENTRIES を定義しました． -- Kenta Murata OpenPGP FP = FA26 35D7 4F98 3498 0810 E0D5 F213 966F E9EB 0BCC ------=_Part_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= ------=_Part_84524_28191180.1186047815015--