一度に扱える桁数を超える演算を行うために10を基数とした多倍長整数を用いて解決する
多倍長整数演算
本記事のタイトルにある「多倍長整数演算」とは何でしょう。
これは、普通にコードを書くと計算できないような大きな数を計算することをいいます。
多倍長整数の加減算
整数の桁ごとの値を、一の位から順に一次元配列に格納して管理する。
123=>[3,2,1]と一の位から格納される。
桁ごとの加算の後、繰り上がりを処理することで行う。
多倍長整数の加算の結果[15,13,11]となった場合、一の位から処理が始まる。
15は10*1+5になる。10の位の13に1を足し[5,14,11]になる。（繰り上がり）
多倍長整数の乗算
桁数が２の冪乗で、同じ桁数を持った正の整数同士の乗算について、カラツバ法を適用した計算を行うことを考える。桁数が２の冪乗で、同じ桁数を持った正の整数同士の乗算を扱う場合は、上位の桁を０で埋めて処理する。
桁数が２の冪乗であればカラツバ法をすぐ行う。２の冪乗でなければ同じ桁数を持った正の整数同士になるように０で埋めるてカラツバ法を行う。123 * 4 → 0123 * 0004
ツリー構造の構築
計算するためのツリー構造（以下、ツリーという）を作る処理とツリーを用いて演算をする処理からなる。
ツリーを作る処理とツリーを用いて演算する２つの処理がある。
ツリーは、多倍長整数の乗算の式を一つのノードとし、一つのノードは三個の子ノードを持つ。
M桁＊M桁の乗算の式について、乗算記号の左右にある値を、それぞれM/2桁ずつに分けてA ,B ,C, Dの４つの多倍長整数を作る。これらの整数を使って、A＊C、B＊D, (A+B)*(C+D)の３つの子ノードを作り、M/2桁＊M/2桁の乗算を行う層を作る。
多倍長整数の乗算の式を一つのノードとし、一つのノードは三個の子ノードになる。
３つの子それぞれA＊C、B＊D, (A+B)*(C+D)になる。
式で使われるA ,B ,C, Dは乗算記号の左右にある値を、それぞれM/2桁ずつ分けた値になる。
1234 * 5678 → A:12 ,B:34 ,C:56 , D:78になる
子ノード３つは12 * 56,34 * 78,(12+34) * (56*78)となる
ツリーを用いた演算
ツリーの最下層のノードは、整数の乗算だけで計算できる。最下層以外の層は、子ノードの計算結果を使って、次の式で計算できることがわかっている。ここで、α、β、γはそれぞれ子ノード①、２、③の乗算の計算結果を、Kは対象のノードの桁数を表す。
α * 10^k + (γ - α - β) * 10^(k/2) + β
左から順のノードの計算結果をそれぞれα、β、γに代入して計算することで目的の計算結果が求めることができる。
与えられた２つの多倍長整数からツリーを構築するプログラム
layer_top[1] ← 1 # 各層左端ノードのelements配列の添字を格納
for (iを1からt_depth - 1まで1ずつ増やす) # すでに根の添字が格納されているため-1する
layer_top[i + 1] ← layer_top[i] + <ウ> # ツリーの左端のノード番号を格納
endfor
elements[1] ← new_elem(val1.N, val1, val2)
for (dpを1からt_depth - 1まで1ずつ増やす) #深さごとに縦方向に処理
for (iを1からpow(3, dp - 1)まで1ずつ増やす) #
pe ← elements[layer_top[dp] + (i - 1)] # peはツリーのノードの計算式（要素）が代入される
cn ← pe.N / 2 # ツリーの計算式の２桁に分類する処理
tidx ← layer_top[dp + 1] + <エ> # ノードの子の左端のノード
elements[tidx] ← new_elem(cn, left(<オ>, cn), left(<カ>, cn)) # 以下３つの子ノードを生成
elements[tidx + 1] ← new_elem(cn, right(<オ>, cn), right(<カ>, cn))
elements[tidx + 2] ← new_elem(cn, lradd(<オ>, cn), lradd(<カ>, cn))
endfor
endfor
ウ
ツリー構造のelements配列の各層左端ノードの添字を格納する。なので２と５が格納されることはわかっている。
エに入る数値も１と３ということはわかっている。
pow(3, i-1)を答えられなかった。
各層左端ノードの添字 + 増分でlayer_top[]に格納される。
1 + x = 2, 2 + x = 5, 5 + x = 14となることはアルゴリズムを見て想像できる。
でこのxも左の式から1, 3となる。つまり3の冪乗の値になる。
pow(m, k)はmのk乗を意味するのでpow(3, 0) = 1、pow(3, 1) = 3となる。
pow(3, i-1)
layer_top[]
ルートノードから順に、各層の左端のノードの、elements配列上での添字の値を格納する。図2の場合にあは1234 * 5678, 12 * 56, 1 * 5の添字に対応する{1,2,5}が入る
この配列は各層の左端のノードの添字が格納される。（初期値では1だけ)
ツリー構造の根から順に各層左側から格納していく。
elements[]
ツリーのノードを管理する配列、ルートノードを先頭に、各そうの左側のノードから順に要素を格納する。
tidx ← layer_top[dp + 1] + <エ>
親のノードdpの子ノードpeの子ノードの子の左端のノードの配列番号つまり層３の子ノードの番号なる。
dpが２の時iが１ずつ増えながら三回処理をする
layer_top[３]になるので５、下の行の処理を見るとtidxは子のノード番号を表す。
tidxは子の三個のノードの左端の番号を表す。
三回繰り返してもlayer_top[]は５のままだ。なので何かを足さなければならない。
左端のノードは5,8,11になるので5+0,5+3,5+6になる。また増加分は繰り越されず、自分で増やすしかない。
0,3,6を表せる式を見つける。iが１ずつ増えながら三回繰り返すので3*(i-1)になる
dp
1からt_depth - 1まで1ずつ増やすと条件に書いてある。
t_depth
ツリーの層の数
- 木の深さ
オ,カ
elements[tidx] ← new_elem(cn, left(<オ>, cn), left(<カ>, cn))
elements[tidx + 1] ← new_elem(cn, right(<オ>, cn), right(<カ>, cn))
elements[tidx + 2] ← new_elem(cn, lradd(<オ>, cn), lradd(<カ>, cn))
1234 * 5678 → A:12 ,B:34 ,C:56 , D:78というノードの値を分ける作業をすると考える。
オはv1、カはv2となる。
A＊C、B＊D, (A+B)*(C+D)のノード３つを生成する。
最初の値はAがleft(<オ>, cn)、Cがleft(<カ>, cn)、cnの最初は２になる。
オ、カは親ノードの左側の値と右側の値になる。
オは1234.valuesで{4,3,2,1}となる。left()で左側から取り出す。
12になる。
子を生成する作業を二回行う（階層分）だから親ノードを取得する必要がある。
それがpeになる。elements[]から取り出した値で、1234 * 5678のような値になる。
val1とval2は左右の値を表す要素名になる
peは1234 * 5678、pe.val1は1234、pe.val1.valuesで{4,3,2,1}になる。
これを答えて間違えた。
left()は引数の値をvaluesを使って左から取り出すので、答えはpe.val1となる。
だからカはpe.val2となる。
new_elem
ノード構造体を新規に一つ生成して返す
cn
数値の桁数なので一回目は2、二回目は１となる
ツリーを用いて演算を行うプログラム
# 最下層の計算
for (iをからpow(3, t_depth -1)まで1ずつ増やす) # 深さが２なので3回
el ← elements[layer_top[t_depth] + (i - 1)] # 指定された計算式を代入する
mul ← el.val1.values[1] * el.val2.values[1] # ノードの左、右の配列同士を掛ける
el.result.N ← 2 # 乗算の結果の桁数に２を代入する
el.result.value[1] ← <キ> # 一の位の数値を代入する
el.result.value[2] ← mul / 10 # 計算結果の１０の位を代入するために１０で割り整数にする
endfor
# 最下層以外の計算
for (dpをt_depth - 1 から1まで1ずつ減らす) # 2回下のfor文を繰り返す
for (iを1からpow(3, dp - 1)まで一つずつ増やす) # 3回、一回とこのfor文を繰り返す
el ← elements[layer_top[dp] + (i - 1)] # 計算式（要素）を取り出す
cidx ← layer_top[dp + 1] + <エ> #
s1 ← sub(<ク>.result, <ケ>.result)
s2 ← sub(s1, elements[cidx + 1].result)
p1 ← shift(elements[cidx].result, el.N)
p2 ← shift(s2, el.N / 2)
p3 ← elements[cidx + 1].result
el.result ← add(add(p1, p2), p3)
endfor
endfor
answer ← carry(elements[1].result)
エ：3*(i-1)
el.result.value[1] ← <キ>
多分el.resultは２桁になり、一の位から格納されるからvalue[1]は一の位が代入される
計算結果から１０のくらいの数字を引けばなる。
el.result mod 10
間違えた
mod(mul, 10)
mulが配列の乗算しているのでmulがあっている
s1 ← sub(<ク>.result, <ケ>.result)
ク、ケは要素だと考える。
α * 10^k + (γ - α - β) * 10^(k/2) + βは最下層以外の層は、子ノードの計算結果を行う。これと対応しているようだ。
subは引き算だ。問題の行の下の行を見ると
s2 ← sub(s1, elements[cidx + 1].result)と書いてある。
３つのうちの真ん中のノードと引き算をしていることがわかる。またもう一つの下の行を見ると
p2 ← shift(s2, el.N / 2)と書いてある。s2を(el.N / 2)乗することがわかる。
なので問題の行の処理は(γ - α - β)の部分のγ - αとわかる。
γ: element[cidx+2].result
α: element[cidx].result
間違えた
γ: element[cidx+2]
α: element[cidx]
.resultは演算結果が配列になっていると考える。
N桁同士の乗算をする場合、多倍長整数の構造体において、配列valuesに必要な最大の要素数はいくつか？Nを用いて答えよ。
Nかな？
間違えた
2*Nだった。
同じ桁数の乗算だと2倍の桁数になる可能性があるためだ。
繰り上がりのcarrayを見ればわかったかもしれない。