➜ ~ crystal -v
Crystal 0.35.1 [5999ae29b] (2020-06-19)
LLVM: 8.0.0
Default target: x86_64-unknown-linux-gnu
Intel Core i7-6700HQ bits: 64 type: 4C/8T; 800/3500 MHz
I ran a comparison of doing a primalitytest on the same prime value of type u64 and BigInt, and BigInt value was substantially slower than the u64 value.
Does his expose an inefficient implementation of BigInt by Crystal, or this an inherent characteristic to be expected (lived with)?
I would have assumed BigInt would check to see if the value could be represented by the system architecture before translating it to another format.
Also, when running the testcode, I see using htop, for the u64 value the process runs on a single thread close to the max system clock freq until finished, but for BigInt the process is spread over the (8) threads at much lower freqs.
#primetest.cr
require "big"
def prime?(n) # P3 Prime Generator primality test
return n | 1 == 3 if n < 5 # n: 2,3|true; 0,1,4|false
return false if n.gcd(6) != 1 # this filters out 2/3 of all integers
pc = typeof(n).new(5) # first P3 prime candidates sequence value
until pc*pc > n
return false if n % pc == 0 || n % (pc + 2) == 0 # if n is composite
pc += 6 # 1st prime candidate for next residues group
end
true
end
def prime1?(n) # P3 Prime Generator primality test
return n | 1 == 3 if n < 5 # n: 2,3|true; 0,1,4|false
return false if n.gcd(6) != 1 # this filters out 2/3 of all integers
pc = typeof(n).new(5) # first P3 prime candidates sequence value
sqrtN = typeof(n).new(Math.sqrt(n))
until pc > sqrtN
return false if n % pc == 0 || n % (pc + 2) == 0 # if n is composite
pc += 6 # 1st prime candidate for next residues group
end
true
end
def tm; t = Time.monotonic; yield; Time.monotonic - t end
# 20 digit prime
n = 12345678901234567891u64 # u64 value
print "\n number = #{n} is prime "; print " in ", tm{ print prime?(n) }, " secs"
print "\n number = #{n} is prime "; print " in ", tm{ print prime1?(n) }, " secs"
puts
# 20 digit prime
n = "12345678901234567891".to_big_i # BigInt vaue
print "\n number = #{n} is prime "; print " in ", tm{ print prime?(n) }, " secs"
print "\n number = #{n} is prime "; print " in ", tm{ print prime1?(n) }, " secs"
puts
Timing results.
# For u64
number = 12345678901234567891 is prime true in 00:00:10.394791582 secs
number = 12345678901234567891 is prime true in 00:00:09.589179257 secs
# For BigInt
number = 12345678901234567891 is prime true in 00:01:58.417328276 secs
number = 12345678901234567891 is prime true in 00:01:38.544755966 secs
9/10 to 98/118 seconds is a big 10x+ unexpected difference for the same value.
