Per the issue raised in forum here:
https://forum.crystal-lang.org/t/lessons-fr…om-the-trenches-use-of-u-int128/5127
When converting BigInts to U|Ints64|128 in old working code various error start to occur.
This code is one place that's marked.
```
# Compute b**x mod m
private def powmod(b, e, m)
r = 1.to_big_i; b = b.to_big_i % m
while e > 0
r = (r * b) % m if e.odd?
b = (b * b) % m
e >>= 1
end
r
end
```
Here are some error messages.
```
In mrtest3a.cr:24:13
24 | y = powmod(b, d, self) # y = (b**d) mod self
^-----
Error: instantiating 'powmod(Int32, UInt64, UInt64)'
In mrtest3a.cr:37:38
37 | r = 1.to_big_i; b = b.to_big_i % m
^
Error: instantiating 'BigInt#%(UInt64)'
n /home/jzakiya/crystal/share/crystal/src/big/big_int.cr:256:35
256 | -(-self).unsafe_floored_mod(-other)
^
Error: wrong number of arguments for 'UInt64#-' (given 0, expected 1)
Overloads are:
- UInt64#-(other : Int8)
- UInt64#-(other : Int16)
- UInt64#-(other : Int32)
- UInt64#-(other : Int64)
- UInt64#-(other : Int128)
- UInt64#-(other : UInt8)
- UInt64#-(other : UInt16)
- UInt64#-(other : UInt32)
- UInt64#-(other : UInt64)
- UInt64#-(other : UInt128)
- UInt64#-(other : Float32)
- UInt64#-(other : Float64)
- Int#-(other : BigInt)
- Int#-(other : BigRational)
- Int#-(other : BigDecimal)
- Number#-(other : BigFloat)
```
Here's the whole file, which does the Miller-Rabin primality test in Crystal.
```
require "big"
module Primes
module MillerRabin
# Returns true if +self+ is a prime number, else returns false.
def primemr? (k = 10)
primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47}
return primes.includes? self if self <= primes.last
return false if 614_889_782_588_491_410.to_big_i.gcd(self.to_big_i) != 1
# wits = [range, [wit_prms]] or nil
wits = WITNESS_RANGES.find { |range, wits| range > self }
witnesses = wits && wits[1] || k.times.map{ 2 + rand(self - 4) }
miller_rabin_test(witnesses)
end
# Returns true if +self+ passes Miller-Rabin Test on witnesses +b+
private def miller_rabin_test(witnesses)
neg_one_mod = n = d = self - 1
d >>= d.trailing_zeros_count
witnesses.each do |b|
next if (b % self) == 0
#next if b.divisible_by? self
y = powmod(b, d, self)
s = d
until y == 1 || y == neg_one_mod || s == n
y = (y &* y) % self
s <<= 1
end
return false unless y == neg_one_mod || s.odd?
end
true
end
# Compute b**x mod m
private def powmod(b, e, m)
r = 1.to_big_i; b = b.to_big_i % m
while e > 0
r = (r * b) % m if e.odd?
b = (b * b) % m
e >>= 1
end
r
end
# Best known deterministic witnesses for given range and set of bases
# https://miller-rabin.appspot.com/
# https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_te
private WITNESS_RANGES = {
341_531 => {9345883071009581737u64},
1_050_535_501 => {336781006125u64, 9639812373923155u64},
350_269_456_337 => {4230279247111683200u64, 14694767155120705706u64, 16641139526367750375u64},
55_245_642_489_451 => {2u64, 141889084524735u64, 1199124725622454117u64, 11096072698276303650u64},
7_999_252_175_582_851 => {2u64, 4130806001517u64, 149795463772692060u64, 186635894390467037u64, 3967304179347715805u64},
585_226_005_592_931_977 => {2u64, 123635709730000u64, 9233062284813009u64, 43835965440333360u64, 761179012939631437u64, 1263739024124850375u64},
18_446_744_073_709_551_615u64 => {2, 325, 9375, 28178, 450775, 9780504, 1795265022},
"318665857834031151167461".to_big_i => {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37},
"3317044064679887385961981".to_big_i => {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41}
}
end
end
struct Int; include Primes::MillerRabin end
def tm; t = Time.monotonic; yield; Time.monotonic - t end
# 10 digit primes
n = 2147483647
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts
# 18 digit non-prime
n = 844674407370955389
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts
# 19 digit primes
#n = "9241386435364257883".to_big_i
n = 9241386435364257883u64
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts
# 20 digit primes; largest < 2^64
n = "18446744073709551533".to_big_i
print "\n number = #{n} is prime? "; print " in ", tm{ print n.primemr? }, " secs"
puts
```
Also in the method `miller_rabin_test` when I replaced `next if (b % self) == 0` with `next if b.divisible_by? self`
I get errors too.
