Yesterday I ran a Ruby version of my Crystal implementation of the
Miller-Rabin primality test. I was surprised to find Ruby is significantly
faster for the same code with the same inputs.
Here’s the Ruby code.
def prime? (n, k = 4)
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103]
return primes.include? n if n <= primes.last
modpn = 23286236435849736090006331688050736307 # 101# (101 primorial)
return false if modpn.gcd(n) != 1
return true if n < primes.last ** 2
# Start Miller-Rabin primality test
neg_one_mod = t = d = n - 1 # these are even as n is always odd
while d.even?; d >>= 1 end # shift out factors of 2 to make d odd
witnesses = k.times.map{ 2 + rand(n - 4) } # create k random bases
witnesses.each do |b| # perform Miller-Rabin bases tests
y = b.pow(d, n) # y = (b**d) mod n
s = d
until y == 1 || y == neg_one_mod || s == t
y = (y * y) % n # y = (y**2) mod n
s <<= 1
end
return false unless y == neg_one_mod || s.odd?
end
true
end
Here’s the Crystal code.
require "big"
@[Link("gmp")]
lib LibGMP
fun mpz_powm_sec = __gmpz_powm_sec(rop : MPZ*, base : MPZ*, exp : MPZ*, mod : MPZ*)
end
def powmod(b, e, m) # y = b^e mod m
y = BigInt.new
LibGMP.mpz_powm_sec(y, b.to_big_i, e.to_big_i, m.to_big_i)
y
end
def prime? (n, k = 4)
primes = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103]
return primes.includes? n if n <= primes.last
modpn = 232862364358497360900063316880507363070u128.to_big_i # 101# (101 primorial)
return false if modpn.gcd(n.to_big_i) != 1
return true if n < primes.last ** 2
# Start Miller-Rabin primality test
neg_one_mod = t = d = n - 1 # these are even as n is always odd
d >>= d.trailing_zeros_count # shift out factors of 2 to make d odd
witnesses = k.times.map{ 2 + rand(n - 4).to_big_i } # create k random bases
witnesses.each do |b| # perform Miller-Rabin bases tests
y = powmod(b, d, n) # y = (b**d) mod n
s = d
until y == 1 || y == neg_one_mod || s == t
y = (y &* y) % n # y = (y**2) mod n
s <<= 1
end
return false unless y == neg_one_mod || s.odd?
end
true
end
My system
➜ inxi
CPU: 8-core AMD Ryzen 9 5900HX with Radeon Graphics (-MT MCP-)
speed/min/max: 1262/1200/4679 MHz Kernel: 6.1.22-pclos1 x86_64 Up: 11h 2m
Mem: 6124.9/39489.3 MiB (15.5%) Storage: 953.87 GiB (13.0% used) Procs: 349
Shell: Zsh inxi: 3.3.26
Here are some tests I did with various large digit primes.
# Ruby tests
# $ ruby testfile.rb
def tm; t = Time.now; yield; Time.now - t end
#n = (70965694293 << 200006) - 1 # 60,219 digits
#n = (4111286921397 << 66420) + 5 # 20,008 digits
#n = (4122429552750669 << 16567) + 7 # 5,003 digits
n = (12379 << 12379) - 1 # 3,731 digits
print "\n number = #{n} is prime? "; print " in ", tm{ print prime?(n) }, " secs"
puts
# Crystal tests
# $ crystal run --release testfile.cr
def tm; t=Time.monotonic; yield; (Time.monotonic-t).total_seconds.round(3) end
#n = ("70965694293".to_big_i << 200006) - 1 # 60,219 digits
#n = ("4111286921397".to_big_i << 66420) + 5 # 20,008 digits
#n = ("4122429552750669".to_big_i << 16567) + 7 # 5,003 digits
n = ("12379".to_big_i << 12379) - 1 # 3,731 digits
print "\n number = #{n} is prime? "; print " in ", tm{ print prime?(n) }, " secs"
put
Best times after multiple runs.
Ruby gets progressively faster (or Crystal slower) as the prime digits increase.
Prime Digits | 3,731 | 5,003 | 20,008 | 60,219 |
--------------|-------|--------|------- -|----------|
Ruby 3.2.2 | 0.959 | 1.693 | 49.001 | 727.575 |
--------------|-------|--------|-------- |----------|
Crystal 1.7.3 | 1.843 | 4.423 | 279.322 | 7600.197 |
This was a big surprise, as I hadn’t run this code in Ruby in a while.
This shows Ruby’s efforts to increase performance has paid off, at least here.
But what’s really concerning is that the performance difference isn’t constant,
but Crystal becomes increasingly relatively slower as the prime digits increase.
I suspect it has to do with the BigInts implementation, as Ruby automatically
uses the appropriate integer type and memory as needed.
So, can the Crystal version be significantly sped up?
(FYI, when I run the Ruby code with TruffleRuby and JRuby it’s slower than Crystal.)
