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

< ^ > P N |<>|^_>< --- | ~ ...Help
------art_68138_11322615.1185961038442
Content-Type: text/plain; charset=ISO-2022-JP
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

戈日仃氏匹允‘

# 颱及午仇欠卞 ruby-dev:31312 互廴中化卅中及互尕閤腔’’’

On 8/1/07, Yukihiro Matsumoto <matz / ruby-lang.org> wrote:
> 引勾手午 斗五夫欠匹允
> 切斤丹升[ruby-dev:31312]毛潸曰慇手丹午閤勻化中凶泫燮分勻凶及
> 匹允互﹜升勻切互中中匹允井友尹﹝

⑺元橢瘀匹港畮痐繴袌洶楔①勻誘卅𠴲罊怤悀楔縣擗中中�蚺中牏楔縑阬
匹﹞驕尥及方丹卅由永民午﹞矛件民穴□弁皿伕弘仿丞匹煌竅仄凶午仇欠
動票及方丹卞卅曰引仄凶‘

$ ./ruby -I lib karatsuba.rb
Rehearsal --------------------------------------------------
original         2.410000   0.000000   2.410000 (  9.625259)
ruby-dev:31312   2.420000   0.000000   2.420000 (  9.635740)
ruby-dev:31323   1.740000   0.000000   1.740000 (  6.842046)
----------------------------------------- total: 6.570000sec

                    user     system      total        real
original         2.420000   0.000000   2.420000 (  9.931306)
ruby-dev:31312   2.420000   0.000000   2.420000 (  9.627448)
ruby-dev:31323   1.740000   0.000000   1.740000 (  6.842890)

卅兮井 ruby-dev:31312 互﹞左伉斥瓜伙午⺶勝仄化鍍仁卅勻化卅中及匹允互﹞
矛件民穴□弁皿伕弘仿丞互鬼中及匹仄斤丹井’’’
簽[ruby-dev:31312] 互簧仁卅月橢瘀午﹞颱及 [ruby-dev:31323] 互
簧仁卅月橢瘀互啜丹午中丹咥荸匹恌中手及井升丹井‘

笛尹化﹞[ruby-dev:31323] 匹驕尥仄凶颱及由永民反田弘互丐月橇謫及手及匹仄凶‘
懇仄仁反﹞

+VALUE
+rb_big2str_karatsuba(VALUE x, VALUE base)
+{
+    return rb_big2str0_karatsuba(x, FIX2INT(base), Qtrue);
+}
+

仇及朿坌毛動票及方丹卞竣楔④砟壑竣丑阬

庠賻桲
恤瘊睾蝎黀蟷錆蠌鏵礱嶁祫枎欓 濎皸鵴拽
   蠈鏷襜 蠋蜋氃莢鐍唯錆蠌鏵礱嶁欓 皸鵴栠觶憍拱

丐午﹜Karatsuba午中尹壬井仃遙
> 及嫖簧勾中化手(失伙打伉朮丞互咥荸匹五內)幻勻凶日井仄分勻
> 凶氏匹允方友尹﹝

漆允什午中丹歹仃卞反中井卅中及匹允互﹞仇切日手澎毛勾仃方丹午閤勻化中引允‘
Ruby 卞反匹五月分仃簧仁卅勻化手日中凶中匹允 :)

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

------art_68138_11322615.1185961038442
Content-Type: application/octet-stream; name=bignum_31312_31323.patch
Content-Transfer-Encoding: base64
X-Attachment-Id: f_f4tmk8r8
Content-Disposition: attachment; filename="bignum_31312_31323.patch"

SW5kZXg6IGJpZ251bS5jCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09
PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIGJpZ251bS5jCShyZXZpc2lvbiAxMjg1OSkK
KysrIGJpZ251bS5jCSh3b3JraW5nIGNvcHkpCkBAIC0xOSw2ICsxOSw4IEBACiAjaW5jbHVkZSA8
aWVlZWZwLmg+CiAjZW5kaWYKIAorI2luY2x1ZGUgPHN0Lmg+CisKIFZBTFVFIHJiX2NCaWdudW07
CiAKICNpZiBkZWZpbmVkIF9fTUlOR1czMl9fCkBAIC03MjcsMTIgKzcyOSw0NjcgQEAKICAgICBy
ZXR1cm4gc3M7CiB9CiAKKyNkZWZpbmUgTUFYX1BPV0VSX0NBQ0hFX0VOVFJJRVMgNjQKKworc3Ry
dWN0IHBvd2VyX2NhY2hlX2RhdGEKK3sKKyAgICBWQUxVRSBwb3dlcjsKKyAgICBsb25nICBtYWdp
YzsKK307CisKK3N0cnVjdCBwb3dlcl9jYWNoZV9lbnRyeQoreworICAgIHN0X3RhYmxlKiBjYWNo
ZTsKKyAgICBsb25nICAgICAgbGVuOworfTsKKworc3RydWN0IHBvd2VyX2NhY2hlCit7CisgICAg
c3RydWN0IHBvd2VyX2NhY2hlX2VudHJ5IGVudHJpZXNbMzVdOworfTsKKworc3RhdGljIGludAor
bWFya19jYWNoZV9lbnRyeShsb25nIG4xLCBzdHJ1Y3QgcG93ZXJfY2FjaGVfZGF0YSogZGF0YSwg
dm9pZCogXykKK3sKKyAgICByYl9nY19tYXJrKGRhdGEtPnBvd2VyKTsKKyAgICByZXR1cm4gU1Rf
Q09OVElOVUU7Cit9CisKK3N0YXRpYyB2b2lkCitwb3dlcl9jYWNoZV9tYXJrKHN0cnVjdCBwb3dl
cl9jYWNoZSogcGMpCit7CisgICAgaW50IGk7CisgICAgZm9yIChpID0gMDsgaSA8IDM1OyArK2kp
CisgICAgICAgIHN0X2ZvcmVhY2gocGMtPmVudHJpZXNbaV0uY2FjaGUsIG1hcmtfY2FjaGVfZW50
cnksIDApOworfQorCitzdGF0aWMgaW50CitmcmVlX2NhY2hlX2VudHJ5KGxvbmcgbjEsIHN0cnVj
dCBwb3dlcl9jYWNoZV9kYXRhKiBkYXRhLCB2b2lkKiBfKQoreworICAgIGlmIChkYXRhICE9IDAp
CisgICAgICAgIGZyZWUoZGF0YSk7CisgICAgcmV0dXJuIFNUX0RFTEVURTsKK30KKworc3RhdGlj
IHZvaWQKK3Bvd2VyX2NhY2hlX2ZyZWUoc3RydWN0IHBvd2VyX2NhY2hlKiBwYykKK3sKKyAgICBp
bnQgaTsKKyAgICBmb3IgKGkgPSAwOyBpIDwgMzU7ICsraSkgeworICAgICAgICBzdF9mb3JlYWNo
KHBjLT5lbnRyaWVzW2ldLmNhY2hlLCBmcmVlX2NhY2hlX2VudHJ5LCAwKTsKKyAgICAgICAgc3Rf
ZnJlZV90YWJsZShwYy0+ZW50cmllc1tpXS5jYWNoZSk7CisgICAgfQorICAgIGZyZWUocGMpOwor
fQorCitzdGF0aWMgVkFMVUUgYmlnMnN0cl9wb3dlcl9jYWNoZSA9IDA7CisKK3N0YXRpYyB2b2lk
Citwb3dlcl9jYWNoZV9pbml0KHZvaWQpCit7CisgICAgc3RydWN0IHBvd2VyX2NhY2hlKiBwYzsK
KyAgICBpbnQgaTsKKworICAgIGJpZzJzdHJfcG93ZXJfY2FjaGUgPSBEYXRhX01ha2VfU3RydWN0
KAorICAgICAgcmJfY0RhdGEsIHN0cnVjdCBwb3dlcl9jYWNoZSwgcG93ZXJfY2FjaGVfbWFyaywg
cG93ZXJfY2FjaGVfZnJlZSwgcGMpOworICAgIHJiX2dsb2JhbF92YXJpYWJsZSgmYmlnMnN0cl9w
b3dlcl9jYWNoZSk7CisgICAgZm9yIChpID0gMDsgaSA8IDM1OyBpKyspIHsKKyAgICAgICAgcGMt
PmVudHJpZXNbaV0uY2FjaGUgPSBzdF9pbml0X251bXRhYmxlKCk7CisgICAgICAgIHBjLT5lbnRy
aWVzW2ldLmxlbiA9IDA7CisgICAgfQorfQorCitzdHJ1Y3QgcG93ZXJfY2FjaGVfZmluZF90b19y
ZW1vdmVfZGF0YQoreworICAgIGxvbmcgbjE7CisgICAgbG9uZyBtYXhfbWFnaWM7Cit9OworCitz
dGF0aWMgaW50Citwb3dlcl9jYWNoZV9maW5kX3RvX3JlbW92ZShsb25nIG4xLCBzdHJ1Y3QgcG93
ZXJfY2FjaGVfZGF0YSogcGNkLAorICAgICAgICAgICAgICAgICAgICAgICAgICAgc3RydWN0IHBv
d2VyX2NhY2hlX2ZpbmRfdG9fcmVtb3ZlX2RhdGEqIGRhdGEpCit7CisgICAgaWYgKHBjZC0+bWFn
aWMgPiBkYXRhLT5tYXhfbWFnaWMpIHsKKyAgICAgICAgZGF0YS0+bjEgPSBuMTsKKyAgICAgICAg
ZGF0YS0+bWF4X21hZ2ljID0gcGNkLT5tYWdpYysrOworICAgIH0KKyAgICByZXR1cm4gU1RfQ09O
VElOVUU7Cit9CisKK3N0YXRpYyBWQUxVRQorcG93ZXJfY2FjaGVfbG9va3VwKGJhc2UsIG4xKQor
ICAgIGludCBiYXNlOworICAgIGxvbmcgbjE7Cit7CisgICAgc3RydWN0IHBvd2VyX2NhY2hlKiBw
YzsKKyAgICBzdHJ1Y3QgcG93ZXJfY2FjaGVfZGF0YSogcGNkID0gMDsKKworICAgIGlmIChiaWcy
c3RyX3Bvd2VyX2NhY2hlID09IDApIHBvd2VyX2NhY2hlX2luaXQoKTsKKyAgICBEYXRhX0dldF9T
dHJ1Y3QoYmlnMnN0cl9wb3dlcl9jYWNoZSwgc3RydWN0IHBvd2VyX2NhY2hlLCBwYyk7CisgICAg
aWYgKHBjLT5lbnRyaWVzW2Jhc2UgLSAyXS5sZW4gPT0gMCB8fAorICAgICAgICAhc3RfbG9va3Vw
KHBjLT5lbnRyaWVzW2Jhc2UgLSAyXS5jYWNoZSwgbjEsIChzdF9kYXRhX3QqKSZwY2QpKQorICAg
ICAgICByZXR1cm4gUW5pbDsKKyAgICByZXR1cm4gcGNkLT5wb3dlcjsKK30KKworc3RhdGljIHZv
aWQKK3Bvd2VyX2NhY2hlX2luc2VydChiYXNlLCBuMSwgcG93ZXIpCisgICAgaW50IGJhc2U7Cisg
ICAgbG9uZyBuMTsKKyAgICBWQUxVRSBwb3dlcjsKK3sKKyAgICBzdHJ1Y3QgcG93ZXJfY2FjaGUq
IHBjOworICAgIHN0cnVjdCBwb3dlcl9jYWNoZV9kYXRhKiBwY2Q7CisKKyAgICBEYXRhX0dldF9T
dHJ1Y3QoYmlnMnN0cl9wb3dlcl9jYWNoZSwgc3RydWN0IHBvd2VyX2NhY2hlLCBwYyk7CisgICAg
aWYgKHBjLT5lbnRyaWVzW2Jhc2UgLSAyXS5sZW4gPT0gTUFYX1BPV0VSX0NBQ0hFX0VOVFJJRVMp
IHsKKyAgICAgICAgc3RydWN0IHBvd2VyX2NhY2hlX2ZpbmRfdG9fcmVtb3ZlX2RhdGEgZGF0YSA9
IHsgMCwgMCB9OworICAgICAgICBzdF9mb3JlYWNoKHBjLT5lbnRyaWVzW2Jhc2UgLSAyXS5jYWNo
ZSwKKyAgICAgICAgICAgICAgICAgICBwb3dlcl9jYWNoZV9maW5kX3RvX3JlbW92ZSwgKHN0X2Rh
dGFfdCkmZGF0YSk7CisgICAgICAgIHN0X2RlbGV0ZShwYy0+ZW50cmllc1tiYXNlIC0gMl0uY2Fj
aGUsICZkYXRhLm4xLCAwKTsKKyAgICAgICAgcGMtPmVudHJpZXNbYmFzZSAtIDJdLmxlbi0tOwor
ICAgIH0KKworICAgIHBjZCA9IEFMTE9DKHN0cnVjdCBwb3dlcl9jYWNoZV9kYXRhKTsKKyAgICBw
Y2QtPnBvd2VyID0gcG93ZXI7CisgICAgcGNkLT5tYWdpYyA9IDA7CisgICAgc3RfaW5zZXJ0KHBj
LT5lbnRyaWVzW2Jhc2UgLSAyXS5jYWNoZSwgbjEsIChzdF9kYXRhX3QpcGNkKTsKKyAgICBwYy0+
ZW50cmllc1tiYXNlIC0gMl0ubGVuKys7Cit9CisKK3N0YXRpYyBWQUxVRQorcG93ZXJfY2FjaGVf
Z2V0X3Bvd2VyKGJhc2UsIG4xKQorICAgIGludCBiYXNlOworICAgIGxvbmcgbjE7Cit7CisgICAg
VkFMVUUgcG93ZXIgPSBwb3dlcl9jYWNoZV9sb29rdXAoYmFzZSwgbjEpOworICAgIGlmIChOSUxf
UChwb3dlcikpIHsKKyAgICAgICAgcG93ZXIgPSByYl9iaWdfcG93KHJiX2ludDJiaWcoYmFzZSks
IExPTkcyTlVNKG4xKSk7CisgICAgICAgIHBvd2VyX2NhY2hlX2luc2VydChiYXNlLCBuMSwgcG93
ZXIpOworICAgIH0KKyAgICByZXR1cm4gcG93ZXI7Cit9CisKKy8qIGJpZzJzdHJfa2FyYXRzdWJh
X2ZpbmRfbjEKKyAqCisgKiBMZXQgYSBuYXR1cmFsIG51bWJlciB4IGlzIGdpdmVuIGJ5OgorICog
eCA9IDJeMCAqIHhfMCArIDJeMSAqIHhfMSArIC4uLiArIDJeKEIqbl8wIC0gMSkgKiB4X3tCKm5f
MCAtIDF9LAorICogd2hlcmUgQiBpcyBCSVRTUEVSRElHIChpLmUuIEJESUdJVFMqQ0hBUl9CSVQp
IGFuZCBuXzAgaXMKKyAqIFJCSUdOVU0oeCktPmxlbi4KKyAqCisgKiBOb3csIHdlIGFzc3VtZSBu
XzEgPSBtaW5fbiBceyBuIHwgMl4oQipuXzAvMikgPD0gYl8xXihuXzEpIFx9LCBzbworICogaXQg
aXMgcmVhbGl6ZWQgdGhhdCAyXihCKm5fMCkgPD0ge2JfMX1eezIqbl8xfSwgd2hlcmUgYl8xIGlz
IGEKKyAqIGdpdmVuIHJhZGl4IG51bWJlci4gQW5kIHRoZW4sIHdlIGhhdmUgbl8xIDw9IChCKm5f
MCkgLworICogKDIqbG9nXzIoYl8xKSksIHRoZXJlZm9yZSBuXzEgaXMgZ2l2ZW4gYnkgY2VpbCgo
QipuXzApIC8KKyAqICgyKmxvZ18yKGJfMSkpKS4KKyAqLworc3RhdGljIGxvbmcKK2JpZzJzdHJf
a2FyYXRzdWJhX2ZpbmRfbjEoVkFMVUUgeCwgaW50IGJhc2UpCit7CisgICAgc3RhdGljIGNvbnN0
IGRvdWJsZSBsb2dfMltdID0geworICAgICAgICAxLjAsICAgICAgICAgICAgICAxLjU4NDk2MjUw
MDcyMTE2LCAyLjAsCisgICAgICAgIDIuMzIxOTI4MDk0ODg3MzYsIDIuNTg0OTYyNTAwNzIxLCAg
IDIuNTg0OTYyNTAwNzIxMTYsCisgICAgICAgIDIuODA3MzU0OTIyMDU3NiwgIDMuMCwgICAgICAg
ICAgICAgIDMuMTY5OTI1MDAxNDQyMzEsCisgICAgICAgIDMuMzIxOTI4MDk0ODg3MzYsIDMuNDU5
NDMxNjE4NjM3MywgIDMuNTg0OTYyNTAwNzIxMTYsCisgICAgICAgIDMuNzAwNDM5NzE4MTQxMDks
IDMuODA3MzU0OTIyMDU3NiwgIDMuOTA2ODkwNTk1NjA4NTIsCisgICAgICAgIDQuMCwgICAgICAg
ICAgICAgIDQuMDg3NDYyODQxMjUwMzQsIDQuMTY5OTI1MDAxNDQyMzEsCisgICAgICAgIDQuMjQ3
OTI3NTEzNDQzNTksIDQuMzIxOTI4MDk0ODg3MzYsIDQuMzkyMzE3NDIyNzc4NzYsCisgICAgICAg
IDQuNDU5NDMxNjE4NjM3MywgIDQuNTIzNTYxOTU2MDU3MDEsIDQuNTg0OTYyNTAwNzIxMTYsCisg
ICAgICAgIDQuNjQzODU2MTg5Nzc0NzIsIDQuNzAwNDM5NzE4MTQxMDksIDQuNzU0ODg3NTAyMTYz
NDcsCisgICAgICAgIDQuODA3MzU0OTIyMDU3NiwgIDQuODU3OTgwOTk1MTI3NTcsIDQuOTA2ODkw
NTk1NjA4NTIsCisgICAgICAgIDQuOTU0MTk2MzEwMzg2ODgsIDUuMCwgICAgICAgICAgICAgIDUu
MDQ0Mzk0MTE5MzU4NDUsCisgICAgICAgIDUuMDg3NDYyODQxMjUwMzQsIDUuMTI5MjgzMDE2OTQ0
OTcsIDUuMTY5OTI1MDAxNDQyMzEKKyAgICB9OworICAgIGxvbmcgYml0czsKKworICAgIGlmIChi
YXNlIDwgMiAmJiAzNiA8IGJhc2UpCisgICAgICByYl9idWcoImlsbGVnYWwgcmFkaXggJWQiLCBi
YXNlKTsKKworICAgIGlmIChGSVhOVU1fUCh4KSkgeworICAgICAgICBiaXRzID0gKFNJWkVPRl9M
T05HKkNIQVJfQklUIC0gMSkvMiArIDE7CisgICAgfQorICAgIGVsc2UgaWYgKEJJR1pFUk9QKHgp
KSB7CisgICAgICAgIHJldHVybiAwOworICAgIH0KKyAgICBlbHNlIHsKKyAgICAgICAgYml0cyA9
IEJJVFNQRVJESUcqUkJJR05VTSh4KS0+bGVuOworICAgIH0KKworICAgIHJldHVybiAobG9uZyko
Yml0cy8oMipsb2dfMltiYXNlIC0gMl0pICsgMSk7Cit9CisKK3N0YXRpYyBsb25nCitiaWcyc3Ry
X2thcmF0c3ViYV93aXRob3V0X3NpZ24oeCwgYmFzZSwgcHRyLCBuMSkKKyAgICBWQUxVRSB4Owor
ICAgIGludCBiYXNlOworICAgIGNoYXIqIHB0cjsKKyAgICBsb25nIG4xOworeworICAgIGxvbmcg
bGVuID0gMipuMTsKKyAgICBWQUxVRSBiLCBxcjsKKworICAgIGlmIChGSVhOVU1fUCh4KSkgewor
ICAgICAgICBWQUxVRSBzdHIgPSByYl9maXgyc3RyKHgsIGJhc2UpOworICAgICAgICBtZW1zZXQo
cHRyLCAnMCcsIGxlbiAtIFJTVFJJTkcoc3RyKS0+bGVuKTsKKyAgICAgICAgTUVNQ1BZKHB0ciAr
IGxlbiAtIFJTVFJJTkcoc3RyKS0+bGVuLCBSU1RSSU5HKHN0ciktPnB0ciwKKyAgICAgICAgICAg
ICAgIGNoYXIsIFJTVFJJTkcoc3RyKS0+bGVuKTsKKyAgICAgICAgcmV0dXJuOworICAgIH0KKyAg
ICBpZiAoQklHWkVST1AoeCkpIHsKKyAgICAgICAgbWVtc2V0KHB0ciwgJzAnLCBsZW4pOworICAg
ICAgICByZXR1cm47CisgICAgfQorCisgICAgaWYgKG4xICUgMiA9PSAxKSArK24xOworICAgIGIg
PSBwb3dlcl9jYWNoZV9nZXRfcG93ZXIoYmFzZSwgbjEpOworICAgIHFyID0gcmJfYmlnX2Rpdm1v
ZCh4LCBiKTsKKyAgICBiaWcyc3RyX2thcmF0c3ViYV93aXRob3V0X3NpZ24oCisgICAgICAgIFJB
UlJBWShxciktPnB0clswXSwgYmFzZSwgcHRyLCAgICAgICAgICAgICAgKGxlbiAtIG4xKS8yKTsK
KyAgICBiaWcyc3RyX2thcmF0c3ViYV93aXRob3V0X3NpZ24oCisgICAgICAgIFJBUlJBWShxcikt
PnB0clsxXSwgYmFzZSwgcHRyICsgKGxlbiAtIG4xKSwgbjEvMik7Cit9CisKIFZBTFVFCityYl9i
aWcyc3RyMF9rYXJhdHN1YmEoeCwgYmFzZSwgdHJpbSkKKyAgICBWQUxVRSB4OworICAgIGludCBi
YXNlOworICAgIGludCB0cmltOworeworICAgIFZBTFVFIHNzLCB4eDsKKyAgICBsb25nIG4xOwor
CisgICAgaWYgKEZJWE5VTV9QKHgpKSB7CisgICAgICAgIHJldHVybiByYl9maXgyc3RyKHgsIGJh
c2UpOworICAgIH0KKyAgICBpZiAoQklHWkVST1AoeCkpIHsKKyAgICAgICAgcmV0dXJuIHJiX3N0
cl9uZXcyKCIwIik7CisgICAgfQorCisgICAgaWYgKGJhc2UgPCAyICYmIDM2IDwgYmFzZSkKKyAg
ICAgICAgcmJfcmFpc2UocmJfZUFyZ0Vycm9yLCAiaWxsZWdhbCByYWRpeCAlZCIsIGJhc2UpOwor
CisgICAgeHggPSByYl9iaWdfY2xvbmUoeCk7CisgICAgbjEgPSBiaWcyc3RyX2thcmF0c3ViYV9m
aW5kX24xKHh4LCBiYXNlKTsKKyAgICBzcyA9IHJiX3N0cl9uZXcoMCwgMipuMSArIDEpOyAvKiBw
bHVzIG9uZSBmb3Igc2lnbiAqLworICAgIFJTVFJJTkcoc3MpLT5wdHJbMF0gPSBSQklHTlVNKHh4
KS0+c2lnbiA/ICcrJyA6ICctJzsKKyAgICBSQklHTlVNKHh4KS0+c2lnbiA9IDE7CisKKyAgICBi
aWcyc3RyX2thcmF0c3ViYV93aXRob3V0X3NpZ24oCisgICAgICAgIHh4LCBiYXNlLCBSU1RSSU5H
KHNzKS0+cHRyICsgMSwgbjEpOworICAgIGlmICh0cmltKSB7CisgICAgICAgIGludCBpID0gMTsK
KyAgICAgICAgd2hpbGUgKFJTVFJJTkcoc3MpLT5wdHJbaV0gPT0gJzAnKSArK2k7CisgICAgICAg
IGlmIChSQklHTlVNKHgpLT5zaWduKSB7CisgICAgICAgICAgICBNRU1NT1ZFKFJTVFJJTkcoc3Mp
LT5wdHIsIFJTVFJJTkcoc3MpLT5wdHIgKyBpLAorICAgICAgICAgICAgICAgICAgICBjaGFyLCBS
U1RSSU5HKHNzKS0+bGVuIC0gaSk7IC8qIHBsdXMgb25lIGZvciAnXDAnICovCisgICAgICAgIH0K
KyAgICAgICAgZWxzZSB7CisgICAgICAgICAgICBNRU1NT1ZFKFJTVFJJTkcoc3MpLT5wdHIgKyAx
LCBSU1RSSU5HKHNzKS0+cHRyICsgaSwKKyAgICAgICAgICAgICAgICAgICAgY2hhciwgUlNUUklO
RyhzcyktPmxlbiAtIGkpOyAvKiBwbHVzIG9uZSBmb3IgJ1wwJyAqLworICAgICAgICB9CisgICAg
ICAgIFJTVFJJTkcoc3MpLT5sZW4gLT0gaSAtICFSQklHTlVNKHgpLT5zaWduOworICAgIH0KKyAg
ICBSU1RSSU5HKHNzKS0+cHRyW1JTVFJJTkcoc3MpLT5sZW5dID0gJ1wwJzsKKworICAgIHJldHVy
biBzczsKK30KKworc3RhdGljIGlubGluZSBpbnQKK2JpZzJzdHJfbm9ybWFsKFZBTFVFIHgsIGxv
bmcgaiwgaW50IGJhc2UsIGludCBoYmFzZSwgY2hhciAqcywgaW50IHRyaW0pCit7CisgICAgbG9u
ZyBpID0gUkJJR05VTSh4KS0+bGVuOworICAgIEJESUdJVCAqZHMgPSBCRElHSVRTKHgpOworCisg
ICAgd2hpbGUgKGkgJiYgaiA+IDEpIHsKKyAgICAgICBsb25nIGsgPSBpOworICAgICAgIEJESUdJ
VF9EQkwgbnVtID0gMDsKKworICAgICAgIHdoaWxlIChrLS0pIHsKKyAgICAgICAgICAgbnVtID0g
QklHVVAobnVtKSArIGRzW2tdOworICAgICAgICAgICBkc1trXSA9IChCRElHSVQpKG51bSAvIGhi
YXNlKTsKKyAgICAgICAgICAgbnVtICU9IGhiYXNlOworICAgICAgIH0KKyAgICAgICBpZiAodHJp
bSAmJiBkc1tpLTFdID09IDApIGktLTsKKyAgICAgICBrID0gU0laRU9GX0JESUdJVFM7CisgICAg
ICAgd2hpbGUgKGstLSkgeworICAgICAgICAgICBzWy0tal0gPSBydWJ5X2RpZ2l0bWFwW251bSAl
IGJhc2VdOworICAgICAgICAgICBudW0gLz0gYmFzZTsKKyAgICAgICAgICAgaWYgKCF0cmltICYm
IGogPCAxKSBicmVhazsKKyAgICAgICAgICAgaWYgKHRyaW0gJiYgaSA9PSAwICYmIG51bSA9PSAw
KSBicmVhazsKKyAgICAgICB9CisgICAgfQorICAgIHJldHVybiBqOworfQorCisjZGVmaW5lIEtB
UkFUU1VCQV9ESUdJVFMgMTAyNAorc3RhdGljIFZBTFVFIGJpZzJzdHJfdGFibGVbMzddWzE2XTsK
Kworc3RhdGljIFZBTFVFIGJpZ3NxcihWQUxVRSB4KTsKK3N0YXRpYyB2b2lkIGJpZ2Rpdm1vZChW
QUxVRSB4LCBWQUxVRSB5LCBWQUxVRSAqZGl2cCwgVkFMVUUgKm1vZHApOworCitzdGF0aWMgaW5s
aW5lIGludAorYmlnMnN0cl9rYXJhdHN1YmFfMzEzMTIoVkFMVUUgeCwgaW50IG4sIGludCBiYXNl
LCBpbnQgaGJhc2UsIGNoYXIgKnMsIGludCB0cmltKQoreworICAgIGxvbmcgaSwgaiwgaywgYnNf
bGVuLCBzaWduID0gUkJJR05VTSh4KS0+c2lnbjsKKyAgICB2b2xhdGlsZSBWQUxVRSB0ID0gYmln
MnN0cl90YWJsZVtiYXNlXVswXSwgdDI7CisgICAgVkFMVUUgKmFzLCAqYnMsIHEsIHI7CisKKyAg
ICBqID0gUkJJR05VTSh0KS0+bGVuOworICAgIGZvciAoaT0wOyBqIDw9IFJCSUdOVU0oeCktPmxl
bjsgaSsrKSBqICo9IDI7CisKKyAgICBhcyA9IEFMTE9DQV9OKFZBTFVFLCBpKTsKKworICAgIGZv
ciAoaT0wLGo9MTsgOyBpKyssaio9MikgeworICAgICAgIGFzW2ldID0gdDsKKyAgICAgICBpZihi
aWcyc3RyX3RhYmxlW2Jhc2VdW2kgKyAxXSkgeworICAgICAgICAgICB0MiA9IGJpZzJzdHJfdGFi
bGVbYmFzZV1baSArIDFdOworICAgICAgIH0KKyAgICAgICBlbHNlIHsKKyAgICAgICAgICAgdDIg
PSBiaWdzcXIodCk7CisgICAgICAgICAgIGlmKGkgKyAxIDwgMTYpIHsKKyAgICAgICAgICAgICAg
IGJpZzJzdHJfdGFibGVbYmFzZV1baSArIDFdID0gdDI7CisgICAgICAgICAgICAgICByYl9nbG9i
YWxfdmFyaWFibGUoJmJpZzJzdHJfdGFibGVbYmFzZV1baSArIDFdKTsKKyAgICAgICAgICAgfQor
ICAgICAgIH0KKyAgICAgICBpZihSQklHTlVNKHgpLT5sZW4gPCBSQklHTlVNKHQyKS0+bGVuKSBi
cmVhazsKKyAgICAgICB0ID0gdDI7CisgICAgfQorCisgICAgYnNfbGVuID0gaiAqIDI7CisgICAg
YnMgPSBBTExPQ0FfTihWQUxVRSwgYnNfbGVuKTsKKyAgICBic1swXSA9IHg7CisgICAgUkJJR05V
TSh4KS0+c2lnbiA9IDE7CisgICAgZm9yICg7IGo+MDsgaS0tLCBqLz0yKSB7CisgICAgICAgZm9y
IChrPTA7IGs8YnNfbGVuOyBrKz1qKjIpIHsKKyAgICAgICAgICAgYmlnZGl2bW9kKGJzW2tdLCBh
c1tpXSwgJnEsICZyKTsKKyAgICAgICAgICAgYnNba10gPSBxOworICAgICAgICAgICBic1trICsg
al0gPSByOworICAgICAgIH0KKyAgICB9CisgICAgUkJJR05VTSh4KS0+c2lnbiA9IHNpZ247CisK
KyAgICBqID0gMDsKKyAgICB3aGlsZShSQklHTlVNKGJzW2pdKS0+bGVuID09IDEgJiYgQkRJR0lU
Uyhic1tqXSlbMF0gPT0gMCkgaisrOworICAgIGZvciAoaT1ic19sZW4tMTsgaT5qOyBpLS0pIHsK
KyAgICAgICBrID0gYmlnMnN0cl9ub3JtYWwoCisgICAgICAgICAgIGJzW2ldLCBLQVJBVFNVQkFf
RElHSVRTLCBiYXNlLCBoYmFzZSwKKyAgICAgICAgICAgcyArIG4gLSBLQVJBVFNVQkFfRElHSVRT
LCBRZmFsc2UpOworICAgICAgIG4gLT0gS0FSQVRTVUJBX0RJR0lUUyAtIGs7CisgICAgfQorICAg
IG4gPSBiaWcyc3RyX25vcm1hbChic1tqXSwgbiwgYmFzZSwgaGJhc2UsIHMsIHRyaW0pOworCisg
ICAgcmV0dXJuIG47Cit9CisKK1ZBTFVFCityYl9iaWcyc3RyMF8zMTMxMihWQUxVRSB4LCBpbnQg
YmFzZSwgaW50IHRyaW0pCit7CisgICAgdm9sYXRpbGUgVkFMVUUgdDsKKyAgICBsb25nIGksIGos
IGhiYXNlOworICAgIFZBTFVFIHNzOworICAgIGNoYXIgKnM7CisKKyAgICBpZiAoRklYTlVNX1Ao
eCkpIHsKKwlyZXR1cm4gcmJfZml4MnN0cih4LCBiYXNlKTsKKyAgICB9CisgICAgaSA9IFJCSUdO
VU0oeCktPmxlbjsKKyAgICBpZiAoQklHWkVST1AoeCkpIHsKKwlyZXR1cm4gcmJfc3RyX25ldzIo
IjAiKTsKKyAgICB9CisgICAgaiA9IFNJWkVPRl9CRElHSVRTKkNIQVJfQklUKmk7CisgICAgc3dp
dGNoIChiYXNlKSB7CisgICAgICBjYXNlIDI6IGJyZWFrOworICAgICAgY2FzZSAzOgorCWogPSBq
ICogNTNMIC8gODQgKyAxOworCWJyZWFrOworICAgICAgY2FzZSA0OiBjYXNlIDU6IGNhc2UgNjog
Y2FzZSA3OgorCWogPSAoaiArIDEpIC8gMjsKKwlicmVhazsKKyAgICAgIGNhc2UgODogY2FzZSA5
OgorCWogPSAoaiArIDIpIC8gMzsKKwlicmVhazsKKyAgICAgIGNhc2UgMTA6IGNhc2UgMTE6IGNh
c2UgMTI6IGNhc2UgMTM6IGNhc2UgMTQ6IGNhc2UgMTU6CisJaiA9IGogKiAyOEwgLyA5MyArIDE7
CisJYnJlYWs7CisgICAgICBjYXNlIDE2OiBjYXNlIDE3OiBjYXNlIDE4OiBjYXNlIDE5OiBjYXNl
IDIwOiBjYXNlIDIxOgorICAgICAgY2FzZSAyMjogY2FzZSAyMzogY2FzZSAyNDogY2FzZSAyNTog
Y2FzZSAyNjogY2FzZSAyNzoKKyAgICAgIGNhc2UgMjg6IGNhc2UgMjk6IGNhc2UgMzA6IGNhc2Ug
MzE6CisJaiA9IChqICsgMykgLyA0OworCWJyZWFrOworICAgICAgY2FzZSAzMjogY2FzZSAzMzog
Y2FzZSAzNDogY2FzZSAzNTogY2FzZSAzNjoKKwlqID0gKGogKyA0KSAvIDU7CisJYnJlYWs7Cisg
ICAgICBkZWZhdWx0OgorCXJiX3JhaXNlKHJiX2VBcmdFcnJvciwgImlsbGVnYWwgcmFkaXggJWQi
LCBiYXNlKTsKKwlicmVhazsKKyAgICB9CisgICAgaisrOwkJCS8qIHNwYWNlIGZvciBzaWduICov
CisKKyAgICBoYmFzZSA9IGJhc2UgKiBiYXNlOworI2lmIFNJWkVPRl9CRElHSVRTID4gMgorICAg
IGhiYXNlICo9IGhiYXNlOworI2VuZGlmCisKKyAgICB0ID0gcmJfYmlnX2Nsb25lKHgpOworICAg
IHNzID0gcmJfc3RyX25ldygwLCBqKzEpOworICAgIHMgPSBSU1RSSU5HKHNzKS0+cHRyOworCisg
ICAgc1swXSA9IFJCSUdOVU0oeCktPnNpZ24gPyAnKycgOiAnLSc7CisgICAgaWYgKFJCSUdOVU0o
eCktPmxlbiA+IFJCSUdOVU0oYmlnMnN0cl90YWJsZVtiYXNlXVswXSktPmxlbiAqIDQpIHsKKyAg
ICAgICBqID0gYmlnMnN0cl9rYXJhdHN1YmFfMzEzMTIodCwgaiwgYmFzZSwgaGJhc2UsIHMsIHRy
aW0pOworICAgIH0KKyAgICBlbHNlIHsKKyAgICAgICBqID0gYmlnMnN0cl9ub3JtYWwodCwgaiwg
YmFzZSwgaGJhc2UsIHMsIHRyaW0pOworICAgIH0KKyAgICBpZiAodHJpbSkge3doaWxlIChzW2pd
ID09ICcwJykgaisrO30KKyAgICBpID0gUlNUUklORyhzcyktPmxlbiAtIGo7CisgICAgaWYgKFJC
SUdOVU0oeCktPnNpZ24pIHsKKwltZW1tb3ZlKHMsIHMraiwgaSk7CisJUlNUUklORyhzcyktPmxl
biA9IGktMTsKKyAgICB9CisgICAgZWxzZSB7CisJbWVtbW92ZShzKzEsIHMraiwgaSk7CisJUlNU
UklORyhzcyktPmxlbiA9IGk7CisgICAgfQorICAgIHNbUlNUUklORyhzcyktPmxlbl0gPSAnXDAn
OworCisgICAgcmV0dXJuIHNzOworfQorCitzdGF0aWMgdm9pZAoraW5pdF9iaWcyc3RyX3RhYmxl
KHZvaWQpCit7CisgICAgaW50IGksIGo7CisgICAgVkFMVUUgdjsKKworICAgIGZvciAoaT0wOyBp
PDM3OyBpKyspIHsKKyAgICAgICB2ID0gcmJfYmlnX3BvdyhyYl9pbnQyYmlnKGkpLCBJTlQyRklY
KEtBUkFUU1VCQV9ESUdJVFMpKTsKKyAgICAgICBiaWcyc3RyX3RhYmxlW2ldWzBdID0gdjsKKyAg
ICAgICByYl9nbG9iYWxfdmFyaWFibGUoJmJpZzJzdHJfdGFibGVbaV1bMF0pOworICAgICAgIGZv
ciAoaj0xOyBqPDE2OyBqKyspIHsKKyAgICAgICAgICAgYmlnMnN0cl90YWJsZVtpXVtqXSA9IFFm
YWxzZTsKKyAgICAgICB9CisgICAgfQorfQorCitWQUxVRQogcmJfYmlnMnN0cihWQUxVRSB4LCBp
bnQgYmFzZSkKIHsKICAgICByZXR1cm4gcmJfYmlnMnN0cjAoeCwgYmFzZSwgUXRydWUpOwogfQog
CitWQUxVRQorcmJfYmlnMnN0cl9rYXJhdHN1YmEoVkFMVUUgeCwgaW50IGJhc2UpCit7CisgICAg
cmV0dXJuIHJiX2JpZzJzdHIwX2thcmF0c3ViYSh4LCBiYXNlLCBRdHJ1ZSk7Cit9CisKK1ZBTFVF
CityYl9iaWcyc3RyXzMxMzEyKFZBTFVFIHgsIGludCBiYXNlKQoreworICAgIHJldHVybiByYl9i
aWcyc3RyMF8zMTMxMih4LCBiYXNlLCBRdHJ1ZSk7Cit9CisKIC8qCiAgKiAgY2FsbC1zZXE6CiAg
KiAgICAgYmlnLnRvX3MoYmFzZT0xMCkgICA9PiAgc3RyaW5nCkBAIC03NDgsNyArMTIwNSw3IEBA
CiAgKi8KIAogc3RhdGljIFZBTFVFCi1yYl9iaWdfdG9fcyhhcmdjLCBhcmd2LCB4KQorcmJfYmln
X3RvX3Nfb3JpZyhhcmdjLCBhcmd2LCB4KQogICAgIGludCBhcmdjOwogICAgIFZBTFVFICphcmd2
OwogICAgIFZBTFVFIHg7CkBAIC03NjIsNiArMTIxOSwzNiBAQAogICAgIHJldHVybiByYl9iaWcy
c3RyKHgsIGJhc2UpOwogfQogCitzdGF0aWMgVkFMVUUKK3JiX2JpZ190b19zKGFyZ2MsIGFyZ3Ys
IHgpCisgICAgaW50IGFyZ2M7CisgICAgVkFMVUUgKmFyZ3Y7CisgICAgVkFMVUUgeDsKK3sKKyAg
ICBWQUxVRSBiOworICAgIGludCBiYXNlOworCisgICAgcmJfc2Nhbl9hcmdzKGFyZ2MsIGFyZ3Ys
ICIwMSIsICZiKTsKKyAgICBpZiAoYXJnYyA9PSAwKSBiYXNlID0gMTA7CisgICAgZWxzZSBiYXNl
ID0gTlVNMklOVChiKTsKKyAgICByZXR1cm4gcmJfYmlnMnN0cl9rYXJhdHN1YmEoeCwgYmFzZSk7
Cit9CisKK3N0YXRpYyBWQUxVRQorcmJfYmlnX3RvX3NfMzEzMTIoYXJnYywgYXJndiwgeCkKKyAg
ICBpbnQgYXJnYzsKKyAgICBWQUxVRSAqYXJndjsKKyAgICBWQUxVRSB4OworeworICAgIFZBTFVF
IGI7CisgICAgaW50IGJhc2U7CisKKyAgICByYl9zY2FuX2FyZ3MoYXJnYywgYXJndiwgIjAxIiwg
JmIpOworICAgIGlmIChhcmdjID09IDApIGJhc2UgPSAxMDsKKyAgICBlbHNlIGJhc2UgPSBOVU0y
SU5UKGIpOworICAgIHJldHVybiByYl9iaWcyc3RyXzMxMzEyKHgsIGJhc2UpOworfQorCiBzdGF0
aWMgdW5zaWduZWQgbG9uZwogYmlnMnVsb25nKHgsIHR5cGUpCiAgICAgVkFMVUUgeDsKQEAgLTIz
MTQsNiArMjgwMSw4IEBACiB7CiAgICAgcmJfY0JpZ251bSA9IHJiX2RlZmluZV9jbGFzcygiQmln
bnVtIiwgcmJfY0ludGVnZXIpOwogCisgICAgcmJfZGVmaW5lX21ldGhvZChyYl9jQmlnbnVtLCAi
dG9fc19vcmlnIiwgcmJfYmlnX3RvX3Nfb3JpZywgLTEpOworICAgIHJiX2RlZmluZV9tZXRob2Qo
cmJfY0JpZ251bSwgInRvX3NfMzEzMTIiLCByYl9iaWdfdG9fc18zMTMxMiwgLTEpOwogICAgIHJi
X2RlZmluZV9tZXRob2QocmJfY0JpZ251bSwgInRvX3MiLCByYl9iaWdfdG9fcywgLTEpOwogICAg
IHJiX2RlZmluZV9tZXRob2QocmJfY0JpZ251bSwgImNvZXJjZSIsIHJiX2JpZ19jb2VyY2UsIDEp
OwogICAgIHJiX2RlZmluZV9tZXRob2QocmJfY0JpZ251bSwgIi1AIiwgcmJfYmlnX3VtaW51cywg
MCk7CkBAIC0yMzQ0LDQgKzI4MzMsNiBAQAogICAgIHJiX2RlZmluZV9tZXRob2QocmJfY0JpZ251
bSwgInRvX2YiLCByYl9iaWdfdG9fZiwgMCk7CiAgICAgcmJfZGVmaW5lX21ldGhvZChyYl9jQmln
bnVtLCAiYWJzIiwgcmJfYmlnX2FicywgMCk7CiAgICAgcmJfZGVmaW5lX21ldGhvZChyYl9jQmln
bnVtLCAic2l6ZSIsIHJiX2JpZ19zaXplLCAwKTsKKworICAgIGluaXRfYmlnMnN0cl90YWJsZSgp
OwogfQo------art_68138_11322615.1185961038442
Content-Type: application/octet-stream; name=karatsuba.rb
Content-Transfer-Encoding: base64
X-Attachment-Id: f_f4tmke1h
Content-Disposition: attachment; filename="karatsuba.rb"

cmVxdWlyZSAnYmVuY2htYXJrJwoKJHZhbHVlcyA9ICgxLi4xMDApLnRvX2EuY29sbGVjdHsgcmFu
ZCgxMCoqMTAyNCAtIDEpIH0KCmRlZiBtYWluCiAgJHZhbHVlcy5lYWNoe3x2fCAoMi4uMzYpLmVh
Y2h7fGJ8IHlpZWxkKHYsIGIpIH19CmVuZAoKQmVuY2htYXJrLmJtYm0gZG8gfHh8CiAgeC5yZXBv
cnQoJ29yaWdpbmFsJykgZG8KICAgIG1haW4ge3x2LCBifCB2LnRvX3Nfb3JpZyhiKSB9CiAgZW5k
CiAgeC5yZXBvcnQoJ3J1YnktZGV2OjMxMzEyJykgZG8KICAgIG1haW4ge3x2LCBifCB2LnRvX3Nf
MzEzMTIoYikgfQogIGVuZAogIHgucmVwb3J0KCdydWJ5LWRldjozMTMyMycpIGRvCiAgICBtYWlu
IHt8diwgYnwgdi50b19zKGIpIH0KICBlbmQKZW5kCg------art_68138_11322615.1185961038442--