多倍長整数の演算に関する次の記述を読んで，設問に答えよ。
コンピュータが一度に処理できる整数の最大桁には，CPUが一度に扱える情報量に依存した限界がある。一度に扱える桁数を超える演算を行う一つの方法として10を基数とした多倍長整数（以下，多倍長整数という）を用いる方法がある。
〔多倍長整数の加減算〕
多倍長整数の演算では，整数の桁ごとの値を，1の位から順に1次元配列に格納して管理する。例えば整数123は，要素数が3の配列に{3，2，1}を格納して表現する。
多倍長整数の加算は，“桁ごとの加算”の後，“繰り上がり”を処理することで行う。456+789を計算した例を図1に示す。
図1 456+789を計算した例
“桁ごとの加算”を行うと，配列の内容は{15, 13, 11}となる。1の位は15になるが，15は10×1+5なので，10の位である13に1を繰り上げて{5, 14, 11}とする。これを最上位まで繰り返す。最上位で繰り上がりが発生する場合は，配列の要素数を増やして対応する。減算も同様に“桁ごとの減算”と“繰り下がり”との処理で計算できる。
〔多倍長整数の乗算〕
多倍長整数の乗算については，計算量を削減するアルゴリズムが考案されており，その中の一つにカラツバ法がある。ここでは，桁数が2のべき乗で，同じ桁数をもった正の整数同士の乗算について，カラツバ法を適用した計算を行うことを考える。桁数が2のべき乗でない整数や，桁数が異なる整数同士の乗算を扱う場合は，上位の桁を0で埋めて処理する。例えば，123×4は0123×0004として扱う。
〔ツリー構造の構築〕
カラツバ法を適用した乗算のアルゴリズムは，計算のためのツリー構造（以下，ツリーという）を作る処理と，ツリーを用いて演算をする処理から成る。ツリーは，多倍長整数の乗算の式を一つのノードとし，一つのノードは3個の子ノードをもつ。
M桁×M桁の乗算の式について，乗算記号の左右にある値を，それぞれM/2桁ずつに分けてA，B，C，Dの四つの多倍長整数を作る。これらの整数を使って①A×C，②BxD，③(A+B)×(C+D)の3個の子ノードを作り，M/2桁×M/2桁の乗算を行う層を作る。(A+B)，(C+D)は多倍長整数の加算の結果であるが，ここでは“桁ごとの加算”だけを行い，“繰り上がり”の処理はツリーを用いて行う演算の最後でまとめて行う。生成した子ノードについても同じ手順を繰り返し，1桁×1桁の乗算を行う最下層のノードまで展開する。
1234×5678についてのツリーを図2に示す。図2の層2の場合，①は12×56，②は34×78，③は46×134となる。③の(C+D)は，“桁ごとの加算”だけの処理を行うと，10の位が5+7=12，1の位が6+8=14となるので，12×10+14=134となる。
図2 1234×5678についてのツリー
〔ツリーを用いた演算〕
ツリーの最下層のノードは，整数の乗算だけで計算できる。最下層以外の層は，子ノードの計算結果を使って，次の式で計算できることが分かっている。ここで，α，β，rは，それぞれ子ノード1，2，3の乗算の計算結果を，Kは対象のノードの桁数を表す。
α×10ᵏ+(γ-a-β)×10K/2+β.....（1）
図2のルートノードの場合，K=4，a=672，β=2652，r=6164なので，計算結果は次のとおりとなる。
672×10000+(6164-672-2652)x100+2652=7006652
桁数が2のべき乗の多倍長整数val1，val2の乗算を行うプログラムを作成した。
プログラム中で利用する多倍長整数と，ツリーのノードは構造体で取り扱う。構造体の型と要素を表1に示す。構造体の各要素には，構造体の変数名要素名でアクセスできる。また，配列の添字は1から始まる。
| 構造体の型 | 要素名 | 要素の型 | 內容 |
| 多倍長整数 | N | 整数 | 多倍長整数の桁数 |
| values | 整数の配列 | 桁ごとの値を管理する1次元配列。1の位の値から順に値を格納する。 配列の要素は，必要な桁を全て格納するのに十分な数が確保されているものとする。 |
|
| ノード | N | 整数 | ノードが取り扱う多倍長整数の桁数。図2の1234×5678のノードの場合は4である。 |
| val1 | 多倍長整数 | 乗算記号の左側の値 | |
| val2 | 多倍長整数 | 乗算記号の右側の値 | |
| result | 多倍長整数 | 乗算の計算結果 |
多倍長整数の操作を行う関数を表2に，プログラムで使用する主な変数，配列及び関数を表3，与えられた二つの多倍長整数からツリーを構築するプログラムを図3に，そのツリーを用いて演算を行うプログラムを図4に，それぞれ示す。表2，表3中のp，g，v1，v2の型は多倍長整数である。また，図3，図4中の変数は全て大域変数である。
| 名称 | 型 | 内容 |
| add(p, q) | 多倍長整数 | pとqについて，“桁ごとの加算”を行う。 |
| carry(p) | 多倍長整数 | pについて“繰り上がり”・“繰り下がり”の処理を行う。 |
| left(p, k) | 多倍長整数 | pについて，valuesの添字が大きい方のk個の要素を返す。 pのvaluesが{4, 3, 2, 1}，kが2であれば，valuesが{2, 1}の多倍長整数を返す。 |
| right(p,k) | 多倍長整数 | pについて，valuesの添字が小さい方のk個の要素を返す。 pのvaluesが{4, 3, 2, 1}，kが2であれば，valuesが{4, 3}の多倍長整数を返す。 |
| lradd(p,k) | 多倍長整数 | add(left(p, k), right(p, k))の結果を返す。 |
| shift(p,k) | 多倍長整数 | pを10ᵏ倍する。 |
| sub(p,q) | 多倍長整数 | pとqについて，“桁ごとの減算”を行いp-qを返す。 |
| 名称 | 種類 | 型 | 內容 |
| elements | 配列 | ノード | ツリーのノードを管理する配列。ルートノードを先頭に，各層の左側のノードから順に要素を格納する。 図2の場合は，{1234×5678，12×56，34×78，46×134，1×5，26，...}の順で格納する。 |
| layer_top | 配列 | 整数 | ルートノードから順に，各層の左端のノードの，elements配列上での添字の値を格納する。 図2の場合は1234×5678，12×56，1×5の添字に対応する{1, 2, 5}が入る。 |
| mod(m, k) | 関数 | 整数 | mをkで割った剰余を整数で返す。 |
| new_elem(k, v1, v2) | 関数 | 整数 | 取り扱う多倍長整数の桁数がkで，v1xv2の乗算を表すノード構造体を新規に一つ作成して返す。 |
| pow(m, k) | 関数 | ノード | mのk乗を整数で返す。kが0の場合は1を返す。 |
| t_depth | 変数 | 整数 | ツリーの層の数。図2の場合は3である。 |
| vall，val2 | 変数 | 多倍長整数 | 乗算する対象の二つの値。図2の場合，ルートノードの二つの値で，valは1234，val2は5678である。 |
| answer | 変数 | 多倍長整数 | 乗算の計算結果を格納する変数 |
図3 与えられた二つの多倍長整数からツリーを構築するプログラム
図4 ツリーを用いて演算を行うプログラム
出典：令和5年度春期 問3
設問1 図2中の ア ， イ に入れる適切な字句を答えよ。
解答・解説
解答例
ア：3 × 7 イ：4 × 12
解説
設問2 図2中の層2にある46×134のノードについて，本文中の式（1）の数式は具体的にどのような計算式になるか。次の式の①〜④に入れる適切な整数を答えよ。
( ① )×100+(( ② )-( ③ )-84)×10+( ④ )
解答・解説
解答例
① 48 ② 260 ③ 48 ④ 84
解説
設問3 図3中の ウ 〜 カ に入れる適切な字句を答えよ。
解答・解説
解答例
ウ：pow(3, i - 1)
エ：3*(i - 1)
オ：pe.val1
カ：pe.val2
解説
設問4 図4中の キ 〜 ケ に入れる適切な字句を答えよ。
解答・解説
解答例
キ：mod(mul, 10)
ク：elements[cidx + 2]
ケ：elements[cidx]
解説
設問5 N桁同士の乗算をする場合，多倍長整数の構造体において，配列valuesに必要な最大の要素数は幾つか。Nを用いて答えよ。
解答・解説
解答例
2 × N
解説
IPA公開情報
出題趣旨
桁数が非常に大きい整数の演算は，数学における学問的な用途のほか，暗号処理の分野などで実用化されているアルゴリズムである。
本問では，任意桁数の整数の乗算処理を題材に，多倍長整数の演算のアルゴリズムの一つであるカラツバ法に関するアルゴリズムの理解と実装について問う。
採点講評
問 3 では，任意桁数の整数の乗算処理を題材に，多倍長整数の演算のアルゴリズムの一つであるカラツバ法について出題した。全体として正答率は平均的であった。
設問 3 のエは，正答率が低かった。ツリーなどの構造をもった情報について，1 次元配列を用いて管理する手法は，よく用いられる。データ構造を理解し，単純な形でプログラムを記述できる能力を身につけてほしい。
設問 3 のオ，カは，いずれも正答率がやや低かった。構造体の取扱方と，ツリーの情報構造の両方を理解し，注意深く解答してほしい。
