summaryrefslogtreecommitdiff
path: root/jni/ruby/test/-ext-/bignum/test_mul.rb
blob: 3e78247aa45d2ce43a4ff90d2dd39a504cbfd246 (plain)
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