#カラツバ法 def karatsuba(x, y): # 1. ベースケース（再帰の終了条件） # どちらかが1桁（10未満）になったら、通常の掛け算を行う if x < 10 or y < 10: return x * y # 2. 桁数の計算と分割の基準（m）を決定 # 2つの数のうち、大きい方の桁数を基準にする n = max(len(str(x)), len(str(y))) m = n // 2 # 3. 数の分割 (10^m で割った商と余りで、上位と下位に分ける) # x = x1 * 10^m + x0 x1 = x // (10 ** m) x0 = x % (10 ** m) # y = y1 * 10^m + y0 y1 = y // (10 ** m) y0 = y % (10 ** m) # 4. 3回の掛け算（再帰呼び出し） z2 = karatsuba(x1, y1) # 1回目: 上位桁同士の積 z0 = karatsuba(x0, y0) # 2回目: 下位桁同士の積 z1 = karatsuba(x1 + x0, y1 + y0) - z2 - z0 # 3回目: (上位+下位)同士の積 - z2 - z0 # 5. 結果を結合して返す return z2 * (10 ** (2 * m)) + z1 * (10 ** m) + z0 # --- 実行例 --- # 5678 × 1234 を計算する print(karatsuba(5678, 1234)) # 出力: 7006652 # 1456 × 6533 を計算する print(karatsuba(1456, 6533)) # 出力: 9512048 #2023s 多倍長整数の演算 import math # ========================================== # 1. 構造体の定義 (表1) # ========================================== class LargeInt: """多倍長整数を表すクラス""" def __init__(self, n: int = 0): self.N = n # 多倍長整数の桁数 # 1の位から順に格納する1次元配列 (1-indexedを模倣するため、0番目はダミーとしてNoneを入れる) # 添字 1 が1の位、2 が10の位... となる self.values = [None] + [0] * (2 * n + 2) # 設問5より十分なサイズを確保 def __repr__(self): # デバッグ・表示用 (上の位から順に文字列化) # Noneを除外し、有効な桁数分を逆順にして結合 valid_vals = [str(x) for x in self.values[1:] if x is not None] # 繰り上がり処理前は単に配列の状態を表示する return f"LargeInt(N={self.N}, values={self.values[1:self.N+1]})" class Node: """ツリーのノードを表すクラス""" def __init__(self, k: int = 0, v1: LargeInt = None, v2: LargeInt = None): self.N = k # ノードが取り扱う多倍長整数の桁数 self.val1 = v1 # 乗算記号の左側の値 self.val2 = v2 # 乗算記号の右側の値 self.result = LargeInt(k) # 乗算の計算結果 # ========================================== # 2. 多倍長整数の操作を行う関数 (表2) # ========================================== def add(p: LargeInt, q: LargeInt) -> LargeInt: """p と q について、"桁ごとの加算" を行う""" max_n = max(p.N, q.N) res = LargeInt(max_n) for i in range(1, max_n + 1): p_val = p.values[i] if i <= p.N else 0 q_val = q.values[i] if i <= q.N else 0 res.values[i] = p_val + q_val return res def sub(p: LargeInt, q: LargeInt) -> LargeInt: """p と q について、"桁ごとの減算" を行い p - q を返す""" max_n = max(p.N, q.N) res = LargeInt(max_n) for i in range(1, max_n + 1): p_val = p.values[i] if i <= p.N else 0 q_val = q.values[i] if i <= q.N else 0 res.values[i] = p_val - q_val return res def left(p: LargeInt, k: int) -> LargeInt: """p について、values の添字が大きい方の k 個の要素を返す (上位桁)""" res = LargeInt(k) for i in range(1, k + 1): # 元の配列の上位側（p.N - k + i）からコピー res.values[i] = p.values[p.N - k + i] return res def right(p: LargeInt, k: int) -> LargeInt: """p について、values の添字が小さい方の k 個の要素を返す (下位桁)""" res = LargeInt(k) for i in range(1, k + 1): res.values[i] = p.values[i] return res def lradd(p: LargeInt, k: int) -> LargeInt: """add(left(p, k), right(p, k)) の結果を返す""" return add(left(p, k), right(p, k)) def shift(p: LargeInt, k: int) -> LargeInt: """p を 10^k 倍する (配列の要素を上位へずらす)""" res = LargeInt(p.N + k) # 下位k個を0で埋める for i in range(1, k + 1): res.values[i] = 0 # 元の値をずらして格納 for i in range(1, p.N + 1): res.values[i + k] = p.values[i] return res def carry(p: LargeInt) -> LargeInt: """p について "繰り上がり"・"繰り下がり" の処理を行う""" # 処理中に桁数が増える可能性を考慮し、コピーを作成して処理 res = LargeInt(p.N) for i in range(1, len(p.values)): if p.values[i] is not None: res.values[i] = p.values[i] current_idx = 1 # 配列の最後まで繰り上がりを走査 while current_idx < len(res.values) - 1: v = res.values[current_idx] if v >= 10: res.values[current_idx] = v % 10 res.values[current_idx + 1] += v // 10 elif v < 0: # 繰り下がり処理 (今回の乗算では基本発生しないが仕様通り) borrow = (-v + 9) // 10 res.values[current_idx] = v + borrow * 10 res.values[current_idx + 1] -= borrow current_idx += 1 # 有効な最大桁数を再計算してNに設定 max_len = 1 for i in range(len(res.values) - 1, 0, -1): if res.values[i] != 0 and res.values[i] is not None: max_len = i break res.N = max_len return res # ========================================== # 3. 補助関数 (表3) # ========================================== def pow_func(m: int, k: int) -> int: """m の k 乘を整数で返す""" return int(math.pow(m, k)) def mod(m: int, k: int) -> int: """m を k で割った剰余を整数で返す""" return m % k def new_elem(k: int, v1: LargeInt, v2: LargeInt) -> Node: """新しくノード構造体を作成して返す""" return Node(k, v1, v2) # 数値を今回の多倍長整数クラスに変換するヘルパー関数 def to_large_int(num_str: str, n: int) -> LargeInt: # 桁数が足りない場合は上位を0埋めする (101.jpgの仕様) num_str = num_str.zfill(n) li = LargeInt(n) # 文字列の配列表現は「1の位から順に格納」 for i in range(n): li.values[i + 1] = int(num_str[n - 1 - i]) return li # 結果を人間が見やすい普通の数値文字列に戻すヘルパー関数 def to_standard_str(li: LargeInt) -> str: # 上位桁から順に結合 res_str = "" for i in range(li.N, 0, -1): res_str += str(li.values[i]) return res_str if res_str else "0" # ========================================== # 4. メインアルゴリズム (図3 & 図4) # ========================================== # グローバル変数の定義 (図3, 図4内の変数はすべて大域変数) elements = [None] * 50 # ツリーのノードを管理する配列 (十分な大きさを確保) layer_top = [None] * 10 # 各層の左端のノードの、elements配列上での添字 t_depth = 3 # ツリーの層の数 (今回の例 1234 * 5678 では 3) def main_process(val1_str, val2_str): global elements, layer_top # 初期値の設定 (1234 と 5678) N_start = len(val1_str) val1 = to_large_int(val1_str, N_start) val2 = to_large_int(val2_str, N_start) # -------------------------------------- # 【図3】ツリーを構築するプログラム # -------------------------------------- # // ツリーの各層の、elements配列上での先端インデックスを算出する layer_top[1] = 1 # // ルートノードは先頭なので1を入れる for i in range(1, t_depth): # [空欄 ウ]: pow(3, i - 1) layer_top[i + 1] = layer_top[i] + pow_func(3, i - 1) # // ツリーを構築する elements[1] = new_elem(val1.N, val1, val2) # // ルートノードを用意。桁数はval1の桁数を使う for dp in range(1, t_depth): # // ルートノードの層から、最下層以外の層を順に処理 for i in range(1, pow_func(3, dp - 1) + 1): # // 親ノードになる層の要素数だけ繰り返す pe = elements[layer_top[dp] + (i - 1)] # // 親ノードの要素を取得 cn = pe.N // 2 # // 子ノードの桁数を算出 # [空欄 エ]: 3 * (i - 1) tidx = layer_top[dp + 1] + (3 * (i - 1)) # // 子ノード①へのインデックス # [空欄 オ]: pe.val1 / [空欄 カ]: pe.val2 elements[tidx] = new_elem(cn, left(pe.val1, cn), left(pe.val2, cn)) elements[tidx + 1] = new_elem(cn, right(pe.val1, cn), right(pe.val2, cn)) elements[tidx + 2] = new_elem(cn, lradd(pe.val1, cn), lradd(pe.val2, cn)) # -------------------------------------- # 【図4】ツリーを用いて演算を行うプログラム # -------------------------------------- # // 最下層の計算 for i in range(1, pow_func(3, t_depth - 1) + 1): el = elements[layer_top[t_depth] + (i - 1)] # // 最下層のノード mul = el.val1.values[1] * el.val2.values[1] # // 最下層の乗算 el.result.N = 2 # // 計算結果は2桁の多倍長整数 # [空欄 キ]: mod(mul, 10) el.result.values[1] = mod(mul, 10) # // 1の位 el.result.values[2] = mul // 10 # // 10の位 # // 最下層以外の計算 for dp in range(t_depth - 1, 0, -1): # // 最下層より一つ上の層から順に処理 for i in range(1, pow_func(3, dp - 1) + 1): # // 各層の要素数だけ繰り返す el = elements[layer_top[dp] + (i - 1)] # // 計算対象のノード # [空欄 エ]: 3 * (i - 1) cidx = layer_top[dp + 1] + (3 * (i - 1)) # // 子ノード①へのインデックス # [空欄 ク]: elements[cidx + 2] / [空欄 ケ]: elements[cidx] s1 = sub(elements[cidx + 2].result, elements[cidx].result) s2 = sub(s1, elements[cidx + 1].result) # // γ - a - β を計算 p1 = shift(elements[cidx].result, el.N) # // α × 10^K を計算 p2 = shift(s2, el.N // 2) # // (γ - a - β) × 10^(K/2) を計算 p3 = elements[cidx + 1].result # // β を計算 el.result = add(add(p1, p2), p3) # // 繰り上がり処理 answer = carry(elements[1].result) # // 計算結果をanswerに格納 return answer # ========================================== # 5. 実行と結果確認 # ========================================== if __name__ == "__main__": v1 = "1234" v2 = "5678" print(f"計算開始: {v1} × {v2}") ans_large_int = main_process(v1, v2) print("--- 計算完了 ---") print(f"多倍長整数の内部の型: {ans_large_int}") print(f"文字列に復元した答え: {to_standard_str(ans_large_int)}") print(f"Pythonの標準算術演算での答え: {int(v1) * int(v2)}")