Python - 多桁乗算（標準（筆算）法）！
Updated:
前回、 Python 3 で多桁計算を行う方法を紹介しました。
ただ、乗算は一方が多桁でもう一方が小さい桁数と限定していました。
今回は、多桁同士の乗算アルゴリズム（標準（筆算）法）を Python 3 で実装してみました。
0. 前提条件
- LMDE 2 (Linux Mint Debian Edition 2; 64bit) での作業を想定。
- Python 3.6.4 での作業を想定。
- 当方は他のバージョンとの共存環境であり、
python3.6,pip3.6で 3.6 系を使用するようにしている。（適宜、置き換えて考えること）
1. アルゴリズムについて
当ブログ過去記事を参照。
2. Python スクリプトの作成
- 敢えてオブジェクト指向で作成している。
- Shebang ストリング（1行目）では、フルパスでコマンド指定している。（当方の慣習）
- 数値計算ライブラリ NumPy を使用しない。（この程度の計算では、逆に2倍程度時間がかかってしまうため）
- 必要であれば、スクリプト内の定数を変更する。
File: multiply_normal.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#! /usr/local/bin/python3.6
"""
Multiplication of big-digit values
"""
import random
import sys
import traceback
class MultiplyNormal:
D_MAX = 1024 # Maximum number of digits (power of 2)
D = 1024 # Digits of computation (Multiples of 4 <= D_MAX)
def __init__(self):
self.a = [random.randrange(10) for _ in range(self.D)]
self.b = [random.randrange(10) for _ in range(self.D)]
def compute(self):
""" Computation of multiplication """
try:
for i in range(self.D_MAX - len(self.a)):
self.a.append(0)
for i in range(self.D_MAX - len(self.b)):
self.b.append(0)
z = self.__multiply_normal(self.a, self.b)
z = self.__do_carry(z)
self.__display(self.a, self.b, z);
except Exception as e:
raise
def __multiply_normal(self, a, b):
""" Normal multiplication
:param list a
:param list b
:return list z
"""
try:
a_len, b_len = len(a), len(b)
z = [0 for _ in range(a_len + b_len)]
for j in range(b_len):
for i in range(a_len):
z[j + i] += a[i] * b[j]
return z
except Exception as e:
raise
def __do_carry(self, a):
""" Process of carrying
:param list a
:return list z
"""
cr = 0
try:
for i in range(len(a)):
a[i] += cr
cr = a[i] // 10
a[i] -= cr * 10
if cr != 0:
print("[ OVERFLOW!! ] ", cr)
return a
except Exception as e:
raise
def __display(self, a, b, z):
""" Display
:param list a
:param list b
:param list z
"""
a_len, b_len, z_len = self.D_MAX, self.D_MAX, self.D_MAX * 2
try:
while a[a_len - 1] == 0:
if a[a_len - 1] == 0:
a_len -= 1
while b[b_len - 1] == 0:
if b[b_len - 1] == 0:
b_len -= 1
while z[z_len - 1] == 0:
if z[z_len - 1] == 0:
z_len -= 1
print("a =")
for i in reversed(range(a_len)):
print(a[i], end="")
if (a_len - i) % 10 == 0:
print(" ", end="")
if (a_len - i) % 50 == 0:
print()
print()
print("b =")
for i in reversed(range(b_len)):
print(b[i], end="")
if (b_len - i) % 10 == 0:
print(" ", end="")
if (b_len - i) % 50 == 0:
print()
print()
print("z =")
for i in reversed(range(z_len)):
print(z[i], end="")
if (z_len - i) % 10 == 0:
print(" ", end="")
if (z_len - i) % 50 == 0:
print()
print()
except Exception as e:
raise
if __name__ == '__main__':
try:
obj = MultiplyNormal()
obj.compute()
except Exception as e:
traceback.print_exc()
sys.exit(1)
3. Python スクリプトの実行
まず、実行権限を付与。
$ chmod +x multiply_normal.py
そして、実行。
$ ./multiply_normal.py
a =
5769400681 9298577946 3356194219 0179484577 1179807297
7154156873 0997794826 6397077580 4825349834 2375740690
5889459026 8444843484 6011815384 0198074201 5792014755
2014018978 1920056972 9089903998 7404948327 5017922391
3736123520 3375690127 9785617933 9449959132 0975166371
5903029938 1247716582 7967079326 2751830486 8729426481
3777497061 9735049408 1868615454 5492016143 1628784699
9186463248 0402022907 2159742239 0322767444 2178924875
1226305088 8668094530 8548964595 8753396147 7431252021
5177656282 3128781023 1362045538 3908705771 7596990165
4213081425 2615298843 9976094040 3708440022 9605202704
1433237776 1693579438 5627412327 5439398060 7950197307
1628149357 1627627672 3506888804 1713863036 2618161457
9855456166 5568538885 6184911138 4636847757 3563863233
5044333811 7638492195 5771259072 1717980905 6506589965
9734752644 6007526719 0684542893 8023450157 3084748275
6059108564 9292676141 1340827945 6761888783 1546376359
8297022836 7718950210 8564233726 4461487424 4512173931
0301407377 9276559512 5746146957 9935463557 5259884706
6734124151 7586329238 4943367062 8384656044 0765984059
5071128698 3756660756 2578
b =
5177362107 9574511884 2229097997 8973106161 2659649176
5027849779 3037828646 9071494759 0744159611 5310230199
9832631794 5126490175 9487231615 3741211617 3342818373
0206237895 2900484940 1744719906 0902299397 0365685001
5815383345 9232364949 6057292355 4239680552 4838767395
9006697424 7291607599 8685272282 1282909041 3870379584
4387640577 7762687346 6593083530 7667510383 1935959758
9698038845 1051496799 4793436870 1321389122 7678424586
4574343305 4669113031 5301731024 8037986252 5538375143
7747040575 1898225804 0875606589 4654888659 1533331499
5300790397 0989957748 8892160946 8747722899 5268743308
0250154823 3588899301 4837450645 7550047897 3002045696
1485512344 7537886661 4446656335 4406993856 9434468893
8206100631 9628847454 8526616973 2335318763 8299846599
5976151021 8051896217 8363284621 2885319713 8773966249
6873670972 8621988240 9866635609 6862734669 6768117904
1318849324 8582752847 9413066210 2673377723 4729724750
0412380754 2387339662 2333623687 9718884887 9595214566
6807650450 2436322564 0953318934 9055181951 2174139585
7326286471 5189044840 4766730166 7820461161 5077520418
0674516306 1163049715 1090
z =
2987027647 6247524917 2325098959 3923912090 4322968283
5932796406 8954631312 5081457448 5734858018 1496764939
3393694391 3326409084 9995258687 0425898136 1505159531
6028045686 7913349653 6341658075 9490865096 7115362525
9380500313 6863538796 6560109469 8018137146 5600940054
4553487612 4153847041 5506495640 8933922503 4244977127
2256864467 8179069017 1240679485 0942483022 2261940791
3132121499 3405406498 2883691308 3786008854 1048614372
9679427170 9794181702 5936066480 9167094455 5232830672
2877797887 8975636432 9828497153 7930981569 4826011443
9366658527 3752975577 4109372927 1119985840 0560069350
2890669920 9071647713 2770166376 9463367909 0580035936
2860326912 1963514274 3384242840 9215464434 9816418836
7636260106 5250735971 7316451217 2862325775 8553375667
6626789047 5133518247 0146367555 7986421961 9024544187
2340875595 4960502106 4008633157 3943230567 3969581010
6921308474 8089432812 5992373216 3960588678 3513122344
6201643090 7728614388 3254234842 8839031486 4944057903
1836167720 7974310860 7178135628 1392079011 4639971626
3810592042 3525583957 8890183614 3467837181 1224192338
9698160656 1694779463 8787899878 8900439577 2047331975
2047010311 1111415837 2063220240 7643317837 8032615102
4320986156 6125823880 2380771697 5757469285 3644196908
8114990135 3292871171 1526487186 0871184740 5885543600
0244212920 5512252054 7956516595 0187280755 4627654415
8580722936 1239220353 6804719632 4990166647 3945760084
6714126119 9033750581 4877054645 7775608606 0905348333
5202445341 2640180252 2671369985 6495552860 7215980369
4011430052 9752703804 7664219367 7589086704 5897564744
1931389427 4352956960 1637943310 2173127444 7332709957
7261130729 1080986131 7859835313 7765814313 3601607653
8712054732 1763337680 9046631824 0116591038 0235061049
0159763301 4822986274 0370190271 3227991653 5944444929
3764276349 3936528064 1164669790 0982589900 1010689050
4696693901 0741551974 8513358094 3893253627 9176876926
6123938778 4859976573 6694467652 9064653099 2202834742
3030041468 5825267563 7796005234 5471534514 5831508538
7603051031 0605029218 2422541736 8591178891 5481740625
5759489616 7409237986 2975137788 6774054731 7633145700
2240490553 0567953410 9324456553 0941949763 3356313337
4827085213 3483026179 6047070060 0014794778 95910020
以上
Comments