乗算-筆算のシミュレーションの方法
概要
- 大きな数を計算する際に、桁あふれをしてしまうのであれば、普通の方法では計算できない
- 小学校で習う方法で、乗算の筆算があるが、これをシミュレーションすることで、桁数の制限を受けることなく、乗算を行える
実装例
def multiply(num1: str, num2: str) -> str:
*num1, = map(int, num1[::-1])
*num2, = map(int, num2[::-1])
"""
桁上げを考慮しながら掛け算の筆算をシミュレーション
"""
calcs = []
for x2 in num2:
tmp = 0
calc = []
for x1 in num1:
calc.append( (x1*x2 + tmp)%10 )
tmp = (x1*x2 + tmp)//10
if tmp != 0:
calc.append(tmp)
calcs.append(calc)
"""
calcテーブルの足し合わせ
"""
size = len(calcs) + max([len(calc) for calc in calcs])
ans = [0] * size
for k, calc in enumerate(calcs):
for i in range(len(calc)):
ans[k+i] += calc[i]
# 10以上になった場合は繰り上げ
for i in range(size):
if ans[i] >= 10:
ans[i+1] += ans[i]//10
ans[i] = ans[i]%10
"""
余分な数値のトリミング
"""
ans = ans[::-1]
for i in range(len(ans)):
if ans[0] == 0:
ans.pop(0)
else:
break
ans = [0] if ans == [] else ans
return "".join(map(str, ans))
print(multiply(num1 = "43", num2 = "56"))
print(multiply(num1 = "123", num2 = "456"))
print(multiply(num1 = "0", num2 = "0"))