`BigInt#gcd(Int::Primitive)` returns a union

[HertzDevil]

require "big"

typeof(1.to_big_i.gcd(1)) # => (BigInt | UInt64)

This happens because BigInt#gcd(Int) is defined as:

struct BigInt
  # a more specialized overload accepts `BigInt` arguments, so
  # this overload is effectively only used for `Int::Primitive`
  def gcd(other : Int) : Int
    result = LibGMP.gcd_ui(nil, self, other.abs.to_u64)
    result == 0 ? self : result
  end
end

The original intent seems to be that one can avoid allocating a BigInt if other is small enough and non-zero, but this union type is inconsistent with pretty much every other numeric operation where non-union inputs should produce non-union outputs.

I think this method should simply return BigInt at all times. The old behavior can be obtained by other.class.new((self % other).gcd(other)).

[jzakiya]

I agree it should be just one type. But it could also be the type of the smallest value, as the answer has to fit within it.

However in many cases when doing using gcd you don't care what the value is. You're really testing if the values are coprime i.e. if gcd(a,b) == 1.

It would really be nice to have an optimized coprime?(a, b) method that returns true|false. That would certainly cleanup allot of my code, and make it more readable, by explicitly naming what you're doing.

[straight-shoota]

I think using the smaller type could be good for this. That would make it different from most other methods, but it makes sense for gcd logic.

[HertzDevil]

Using the smaller type would overflow when that smaller argument is 0 and the other argument exceeds the smaller type's range, e.g. 0_i8.gcd(150_i32)

[jzakiya]

Having "0" as an argument into a gcd is an edge case, which some algorithms handle differently.

For this gcd calculator, https://calculating-it.com/math-calculators/common-denominator/ if you put the values of 0 and 152 in, it returns 152, which would be greater than an Int8 (but fit in an UInt8). But I've seen some set that answer to 0 (no greatest common divisor) or even 1. Sometimes it just depends on how (if) the algorithm wants to allow using 0, and/or handle it.

However that edge case is the only time (potentially) the answer could not fit in the smallest value type.

Usually in real algorithms, if you want the value of a gcd (versus testing if coprime) you want to use it to make some other calculation with, and you know that value is < the smallest input value. So either the algorithm ensures no input is 0, or the implementation handles it in a documented way.

Another thing to consider is, because currently there is no .to_(u|i)128 method for BigInts that causes problems if you want a (u|i)128 type to use doing your math with. But you can always do a gcd(a,b).to_big_i if you need to, or make a and b be BigInts to give an answer of that type. But again, doing math with BigInts is slower than with primitive types, so you want to avoid using them when you can.