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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
|
require 'test/unit'
require "-test-/bignum"
class TestBignum < Test::Unit::TestCase
class TestMul < Test::Unit::TestCase
SIZEOF_BDIGIT = Bignum::SIZEOF_BDIGIT
BITSPERDIG = Bignum::BITSPERDIG
BDIGMAX = (1 << BITSPERDIG) - 1
def test_mul_normal
x = (1 << BITSPERDIG) | 1
y = (1 << BITSPERDIG) | 1
z = (1 << (BITSPERDIG*2)) | (2 << BITSPERDIG) | 1
assert_equal(z, x.big_mul_normal(y))
end
def test_mul_normal_zero_in_x
x = (1 << (2*BITSPERDIG)) | 1
y = (1 << BITSPERDIG) | 1
z = (1 << (BITSPERDIG*3)) | (1 << (BITSPERDIG*2)) | (1 << BITSPERDIG) | 1
assert_equal(z, x.big_mul_normal(y))
end
def test_mul_normal_zero_in_y
x = (1 << BITSPERDIG) | 1
y = (1 << (2*BITSPERDIG)) | 1
z = (1 << (BITSPERDIG*3)) | (1 << (BITSPERDIG*2)) | (1 << BITSPERDIG) | 1
assert_equal(z, x.big_mul_normal(y))
end
def test_mul_normal_max_max
x = (1 << (2*BITSPERDIG)) - 1
y = (1 << (2*BITSPERDIG)) - 1
z = (1 << (4*BITSPERDIG)) - (1 << (2*BITSPERDIG+1)) + 1
assert_equal(z, x.big_mul_normal(y))
end
def test_sq_fast
x = (1 << BITSPERDIG) | 1
z = (1 << 2*BITSPERDIG) | (2 << BITSPERDIG) | 1
assert_equal(z, x.big_sq_fast)
end
def test_sq_fast_max2
x = (BDIGMAX << BITSPERDIG) | BDIGMAX
assert_equal(x.big_mul_normal(x), x.big_sq_fast)
end
def test_sq_fast_zero_in_middle
x = (BDIGMAX << 2*BITSPERDIG) | BDIGMAX
assert_equal(x.big_mul_normal(x), x.big_sq_fast)
end
def test_mul_balance
x = (1 << BITSPERDIG) | 1
y = (1 << BITSPERDIG) | 1
z = (1 << (BITSPERDIG*2)) | (2 << BITSPERDIG) | 1
assert_equal(z, x.big_mul_balance(y))
end
def test_mul_balance_2x16
x = (1 << Bignum::BITSPERDIG) | 1
y = (1 << Bignum::BITSPERDIG*16) | 1
assert_equal(x.big_mul_normal(y), x.big_mul_balance(y))
end
def test_mul_balance_2x17
x = (1 << Bignum::BITSPERDIG) | 1
y = (1 << Bignum::BITSPERDIG*17) | 1
assert_equal(x.big_mul_normal(y), x.big_mul_balance(y))
end
def test_mul_karatsuba
x = (1 << BITSPERDIG) | 1
y = (1 << BITSPERDIG) | 1
z = (1 << (BITSPERDIG*2)) | (2 << BITSPERDIG) | 1
assert_equal(z, x.big_mul_karatsuba(y))
end
def test_mul_karatsuba_odd_y
x = (1 << BITSPERDIG) | 1
y = (1 << (2*BITSPERDIG)) | 1
assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
end
def test_mul_karatsuba_odd_xy
x = (1 << (2*BITSPERDIG)) | 1
y = (1 << (2*BITSPERDIG)) | 1
assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
end
def test_mul_karatsuba_x1_gt_x0
x = (2 << BITSPERDIG) | 1
y = (1 << BITSPERDIG) | 2
assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
end
def test_mul_karatsuba_y1_gt_y0
x = (1 << BITSPERDIG) | 2
y = (2 << BITSPERDIG) | 1
assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
end
def test_mul_karatsuba_x1_gt_x0_and_y1_gt_y0
x = (2 << BITSPERDIG) | 1
y = (2 << BITSPERDIG) | 1
assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
end
def test_mul_karatsuba_carry2
x = (1 << BITSPERDIG) | BDIGMAX
y = (1 << BITSPERDIG) | BDIGMAX
assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
end
def test_mul_karatsuba_borrow
x = (BDIGMAX << BITSPERDIG) | 1
y = (BDIGMAX << BITSPERDIG) | 1
assert_equal(x.big_mul_normal(y), x.big_mul_karatsuba(y))
end
def test_mul_toom3
x = (1 << 2*BITSPERDIG) | (1 << BITSPERDIG) | 1
y = (1 << 2*BITSPERDIG) | (1 << BITSPERDIG) | 1
assert_equal(x.big_mul_normal(y), x.big_mul_toom3(y))
end
def test_mul_gmp
x = (1 << 2*BITSPERDIG) | (1 << BITSPERDIG) | 1
y = (1 << 2*BITSPERDIG) | (1 << BITSPERDIG) | 1
assert_equal(x.big_mul_normal(y), x.big_mul_gmp(y))
rescue NotImplementedError
end
end
end
|
