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
|
require 'test/unit'
require "-test-/bignum"
class TestBignum < Test::Unit::TestCase
class TestMul < Test::Unit::TestCase
SIZEOF_BDIGITS = Bignum::SIZEOF_BDIGITS
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_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
end
end
|