Chinese Remainder Theorem in Ruby

I needed it in Advent of Code 2020 Day 13, so I ported it to Ruby by referring to the information that came out. For details on the algorithm, see Kenchon's article.

If you write roughly what you can do, It can be used when you want to find "a number that is 2 when divided by 3, 8 when divided by 10, and 9 when divided by 31".

code

Pass an array of remainders (b) and divisions (m) to the crt method. If the return value is (r, m), then the solution is x ≡ r (mod m).

def ext_gcd(a, b, values)
  d = a

  if b.zero?
    values[:x] = 1
    values[:y] = 0
  else
    d = ext_gcd(b, a % b, values)

    x = values[:x]
    y = values[:y]
    values[:x] = y
    values[:y] = x - (a / b) * y
  end

  d
end

def crt(b, m)
  r = 0
  mM = 1
  b.zip(m) do |bi, mi|
    val = {}
    d = extgcd_h(mM, mi, val)
    p = val[:x]
    q = val[:y]
    return [0, -1] if (bi - r) % d != 0
    tmp = (bi - r) / d * p % (mi / d)
    r += mM * tmp
    mM *= mi / d
  end

  [r % mM, mM]
end

Usage example

Divide by 19 and get over 0, Divide by 37 and over 24, When you want to find a number that is more than 504 divided by 523

b = [0, 24, 504]
m = [19, 37, 523]
ans = crt(b, m) # => [317965, 367669]

The answer is 367669n + 317965 with n as an integer. The minimum natural number that satisfies the condition is 317965.

Referenced site

Recommended Posts

Chinese Remainder Theorem in Ruby
Heavy in Ruby! ??
About eval in Ruby
Fast popcount in Ruby
ABC177 --solving E in Ruby
Validate JWT token in Ruby
Implemented XPath 1.0 parser in Ruby
Read design patterns in Ruby
Write class inheritance in Ruby
Integer unified into Integer in Ruby 2.4
Multiplication in a Ruby array
About regular expressions in Ruby
Birthday attack calculation in Ruby
Judgment of fractions in Ruby
Find Roman numerals in Ruby
Try using gRPC in Ruby
NCk mod p in Ruby
Sorting hashes in a Ruby array
Basics of sending Gmail in Ruby
How to iterate infinitely in Ruby
Achieve 3-digit delimited display in Ruby
Encoding when getting in Windows + Ruby
Run GraphQL Ruby resolver in parallel
Ruby on Rails Japanese-English support i18n
[Ruby] Extracting double hash in array
String output method memo in Ruby
Implement a gRPC client in Ruby
I wrote Goldbach's theorem in java
Write keys and values in Ruby
[Super Introduction] About Symbols in Ruby
Hanachan in Ruby (non-destructive array manipulation)
Manipulating data in GCS during Ruby
Is there no type in Ruby?
openssl version information in ruby OPENSSL_VERSION
Ruby methods often used in Rails
Make Ruby segfault in two lines