[ruby-dev:31339] Re: Bignum#to_s 及 Karatsuba 湘醒庍晶卞方月嫖簧祭

< ^ > P N |<>|^_>< --- | ~ ...Help
------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--