Incomprehensible Arithmetic errors

Help & Support
1

This ruby file produces correct results for the 2 functions.

modinvtest.rb

def modinv(a0, m0)
  return 1 if m0 == 1
  a, m = a0, m0
  x0, inv = 0, 1
  while a > 1
    inv -= (a / m) * x0
    a, m = m, a % m
    x0, inv = inv, x0
  end
  inv += m0 if inv < 0
  inv
end

def modinv1(r, m)
  inv = r
  while (r * inv) % m != 1; inv *= r end
  inv % m
end

def tm; t = Time.now; yield; Time.now - t end

resp7 = [11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,
          97,101,103,107,109,113,121,127,131,137,139,143,149,151,157,163,
         167,169,173,179,181,187,191,193,197,199,209,211]

print resp7.map { |r| modinv(r, 210) }
puts
print resp7.map { |r| modinv1(r, 210) }
puts
puts tm{ 100000.times {resp7.each { |r| modinv(r, 210) } } }

puts tm{ 100000.times {resp7.each { |r| modinv1(r, 210) } } }

For the equivalent Crystal code, the 2nd version – modinv1 – produces incorrect results for multiple inputs, and if I don’t use &* it gives arithmetic overflow errors.
These number are so small these errors make no sense at all. :frowning_face:

modinvtest.cr

def modinv(a0, m0)
  return 1 if m0 == 1
  a, m = a0, m0
  x0, inv = 0, 1
  while a > 1
    inv -= (a // m) * x0
    a, m = m, a % m
    x0, inv = inv, x0
  end
  inv += m0 if inv < 0
  inv
end

def modinv1(r, m)
  r = inv = r.to_u64
  while (r &* inv) % m != 1; inv &*= r end
  inv % m
end

def tm; t = Time.monotonic; yield; Time.monotonic - t end

resp7 = [11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,
          97,101,103,107,109,113,121,127,131,137,139,143,149,151,157,163,
         167,169,173,179,181,187,191,193,197,199,209,211]

puts resp7.map { |r| modinv(r, 210) }
puts resp7.map { |r| modinv1(r, 210) }

puts tm{ 100000.times {resp7.each { |r| modinv(r, 210) } } }

puts tm{ 100000.times {resp7.each { |r| modinv1(r, 210) } } }
2

If you add:

    if inv > 18446744073709551615
      p inv
    end

right after inv *= r you will see that it would overflow in Crystal, and that’s in fact what happens.

1 Like
3

Oww, this fixed it, and it’s now its almost 3x faster than the first version, a 2fer. :grin:

def modinv1(r, m)
  r = inv = r.to_u64
  while (r * inv) % m != 1; inv %= m; inv *= r end
  #while (r &* inv) % m != 1; inv &*= r end
  inv % m
end
3 Likes
4

For future reference, another way to check the variables to try and figure out the issue is to rescue the overflow error:

def modinv1(r, m)
  r = inv = r.to_u64
  while (r * inv) % m != 1
    inv *= r
  end
  inv % m
rescue
  p! r, inv, (UInt64::MAX / inv.not_nil!)
  exit 1
end

(Not throwing any formatting shade here; my editor just auto-formats with crystal tool format.)

1 Like
5

Thanks for the suggestion.
I was kinda being lazy (OK, was being lazy), because in most cases inv wouldn’t overflow like I thought, but all you need is one. :roll_eyes:

EDIT:
Actually this was serendipitous, because where I use that function forced me to use all u64 types, which eliminates a bunch of x.to_u64 conversions elsewhere. So the code looks better and is faster too. :slightly_smiling_face:

1 Like
6

Types are affecting performance. Sometimes it’s not very obvious.

This fib function

def fib(n)
   return 1_u64 if n <= 1
   fib(n - 1) + fib(n - 2)
 end

Is faster than this one

def fib(n : UInt64)
   return 1_u64 if n <= 1
   fib(n - 1) + fib(n - 2)
 end

when called like fib(46)

It’s interesting to compare the differences in generated ASM code in compiler explorer https://godbolt.org/