-
Notifications
You must be signed in to change notification settings - Fork 0
/
Karatsuba.py
103 lines (88 loc) · 2.87 KB
/
Karatsuba.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
import math
def karatsuba(x, y, stat):
n_x = int(math.log10(x) + 1) if x > 0 else 1
n_y = int(math.log10(y) + 1) if y > 0 else 1
n = n_x if n_x > n_y else n_y
n = n if n % 2 == 0 else n + 1
half_bit = pow(10, n / 2)
full_bit = pow(10, n)
a = x / half_bit
b = x - a * half_bit
c = y / half_bit
d = y - c * half_bit
ac = check_overflow(a, c, stat)
bd = check_overflow(b, d, stat)
apb = a + b
cpd = c + d
ad_p_bc = check_overflow(apb, cpd, stat) - ac - bd
if ad_p_bc in stat:
stat[ad_p_bc] += 1
else:
stat[ad_p_bc] = 1
return full_bit * ac + half_bit * ad_p_bc + bd
def check_overflow(val_a, val_c, stat):
if val_a < 10 and val_c < 10:
return val_a * val_c
else:
return karatsuba(val_a, val_c, stat)
def run_test(x_val, y_val, correct_result):
statistics = dict()
result = karatsuba(x_val, y_val, statistics)
print "Result %d is correct: %s" % (result, result == correct_result)
for k in sorted(statistics):
if statistics[k] != 1:
print "%d: %d times" % (k, statistics[k])
tests = [
[
49823261,
44269423,
2205647016448403
],
[
54761293,
65394884,
3581108403425012
],
[
9313685456934674,
7658898761837539,
71332574014261268360454523927286
],
[
3957322621234423,
7748313756335578,
30662577304368647842211393201494
],
[
34215432964249374812219364786397,
94541964835273822784327848699719,
3234794260129733170788831535430575611379062580407060392628922443
],
[
71611955325935479159397713213124,
93567726499788166681348352945366,
6700567850052179472481148730882040129649508491917840721086183384
],
[
8436939677358274975644341226884162349535836199962392872868456892,
3864264464372346883776335161325428226997417338413342945574123327,
32602566183268675582196165592691544162522778809155901895617284287276672563976841699892789718741377833554298336397153444191119684
],
[
8711129198194917883527844183686122989894424943636426448417394566,
2924825637132661199799711722273977411715641477832758942277358764,
25478534007255378799894857247961445544397925869179138904636157575535921570058983065006369481295619500406669960288667484926076424
],
[
21625695688898558125310188636840316594920403182768,
13306827740879180856696800391510469038934180115260,
287769407308846640970310151509826255482575362419155842891311909556878670000425352112987881085839680
],
[
1685287499328328297814655639278583667919355849391453456921116729,
7114192848577754587969744626558571536728983167954552999895348492,
0
]
]
for i in range(0, len(tests)):
run_test(tests[i][0], tests[i][1], tests[i][2])