Class: ModInt

Inherits:
Numeric
  • Object
show all
Defined in:
lib/modint.rb

Overview

ModInt

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(val = 0) ⇒ ModInt

Returns a new instance of ModInt.



68
69
70
 
# File 'lib/modint.rb', line 68

def initialize(val = 0)
  @val = val.to_i % $_mod
end

Instance Attribute Details

#val ⇒ Object Also known as: to_i

Returns the value of attribute val.



64
65
66
 
# File 'lib/modint.rb', line 64

def val
  @val
end

Class Method Details

.inv_gcd(a, b) ⇒ Object 



46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
 
# File 'lib/modint.rb', line 46

def inv_gcd(a, b)
  a %= b
  return [b, 0] if a == 0

  s, t = b, a
  m0, m1 = 0, 1
  while t != 0
    u = s / t
    s -= t * u
    m0 -= m1 * u
    s, t = t, s
    m0, m1 = m1, m0
  end
  m0 += b / s if m0 < 0
  [s, m0]
end

.mod ⇒ Object 



17
18
19
 
# File 'lib/modint.rb', line 17

def mod
  $_mod
end

.mod=(mod) ⇒ Object 



13
14
15
 
# File 'lib/modint.rb', line 13

def mod=(mod)
  set_mod mod
end

.prime?(n) ⇒ Boolean

Returns:

  • (Boolean) 


27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
 
# File 'lib/modint.rb', line 27

def prime?(n)
  return false if n <= 1
  return true if (n == 2) || (n == 7) || (n == 61)
  return false if (n & 1) == 0

  d = n - 1
  d >>= 1 while (d & 1) == 0
  [2, 7, 61].each do |a|
    t = d
    y = a.pow(t, n)
    while (t != n - 1) && (y != 1) && (y != n - 1)
      y = y * y % n
      t <<= 1
    end
    return false if (y != n - 1) && ((t & 1) == 0)
  end
  true
end

.raw(val) ⇒ Object 



21
22
23
24
25
 
# File 'lib/modint.rb', line 21

def raw(val)
  x = allocate
  x.val = val.to_i
  x
end

.set_mod(mod) ⇒ Object

Raises:

  • (ArgumentError) 


6
7
8
9
10
11
 
# File 'lib/modint.rb', line 6

def set_mod(mod)
  raise ArgumentError unless mod.is_a?(Integer) && (1 <= mod)

  $_mod = mod
  $_mod_is_prime = ModInt.prime?(mod)
end

Instance Method Details

#*(other) ⇒ Object 



132
133
134
 
# File 'lib/modint.rb', line 132

def *(other)
  dup.mul! other
end

#**(other) ⇒ Object Also known as: pow 



111
112
113
 
# File 'lib/modint.rb', line 111

def **(other)
  $_mod == 1 ? 0 : ModInt.raw(@val.pow(other, $_mod))
end

#+(other) ⇒ Object 



124
125
126
 
# File 'lib/modint.rb', line 124

def +(other)
  dup.add! other
end

#+@ ⇒ Object 



103
104
105
 
# File 'lib/modint.rb', line 103

def +@
  self
end

#-(other) ⇒ Object 



128
129
130
 
# File 'lib/modint.rb', line 128

def -(other)
  dup.sub! other
end

#-@ ⇒ Object 



107
108
109
 
# File 'lib/modint.rb', line 107

def -@
  ModInt.raw($_mod - @val)
end

#/(other) ⇒ Object 



136
137
138
 
# File 'lib/modint.rb', line 136

def /(other)
  dup.div! other
end

#==(other) ⇒ Object 



140
141
142
 
# File 'lib/modint.rb', line 140

def ==(other)
  @val == other.to_i
end

#add!(other) ⇒ Object 



84
85
86
87
 
# File 'lib/modint.rb', line 84

def add!(other)
  @val = (@val + other.to_i) % $_mod
  self
end

#coerce(other) ⇒ Object 



120
121
122
 
# File 'lib/modint.rb', line 120

def coerce(other)
  [ModInt(other), self]
end

#dec! ⇒ Object 



78
79
80
81
82
 
# File 'lib/modint.rb', line 78

def dec!
  @val = $_mod if @val == 0
  @val -= 1
  self
end

#div!(other) ⇒ Object 



99
100
101
 
# File 'lib/modint.rb', line 99

def div!(other)
  mul! inv_internal(other.to_i)
end

#dup ⇒ Object 



156
157
158
 
# File 'lib/modint.rb', line 156

def dup
  ModInt.raw(@val)
end

#inc! ⇒ Object 



72
73
74
75
76
 
# File 'lib/modint.rb', line 72

def inc!
  @val += 1
  @val = 0 if @val == $_mod
  self
end

#inspect ⇒ Object 



168
169
170
 
# File 'lib/modint.rb', line 168

def inspect
  "#{@val} mod #{$_mod}"
end

#inv ⇒ Object 



116
117
118
 
# File 'lib/modint.rb', line 116

def inv
  ModInt.raw(inv_internal(@val) % $_mod)
end

#mul!(other) ⇒ Object 



94
95
96
97
 
# File 'lib/modint.rb', line 94

def mul!(other)
  @val = @val * other.to_i % $_mod
  self
end

#pred ⇒ Object 



144
145
146
 
# File 'lib/modint.rb', line 144

def pred
  dup.add!(-1)
end

#sub!(other) ⇒ Object 



89
90
91
92
 
# File 'lib/modint.rb', line 89

def sub!(other)
  @val = (@val - other.to_i) % $_mod
  self
end

#succ ⇒ Object 



148
149
150
 
# File 'lib/modint.rb', line 148

def succ
  dup.add! 1
end

#to_int ⇒ Object 



160
161
162
 
# File 'lib/modint.rb', line 160

def to_int
  @val
end

#to_s ⇒ Object 



164
165
166
 
# File 'lib/modint.rb', line 164

def to_s
  @val.to_s
end

#zero? ⇒ Boolean

Returns:

  • (Boolean) 


152
153
154
 
# File 'lib/modint.rb', line 152

def zero?
  @val == 0
end