Contents

# Copyright (c) 2007, 2008 Pythonic Pty Ltd
# http://www.pythonic.com.au/

class Integer
  # Returns modular multiplicative inverse.
  # Examples:
  #   2.inverse(7) # => 4
  #   4.inverse(7) # => 2
  def inverse(m)
    u, v = m, self
    x, y = 0, 1
    while v != 0
      q, r = u.divmod(v)
      x, y = y, x - q * y
      u, v = v, r
    end
    if u.abs == 1
      x < 0 ? x + m : x
    end
  end
end

Version data entries

15 entries across 15 versions & 1 rubygems

Version	Path
acts_as_nested_interval-0.3.0.pre	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.2.0	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.2.0.pre2	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.2.0.pre	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.1.1	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.1.0	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.0.10	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.0.9	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.0.8	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.0.7	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.0.6	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.0.5	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.0.4	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.0.2	lib/acts_as_nested_interval/core_ext/integer.rb
acts_as_nested_interval-0.0.1	lib/acts_as_nested_interval/core_ext/integer.rb