Lessons from the Trenches: Use of [U]Int128

jzakiya · November 21, 2022, 5:33pm

I’ve been updating old (2018/9) code to 1.6.2, to use its newer/better features, and thought I’d share this observation.

I’m updating highly computationally intense numerical algorithms that can operate on BiG numbers. Before when limited to [U]Int64s (20|19 digits) I had to use BigInts to process numbers outside their range. But BigInts are much slower than [U]Ints

Now that Crystal supports [U]Ints128s (39|38 digits) using them to replace BigInts can be a significant speedup, especially inside loops you know have bounded upper values inside their range.

So look at where you use BigInts in your code and determine if you can replace them with [U]Int128s, and in general include their support in your code|libraries as well, if appropriate.

yxhuvud · November 21, 2022, 5:42pm

And be sure to report any issues that are found on the github issue tracker. It is not unlikely that some corner cases where missed in the implementation :)

jzakiya · November 21, 2022, 7:43pm

Ah yes…too good to be true.

I just changed some BigInts in places they could be UInt[64|128] and all hell broke loose.

It seems to mess with this code.

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

Get --error-trace messages like:

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)

I’ll keep playing with it to see if I can cleanly reduce it to one thing.

asterite · November 21, 2022, 7:57pm

That’s a bug. Could you please report it? Calling -other when a number is negative is not the best thing to do. The best thing to do is to call abs on it, which is guaranteed to work on unsigned numbers (you can’t change the sign of an unsigned number though!)

straight-shoota · November 21, 2022, 8:10pm

Yes, that’s a trivial bug. Also trivial to fix:

--- i/src/big/big_int.cr
+++ w/src/big/big_int.cr
@@ -253,7 +253,7 @@ struct BigInt < Int
     check_division_by_zero other

     if other < 0
-      -(-self).unsafe_floored_mod(-other)
+      -(-self).unsafe_floored_mod(other.abs)
     else
       unsafe_floored_mod(other)
     end

jzakiya · November 21, 2022, 8:20pm

I just filed an issue and included the total code which generated the errors.

github.com/crystal-lang/crystal

Error when switching for usin BigInts to [U|Int[64|128]

opened 08:18PM - 21 Nov 22 UTC

jzakiya

kind:bug

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.