Modular multiplicative inverse in Ruby

Question

I implemented an algorithm to find the modular multiplicative inverse of an integer. The code works, but it is too slow and I don't know why. I compared it with an algorithm I found in Rosetta Code, which is longer but way faster.

My implementation:

def modinv1(a, c)
  raise "#{a} and #{c} are not coprime" unless a.gcd(c) == 1
  0.upto(c - 1).map { |b| (a * b) % c }.index(1)
end

Rosetta Code's implementation:

def modinv2(a, m) # compute a^-1 mod m if possible
  raise "NO INVERSE - #{a} and #{m} not coprime" unless a.gcd(m) == 1
  return m if m == 1
  m0, inv, x0 = m, 1, 0
  while a > 1
    inv -= (a / m) * x0
    a, m = m, a % m
    inv, x0 = x0, inv
  end
  inv += m0 if inv < 0
  inv
end

Benchmark results (used benchmark-ips):

Warming up --------------------------------------
        Rosetta Code   141.248k i/100ms
                Mine   462.000  i/100ms
Calculating -------------------------------------
        Rosetta Code      2.179M (± 6.5%) i/s -     10.876M in   5.022459s
                Mine      4.667k (± 3.7%) i/s -     23.562k in   5.055259s

Comparison:
        Rosetta Code:  2179237.4 i/s
                Mine:     4667.4 i/s - 466.90x  slower

Why is mine so slow? Should I use the one I found in Rosetta Code?

Answer 1

As the comment says on the less-obfuscated version on Rosetta Code, their implementation is based on the Extended Euclidean Algorithm. Your implementation works by brute force to test every element in the field, so of course it's going to be slow.