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

むらけんです.

まつもとさんの日記で話題になっていた Bignum#to_s の
Karatsuba 基数変換による高速 C で実装してみました.
ベキ数のキャッシュアルゴリズムが少し変な気がしますが,パッチを添付します.

一応,添付した test_karatsuba.rb でテストもして,きちんと動いているようです.

速度的には,べき乗の演算時間が含まれていますえ 丑以下になりました.
$ time ./ruby -e 'p((65536**65536).to_s_orig(10))' > r1.txt

real    4m6.110s
user    1m1.368s
sys     0m0.016s
$ time ./ruby -e 'p((65536**65536).to_s(10))' > r2.txt

real    0m41.312s
user    0m11.421s
sys     0m0.012s

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

------art_66690_7685292.1185949293756
Content-Type: application/octet-stream; name=bignum_to_s_karatsuba.patch
Content-Transfer-Encoding: base64
X-Attachment-Id: f_f4tfezvf
Content-Disposition: attachment; filename="bignum_to_s_karatsuba.patch"

SW5kZXg6IGJpZ251bS5jCj09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09PT09
PT09PT09PT09PT09PT09PT09PT09PT09PT0KLS0tIGJpZ251bS5jCShyZXZpc2lvbiAxMjg1OSkK
KysrIGJpZ251bS5jCSh3b3JraW5nIGNvcHkpCkBAIC0xOSw2ICsxOSw4IEBACiAjaW5jbHVkZSA8
aWVlZWZwLmg+CiAjZW5kaWYKIAorI2luY2x1ZGUgPHN0Lmg+CisKIFZBTFVFIHJiX2NCaWdudW07
CiAKICNpZiBkZWZpbmVkIF9fTUlOR1czMl9fCkBAIC03MjcsMTIgKzcyOSwyODMgQEAKICAgICBy
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
biBzczsKK30KKworVkFMVUUKIHJiX2JpZzJzdHIoVkFMVUUgeCwgaW50IGJhc2UpCiB7CiAgICAg
cmV0dXJuIHJiX2JpZzJzdHIwKHgsIGJhc2UsIFF0cnVlKTsKIH0KIAorVkFMVUUKK3JiX2JpZzJz
dHJfa2FyYXRzdWJhKFZBTFVFIHgsIFZBTFVFIGJhc2UpCit7CisgICAgcmV0dXJuIHJiX2JpZzJz
dHIwX2thcmF0c3ViYSh4LCBGSVgySU5UKGJhc2UpLCBRdHJ1ZSk7Cit9CisKIC8qCiAgKiAgY2Fs
bC1zZXE6CiAgKiAgICAgYmlnLnRvX3MoYmFzZT0xMCkgICA9PiAgc3RyaW5nCkBAIC03NDgsNyAr
MTAyMSw3IEBACiAgKi8KIAogc3RhdGljIFZBTFVFCi1yYl9iaWdfdG9fcyhhcmdjLCBhcmd2LCB4
KQorcmJfYmlnX3RvX3Nfb3JpZyhhcmdjLCBhcmd2LCB4KQogICAgIGludCBhcmdjOwogICAgIFZB
TFVFICphcmd2OwogICAgIFZBTFVFIHg7CkBAIC03NjIsNiArMTAzNSwyMSBAQAogICAgIHJldHVy
biByYl9iaWcyc3RyKHgsIGJhc2UpOwogfQogCitzdGF0aWMgVkFMVUUKK3JiX2JpZ190b19zKGFy
Z2MsIGFyZ3YsIHgpCisgICAgaW50IGFyZ2M7CisgICAgVkFMVUUgKmFyZ3Y7CisgICAgVkFMVUUg
eDsKK3sKKyAgICBWQUxVRSBiOworICAgIGludCBiYXNlOworCisgICAgcmJfc2Nhbl9hcmdzKGFy
Z2MsIGFyZ3YsICIwMSIsICZiKTsKKyAgICBpZiAoYXJnYyA9PSAwKSBiYXNlID0gMTA7CisgICAg
ZWxzZSBiYXNlID0gTlVNMklOVChiKTsKKyAgICByZXR1cm4gcmJfYmlnMnN0cl9rYXJhdHN1YmEo
eCwgYmFzZSk7Cit9CisKIHN0YXRpYyB1bnNpZ25lZCBsb25nCiBiaWcydWxvbmcoeCwgdHlwZSkK
ICAgICBWQUxVRSB4OwpAQCAtMjMxNCw2ICsyNjAyLDcgQEAKIHsKICAgICByYl9jQmlnbnVtID0g
cmJfZGVmaW5lX2NsYXNzKCJCaWdudW0iLCByYl9jSW50ZWdlcik7CiAKKyAgICByYl9kZWZpbmVf
bWV0aG9kKHJiX2NCaWdudW0sICJ0b19zX29yaWciLCByYl9iaWdfdG9fc19vcmlnLCAtMSk7CiAg
ICAgcmJfZGVmaW5lX21ldGhvZChyYl9jQmlnbnVtLCAidG9fcyIsIHJiX2JpZ190b19zLCAtMSk7
CiAgICAgcmJfZGVmaW5lX21ldGhvZChyYl9jQmlnbnVtLCAiY29lcmNlIiwgcmJfYmlnX2NvZXJj
ZSwgMSk7CiAgICAgcmJfZGVmaW5lX21ldGhvZChyYl9jQmlnbnVtLCAiLUAiLCByYl9iaWdfdW1p
bnVzLCAwKTsK
------art_66690_7685292.1185949293756
Content-Type: application/octet-stream; name="test_karatsuba.rb"
Content-Transfer-Encoding: base64
Content-Disposition: attachment; filename="test_karatsuba.rb"
X-Attachment-Id: f_f4tfkwjf

cmVxdWlyZSAndGVzdC91bml0JwoKY2xhc3MgVGVzdEJpZ251bSA8IFRlc3Q6OlVuaXQ6OlRlc3RD
YXNlCiAgZGVmIHNldHVwCiAgICBzcmFuZChUaW1lLm5vdy50b19pKQogIGVuZAoKICBkZWYgdGVz
dF90b19zCiAgICAxMDAudGltZXMgZG8KICAgICAgeCA9IHJhbmQoMjw8MTAyNCAtIDEpCiAgICAg
ICgyLi4zNikudG9fYS5lYWNoIGRvIHxifAogICAgICAgIGFzc2VydF9lcXVhbCh4LnRvX3Nfb3Jp
ZyhiKSwgeC50b19zKGIpKQogICAgICBlbmQKICAgIGVuZAogIGVuZAoKICBkZWYgdGVzdF90b19z
ICAjIFtydWJ5LWNvcmU6MTA2ODZdCiAgICBhc3NlcnRfZXF1YWwoImZ2dnZ2dnZ2dnZ2dnYiICwx
ODQ0Njc0NDA3MzcwOTU1MTYxNS50b19zKDMyKSkKICAgIGFzc2VydF9lcXVhbCgiZzAwMDAwMDAw
MDAwMCIgLDE4NDQ2NzQ0MDczNzA5NTUxNjE2LnRvX3MoMzIpKQogICAgYXNzZXJ0X2VxdWFsKCIz
dzVlMTEyNjRzZ3NmIiAsMTg0NDY3NDQwNzM3MDk1NTE2MTUudG9fcygzNikpCiAgICBhc3NlcnRf
ZXF1YWwoIjN3NWUxMTI2NHNnc2ciICwxODQ0Njc0NDA3MzcwOTU1MTYxNi50b19zKDM2KSkKICAg
IGFzc2VydF9lcXVhbCgibmQwNzVpYjQ1azg2ZiIgLDE4NDQ2NzQ0MDczNzA5NTUxNjE1LnRvX3Mo
MzEpKQogICAgYXNzZXJ0X2VxdWFsKCJuZDA3NWliNDVrODZnIiAsMTg0NDY3NDQwNzM3MDk1NTE2
MTYudG9fcygzMSkpCiAgICBhc3NlcnRfZXF1YWwoIjE3Nzc3Nzc3Nzc3Nzc3Nzc3Nzc3NzciICwx
ODQ0Njc0NDA3MzcwOTU1MTYxNS50b19zKDgpKQogICAgYXNzZXJ0X2VxdWFsKCItMTc3Nzc3Nzc3
Nzc3Nzc3Nzc3Nzc3NyIgLC0xODQ0Njc0NDA3MzcwOTU1MTYxNS50b19zKDgpKQogIGVuZAplbmQK

------art_66690_7685292.1185949293756--