Lessons from the Trenches: Use of [U]Int128

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.


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 :)

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. :face_exhaling:

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

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.

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!)

1 Like

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)

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