偶然,「大きな数の先頭と末尾」の後に類似問題が出たようだ。
「大きな数の先頭と末尾」では本当は先頭1桁だけが必要なのだが,4 桁求めるようにしていた。
更に,べき乗される数もそんなに大きいものは考えていなかった。
なので,仕様を満たすために,以下のプログラムを書くことになった。
問題:a, x を符号なし 32 bit 整数として,べき乗計算 a^x の下 8 桁のみを高速に計算するプログラム
mul = function(m, n) { # 8 桁以下の,m, n の掛け算を行い,下 8 桁を返す
dec = function(k) { # 8 桁の整数を一桁ずつ配列に落とす
a = numeric(8)
for (i in 1:8) {
a[i] = k %% 10
k = k %/% 10
}
return(a)
}
am = dec(m)
an = dec(n)
ans = numeric(17) # 掛け算の答が入る
for (i in seq_along(am)) {
for (j in seq_along(an)) {
ans[i+j-1] = ans[i+j-1]+am[i]*an[j]
}
}
carry = 0 # 繰り上がり
for (i in 1:8) { # 繰り上がり処理
ans[i] = ans[i]+carry
carry = ans[i] %/% 10
ans[i] = ans[i] %% 10
}
return(sum(ans[1:8] * 10^(0:7))) # 答の下 8 桁を返す
}
func = function(m, n) {
m = m %% 1e8
ans = 1
repeat {
if (n %% 2 == 1) {
ans = mul(ans, m) # もとの n の ビットが立っているところを掛け算
}
n = n %/% 2 # もとの n のビットが立っているところを探すため半分ずつにしていく
if (n == 0) return(ans)
m = mul(m, m) # 被巾数は倍々にしていく
}
ans
}
func(3863080011, 2613515386) # 254361
func(21321331, 1234653876) # 81
func(521340345, 1396720193) # 84765625
func(1843165372, 2835135645) # 79967232
func(417934669, 3961963772) # 11298161
func(7564929, 1434531250) # 1
func(3713420107, 616334320) # 57768001
func(57564748, 243756997) # 3328
func(2249407224, 3483719867) # 32397824
func(444893257, 3572472608) # 25452801
以上全てを計算するのに,小生のポンコツ・マシンは 0.126 秒を要した。
※コメント投稿者のブログIDはブログ作成者のみに通知されます