summaryrefslogtreecommitdiff
path: root/test/-ext-/bignum/test_mul.rb
blob: 539b9cf13827924c597b4eef57a2b427fce5481a (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
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_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