2011^2011 の下 3 桁を計算する

Twitter / 2011の2011乗の下三桁は? ... という投げかけをされたので、awk で計算してみました。 2011^2011 は大きすぎる桁数になることが予想されますし、Google 先生に聞いてみても答えが返って来ません

こういう場合は、まともに 2011^2011 を計算しても埒があかないので、以下のようにして計算します。

  • 下 3 桁なので、1000 以上の桁は無視しても問題ない。
  • 毎回下 3 桁を取って、その値で計算すれば良い。

ということになります。

これをスクリプトに直すと以下のようになります。

#! /usr/local/bin/nawk -f
# 2011_2011.awk
# 2011 ^ 2011 の下 3 桁を計算する
# usage: nawk -f 2011_2011.awk

BEGIN {
    var_a = ARGV[1] ? ARGV[1] : 2011;
    var_b = ARGV[2] ? ARGV[2] : 2011;

    var = 1;
    for (i = 1; i <= var_b; i++) {
        var = var * var_a;

        if (var >= 1000) {
            var %= 1000;
        }
    }

    if (var >= 1000) {
        print substr(var, length(var) - 2);
    } else {
        print var;
    }
}

では実行してみましょう。

と、その前にチェックの意味を込めて、2^32 を計算してみます。 2^32 は 4294967296 ですから、"296" となれば良いわけです。

$ nawk -f 2011_2011.awk 2 32
296

確かに計算できているようです。 では、2011^2011 を計算させます。

$ nawk -f 2011_2011.awk
611

というわけで "611" となります。

MPFR で計算してみる

xgawk には MPFR で任意精度で計算することができますので、MPFR を用いて真の解を求めてみます。

#! /usr/local/bin/xgawk -f
# 2011_2011_mpfr.awk
# 2011^2011 を求める
# usage: xgawk -f 2011_2011_mpfr.awk

@load mpfr

BEGIN {
    MPFR_BASE = 10;
    MPFR_PRECISION = 100000;

    print mpfr_pow(2011, 2011);
}

MPFR_PRECISION はいい加減な値です。

$ xgawk -f 2011_2011_mpfr.awk
1.451021909475683544397180425718887307279401554566608193938885574952589688465448
12426169347814722752430518886638741552069339031541981202311916289923018171350482
00098980176752739362987878664059532850107984545109970319612751146817229127042379
60309072708675761902472598144972073950338446367528184459770140534577084346500097
50704150896133322111721826236902705749993499693170780163138070254224811605468435
37968347603649315792489605777834323805460413034900278406748673158431279064662352
84795881869170825339879296015278533803535473731865112245532821378535548840039821
08878541423893709897582346401305062606758740477900258424408854677110371391742976
90267704869910896371907830244052230101607377315283106967320104784230128581678356
73365197272130326192701047654154903482123826210114545446074423558150330080473178
13132974497794277551854875150450904316082159795426428560192805836889252178164286
02650546812760023727355869719417344689058172044429829389003403686273002229187524
53724763491808654775245020322454671225114906459215597334262609062071494416567405
50169534734753412948873085956290970074724104315321219061080889575722820263107147
83107497418246512593517465039367233934654168224981093602413155513695182786967364
98058156547811906510357598482626525586232318167665341696768980223321408834973094
73319945996951819202681301612994059957825656298004680004409412881700694505808045
52732721486676013741611681944793619673798886562111764156394552401369401761640290
95723775711552377656449652439816763274342488000219487895990613402287658400015104
00261863649339227294454160630338870217480967564075022738740731393118978112670954
00718994554595717706599595291309840369068932559458206582023161200627335416474012
48881501617233033726058734924689063771615104438699161157395552391659874970997571
66226797487978421471587266877597968252313755558894230509045977796706695423923250
07347450602190569159391485653708628977505864044630073984857552417164766694174007
44623744229452680144168801583667983496090896506379549878791152504336568010515725
15347330125027079495861299220409817342373155703223983096057323257418694397383262
10465859465676096641936226281199767693354773928874388433433619697484325389804752
32556961743812243634077681175989284096633271300445219402829316678659432331698858
85405483375227711480904645302948315964575858350245660183095183479150857878822467
67059251983592015486463678669596438592049008314992556342253597099170817261519193
11095831558257957961259089797337507767532292572216730565633780231828836674696785
42164859137988014853786247601274197395160668050636152981864431557148478142271683
97129307200659528151215347298459700123443326572253651823725673379629800162640998
64639599418448238860098376759736237326451609886415902627996372694974242542896538
99744742062885390255230087795051011794031835303999236071287116497494179528568341
46668247431995446772474542494576842294761706230522253316484353430938708094756603
91365137325153730937201605626971174859709953781624533441271872267365890764875015
79799362166114907369925383744776008497056240131810917701286764850695810540488746
85904083050140375491505461484946125125451337979611764072862286605372712106006826
37041183689833030142963445234979450141224877750576061434449084978356901450437150
54617703284950593776072022648786135714394642765206754747251980215646210516001195
05652211213532992622202360790091815754312912492831778390646659560040690459901136
05644916213257935476029191119382062542243135224414240937267225598199855473072140
22368960680172913990026085246594947331564585604684542869727441170439803269101746
76178911707063103605254915304021061697977849611533820629613317114846889476696181
90801574469177368458142172176611627813640164250441326768829655306177364088948707
99410795233192372504973737987347001494329939204605715282958081780653138824352084
70362653529114065796062572729665041898351559680918279839147245393054880997783582
68021859392559460762450009037966252276488487947249722873916867879221789591859732
30428899029231834605340058120142165013636459766715842315746336532378459995605725
85757923903205441980717507754148387516844031980736798705250383427695858961777809
55180405833925104438169296727351983383608749934744560129474380621048277175594661
53641380257766995922143285534653848629088291728714430717016272606379483554065676
56586196261571857797351973872753455115341974403208689931822888840618095837856835
83639422096416737369318204333782126917097252462293279181188891279951682343001468
47358387618577767795899742268428050745322430355889347781543249335090235350935066
16335938383230021260887567310329094908408756605538385397234006271831785200944648
39725451311083387815321390941485515614740658019954492631402212956234684081129591
73483747415543512759660994975395837724385597762544134551343925182725776505753365
68062777244668565133254732650588948151145265262483174452321786600631078667589115
40089568548144389666262459642197207263417999812852155132852440914703918115519525
40790541253148337076932534783322062432851731087874142611086003634767286279221804
52603493453425271127307705393556306352032635208921648129782670552618600278257768
43697762740098429021903486888565523342586763132945394612423419294544429206239006
41392875010700236024746912177911232103034760349158780414689742603817408281229800
62146438949536001669362613825058563639940617077400121977921846377164005316723309
24173123542735220652856153220579684363168557988955418061507131993909263408075648
26689881523985617240498452368824088233687407242938556629387148480763867452377081
53888259668172851739419865414324087115957051254617425968124768603533017735321784
07900185045732521882998791148313104743271064635734108972672626890830196380763838
40001537128175601550060917981476665493217361020304302755728503046271267163227399
32121477170815946271923065311867369532267887377248219996879400509573450413921221
20545608881952123051066778156347610620696319019992690389564415624102432781473563
96657401259516199665983393260802422542712133409039630497445225830416930898775976
32573932526178555920706300304747852396865431378278487499260694027311870364355410
32866711274999846743937389600306486038139095680270785115264258055180848450690856
97325955121651065878017367716191185187773035487673715258235644785945709431504229
43471819366503424051758233597273684831997197296226005537112653183943361132860240
38866924855720186733736248067509894142078690333008005297597299467844450388827758
93207110010955892178830757282635581829807619330231364781906859674738486144105895
86742282218929572405880168032768662254225628649076169101399729794796356267028950
51711199433922118432858245465011670971936261700871035205481858499674105039566320
25614031653533999208248248136720143684237833279338535242957356980776290635313270
12611000000000000000000000000000000000000000000000000000000000000000000000000000
<snip>
0000000000000000000000000E6643

おお、確かに最後は "611" でした。

修正 (2011-03-02)

Twitter / @eban: @hi_saito substrを使わないで、素直に ... の指摘を受け、修正しました。

tag_nawk.png tag_nawk.png tag_nawk.png tag_nawk.png