令和5年度春期応用情報技術者試験午後問題問3 カラツバ法による多倍長整数の乗算プログラム

この問題は2023(R5)春応用情報技術者午後に出題されたものです。出題時点の法令・制度に基づく内容のため、現行の内容と一致しない場合があります。

本ページの問題文・選択肢は、原本の体裁を Web 表示用に正規化しています（改行・記号・数式・図表参照の調整）。設問の趣旨および正解に影響する変更は加えていません。

学習ガイド

配列で表した多倍長整数をカラツバ法で乗算するプログラムの問題です。1234×5678の分割を例に計算木を展開し、3分木を一次元配列へ格納する添字と、式中の値がプログラムの変数へどう対応するかを手計算でたどります。本文・表・図の根拠を行き来し、用語だけを暗記するのではなく、短い記述にも判断の理由を残して解答する手順を示します。

この記事で押さえる論点

多倍長整数を1の位から配列に格納し、桁ごとの演算と繰り上がりを分けて処理する仕組みを説明できる
M桁の乗算をA×C・B×D・(A+B)×(C+D)の3つの子ノードに分解するツリー構築を手計算で追える
3分木を1次元配列elementsとlayer_topで管理するときの添字計算式を導く
式(1)のα・β・γをプログラムのs1・s2・p1〜p3に対応付けて空欄を埋める

出題情報

出題: 2023(R5)春応用情報技術者午後問3
配点: 20点満点
模範解答: 公表(設問ごとに掲載)

出題趣旨・採点講評(IPA 公表)

桁数が非常に大きい整数の演算は，数学における学問的な用途のほか，暗号処理の分野などで実用化されているアルゴリズムである。本問では，任意桁数の整数の乗算処理を題材に，多倍長整数の演算のアルゴリズムの一つであるカラツバ法に関するアルゴリズムの理解と実装について問う。

問3では，任意桁数の整数の乗算処理を題材に，多倍長整数の演算のアルゴリズムの一つであるカラツバ法について出題した。全体として正答率は平均的であった。

問題本文

多倍長整数の演算に関する次の記述を読んで，設問に答えよ。

コンピュータが一度に処理できる整数の最大桁には，CPUが一度に扱える情報量に依存した限界がある。一度に扱える桁数を超える演算を行う一つの方法として，10を基数とした多倍長整数（以下，多倍長整数という）を用いる方法がある。

〔多倍長整数の加減算〕

多倍長整数の演算では，整数の桁ごとの値を，1の位から順に1次元配列に格納して管理する。例えば整数123は，要素数が3の配列に{3, 2, 1}を格納して表現する。
多倍長整数の加算は，“桁ごとの加算”の後，“繰り上がり”を処理することで行う。456＋789を計算した例を図1に示す。

“桁ごとの加算”を行うと，配列の内容は{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，②B×D，③(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となる。

〔ツリーを用いた演算〕

ツリーの最下層のノードは，整数の乗算だけで計算できる。最下層以外の層は，子ノードの計算結果を使って，次の式で計算できることが分かっている。ここで， $\alpha$ ， $\beta$ ， $\gamma$ は，それぞれ子ノード①，②，③の乗算の計算結果を，Kは対象のノードの桁数を表す。

$\alpha \times 10^K + (\gamma - \alpha - \beta) \times 10^{K/2} + \beta$ ……(1)

図2のルートノードの場合，K＝4， $\alpha$ ＝672， $\beta$ ＝2652， $\gamma$ ＝6164なので，計算結果は次のとおりとなる。

672×10000＋(6164－672－2652)×100＋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，q，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^k倍する。
sub(p, q)	多倍長整数	pとqについて，“桁ごとの減算”を行いp-qを返す。

名称	種類	型	内容
elements[]	配列	ノード	ツリーのノードを管理する配列。ルートノードを先頭に，各層の左側のノードから順に要素を格納する。図2の場合は，{1234×5678, 12×56, 34×78, 46×134, 1×5, 2×6, …}の順で格納する。
layer_top[]	配列	整数	ルートノードから順に，各層の左端のノードの，elements 配列上での添字の値を格納する。図2の場合は1234×5678，12×56，1×5の添字に対応する{1, 2, 5}が入る。
mod(m, k)	関数	整数	mをkで割った剰余を整数で返す。
new_elem(k, v1, v2)	関数	ノード	取り扱う多倍長整数の桁数がkで，v1×v2 の乗算を表すノード構造体を新規に一つ作成して返す。
pow(m, k)	関数	整数	mのk乗を整数で返す。kが0の場合は1を返す。
t_depth	変数	整数	ツリーの層の数。図2の場合は3である。
val1, val2	変数	多倍長整数	乗算する対象の二つの値。図2の場合，ルートノードの二つの値で，val1は1234，val2は5678である。
answer	変数	多倍長整数	乗算の計算結果を格納する変数

設問と解答・解説

設問1

図2中のア，イに入れる適切な字句を答えよ。

(1)

アに入れる適切な字句を答えよ。

模範解答

3×7

採点基準(配点 2点)

正確性（内容）(2点)

2点: 正解「3×7」が正確に記述されている。
1点: 式の一部が正しい、または軽微な表記揺れがある。
0点: 無解答または完全に誤った解答。

解説

カラツバ法における再帰的な乗算の分割過程をトレースする問題です。
図2の木構造は、大きな桁数の乗算をより小さな桁数の乗算に分割していく過程を示しています。アルゴリズムのルールに従い、上位桁同士の積（ $x_1 y_1$ ）と下位桁同士の積（ $x_0 y_0$ ）がどのように分離されるかを図から読み解くと、空欄アには下位桁同士の積に相当する式が入ることがわかります。

高得点のポイント

カラツバ法の再帰的な分割ルールを正しく理解していること。
図中の他のノードとの関係性から、正しい式 3×7 を導出できていること。

(2)

イに入れる適切な字句を答えよ。

模範解答

4×12

採点基準(配点 2点)

正確性（内容）(2点)

2点: 正解「4×12」が正確に記述されている。
1点: 式の一部が正しい、または軽微な表記揺れがある。
0点: 無解答または完全に誤った解答。

解説

カラツバ法における再帰的な乗算の分割過程をトレースする問題です。
空欄アと同様に、図2のノードの分割則に従って元の被乗数と乗数がどのように分かれているかを追跡します。空欄イには上位桁同士の積（ $x_1 y_1$ ）に関連する式が入ります。

高得点のポイント

乗算の対象となる桁の分割方法を正しくトレースできていること。
適切な数値の組み合わせ 4×12 を導出できていること。

設問2

図2中の層2にある 46×134 のノードについて，本文中の式(1)の数式は具体的にどのような計算式になるか。次の式の①～④に入れる適切な整数を答えよ。

(①)×100＋((②)－(③)－84)×10＋(④)

(1)

① に入れる適切な整数を答えよ。

模範解答

配点 1点

解説

カラツバ法の基本式に基づいて各項の値を導き出す問題です。
式(1)は、乗算 $X \cdot Y$ を次のように展開します。
$X \cdot Y = A \cdot 100 + (C - A - B) \cdot 10 + B$
ここで、 $A = x_1 y_1$ , $B = x_0 y_0$ , $C = (x_1 + x_0)(y_1 + y_0)$ となります。式中の $84$ から $B = 84$ と特定でき、他の計算結果との整合性から $A = 48$ が導き出せます。
したがって、①には $A$ に該当する 48 が入ります。

各選択肢の解説

誤答パターンの解説: アルゴリズムの公式における $A$ , $B$ , $C$ の配置を誤解して、別の項の数値を当てはめてしまうケースが考えられます。式の構造と図の対応を正確に読み取ることが重要です。

(2)

② に入れる適切な整数を答えよ。

模範解答

260

配点 1点

解説

式の展開項における $C = (x_1 + x_0)(y_1 + y_0)$ の部分を求める問題です。
式(1)の展開 $(C - A - B) \cdot 10$ における ② は $C$ に対応します。ノードの計算履歴から $C = 260$ となることがわかります。

各選択肢の解説

誤答パターンの解説: $x_1+x_0$ と $y_1+y_0$ の加算を忘れたり、乗算処理を誤って計算してしまうと、正しい $C$ の値である260を導けません。計算規則を正確に当てはめる必要があります。

(3)

③ に入れる適切な整数を答えよ。

模範解答

配点 1点

解説

式の展開項における減算部分の $A = x_1 y_1$ を求める問題です。
カラツバ法の中間項 $(C - A - B)$ における ③ は $A$ に該当するため、①と同じく 48 となります。

各選択肢の解説

誤答パターンの解説: ①と同じ値が入るというカラツバ法の構造に気づかず、別の数値を計算してしまうケースが挙げられます。公式の仕組みの理解が問われます。

(4)

④ に入れる適切な整数を答えよ。

模範解答

配点 1点

解説

式の展開項における末尾の加算部分 $B = x_0 y_0$ を求める問題です。
式の直前に $- 84$ とあるように、 $B = 84$ であることは明らかです。したがって ④ には 84 が入ります。

各選択肢の解説

誤答パターンの解説: 中間項における減算対象の定数（ $84$ ）と、最終的に加算される項 $B$ が同じ値になることに気づかないと、誤った値を入力してしまいます。

設問3

図3中のウ～カに入れる適切な字句を答えよ。

(1)

ウに入れる適切な字句を答えよ。

模範解答

pow(3, i － 1)

採点基準(配点 1点)

正確性（内容）(1点)

1点: 正解「pow(3, i － 1)」が正確に記述されている。
0点: 無解答または誤った解答。

解説

ツリー構造を用いた情報管理において、1次元配列上で要素の位置を計算する問題です。
カラツバ法の各再帰ステップでは、1つの乗算が3つの部分乗算に分割されます。つまり、この処理は各ノードが3つの子を持つ3分木として表現されます。
根となるノードの深さを $i = 1$ とすると、深さ $i$ におけるノードの総数は $3^{i-1}$ 個となります。
したがって、ウには pow(3, i - 1) が入ります。

高得点のポイント

ツリーが3分木であることを正しく理解していること。
深さ $i$ とノード数の関係を累乗関数 pow を用いて正しく表現できていること。

(2)

エに入れる適切な字句を答えよ。

模範解答

3*(i － 1)

採点基準(配点 1点)

正確性（内容）(1点)

1点: 正解「3*(i － 1)」が正確に記述されている。
0点: 無解答または誤った解答。

解説

配列を用いてツリー構造を管理する際、親ノードから子ノードへのインデックス計算を行う問題です。
3分木において、ある深さのノードから次の深さの子ノード群へ遷移する際、インデックスは深さに応じて3倍ずつスケールします。
エには、インデックスのオフセットを適切に計算するための式 3*(i - 1) が入ります。

高得点のポイント

1次元配列でツリー構造を表現する際のインデックスの規則性を把握していること。
階層に応じたインデックスの差分を正しく数式化できていること。

(3)

オに入れる適切な字句を答えよ。

模範解答

pe.val1

pe.val2

採点基準(配点 1点)

正確性（内容）(1点)

1点: 正解「pe.val1」または「pe.val2」が正確に記述されている。
0点: 無解答または誤った解答。

解説

構造体から必要な変数を取り出す問題です。
対象となるノードの要素 pe（構造体などで定義されたデータ型）には、乗算に必要な2つの値が含まれています。
乗算の対象となるそれぞれの値を取得するため、オとカには pe.val1 と pe.val2 が入ります。

高得点のポイント

構造体のメンバアクセス（ドット演算子等）の記述方法を理解していること。
演算対象となる2つの値を正しく指定できていること。

(4)

カに入れる適切な字句を答えよ。

模範解答

pe.val1

pe.val2

採点基準(配点 1点)

正確性（内容）(1点)

1点: 正解「pe.val1」または「pe.val2」が正確に記述されている。
0点: 無解答または誤った解答。

解説

構造体から必要な変数を取り出す問題です。
オの解説と同様に、乗算のもう一方の値を取得するために pe.val2 または pe.val1 が入ります（オと対になります）。

高得点のポイント

構造体変数の要素を適切に取り出せていること。

設問3のエは，正答率が低かった。ツリーなどの構造をもった情報について，1次元配列を用いて管理する手法は，よく用いられる。データ構造を理解し，単純な形でプログラムを記述できる能力を身につけてほしい。設問3のオ，カは，いずれも正答率がやや低かった。構造体の取扱方と，ツリーの情報構造の両方を理解し，注意深く解答してほしい。

設問4

図4中のキ～ケに入れる適切な字句を答えよ。

(1)

キに入れる適切な字句を答えよ。

模範解答

mod(mul, 10)

採点基準(配点 2点)

正確性（内容）(2点)

2点: 正解「mod(mul, 10)」が正確に記述されている。
1点: 式の一部が正しい、または軽微な表記揺れがある。
0点: 無解答または完全に誤った解答。

解説

各桁の計算処理において、桁あふれ（繰り上がり）を考慮して現在の桁の値を決定する問題です。
変数 mul に乗算結果や加算結果が格納されている場合、現在の桁（基数10）に残る値は、mul を10で割った余りとなります。
したがって、キには mod(mul, 10) が入ります。

高得点のポイント

基数（10）での剰余を求める関数 mod を適切に使用できていること。
繰り上がり処理のアルゴリズムを正しく理解していること。

(2)

クに入れる適切な字句を答えよ。

模範解答

elements[cidx ＋ 2]

採点基準(配点 2点)

正確性（内容）(2点)

2点: 正解「elements[cidx + 2]」が正確に記述されている。
1点: 式の一部が正しい、または軽微な表記揺れがある。
0点: 無解答または完全に誤った解答。

解説

カラツバ法の計算において、3つの部分乗算の結果を用いて最終的な積の各項を求める処理です。
計算式 $A \cdot 100 + (C - A - B) \cdot 10 + B$ の $(C - A - B)$ の部分を計算しています。
配列 elements のうち、インデックス cidx から順に $A, B, C$ が格納されているとすると、 $C$ に該当する要素は elements[cidx + 2] となります。

高得点のポイント

配列上のどの位置に $A, B, C$ が格納されているかを正しくトレースできていること。
$(C - A - B)$ を算出するための配列インデックスを正確に記述できていること。

(3)

ケに入れる適切な字句を答えよ。

模範解答

elements[cidx]

採点基準(配点 2点)

正確性（内容）(2点)

2点: 正解「elements[cidx]」が正確に記述されている。
1点: 式の一部が正しい、または軽微な表記揺れがある。
0点: 無解答または完全に誤った解答。

解説

カラツバ法の計算において、3つの部分乗算の結果を用いて最終的な積の各項を求める処理です。
クの解説と同様に、 $(C - A - B)$ を求めるための $A$ の値を取得します。 $A$ は配列 elements の先頭のインデックスにあるため、ケには elements[cidx] が入ります。

高得点のポイント

カラツバ法の中間項の計算において、配列のインデックス構造を正しく参照できていること。

設問5

N 桁同士の乗算をする場合，多倍長整数の構造体において，配列 values に必要な最大の要素数は幾つか。N を用いて答えよ。

模範解答

2 × N

採点基準(配点 2点)

正確性（内容）(2点)

2点: 正解「2 × N」と同等の式が正確に記述されている。
1点: Nを用いた式であるが係数等の誤りがある、または軽微な表記ミスがある。
0点: 無解答または完全に誤った解答。

解説

多倍長整数の乗算において必要な配列の要素数を求める問題です。
$N$ 桁の整数同士の乗算を行うと、その積の桁数は最大で $2N$ 桁になります。
たとえば2桁の数同士の最大値 $99 \times 99 = 9801$ は4桁になります。計算結果の各桁の値を配列 values に格納するため、必要な最大の要素数は $2N$ となります。

高得点のポイント

乗算結果の最大桁数が $2N$ になることを正しく理解していること。
変数 $N$ を用いて 2 × N（または 2*N, 2N 等）と適切な数式で解答できていること。