crystal-lang · Jul 25, 2016 · Jul 25, 2016
Showing with 56 additions and 0 deletions.

+24 −0 spec/std/big/big_int_spec.cr

+25 −0 src/big/big_int.cr

+7 −0 src/big/lib_gmp.cr
diff --git a/spec/std/big/big_int_spec.cr b/spec/std/big/big_int_spec.cr
@@ -179,6 +179,30 @@ describe "BigInt" do
     a.to_s(32).should eq(d)
   end
 
+  it "does gcd and lcm" do
+    # 3 primes
+    a = BigInt.new("48112959837082048697")
+    b = BigInt.new("12764787846358441471")
+    c = BigInt.new("36413321723440003717")
+    abc = a * b * c
+    a_17 = a * 17
+
+    (abc * b).gcd(abc * c).should eq(abc)
+    (abc * b).lcm(abc * c).should eq(abc * b * c)
+    (abc * b).gcd(abc * c).should be_a(BigInt)
+
+    (a_17).gcd(17).should eq(17)
+    (17).gcd(a_17).should eq(17)
+    (-a_17).gcd(17).should eq(17)
+    (-17).gcd(a_17).should eq(17)
+
+    (a_17).gcd(17).should be_a(Int::Unsigned)
+    (17).gcd(a_17).should be_a(Int::Unsigned)
+
+    (a_17).lcm(17).should eq(a_17)
+    (17).lcm(a_17).should eq(a_17)
+  end
+
   it "can use Number::[]" do
     a = BigInt[146, "3464", 97, "545"]
     b = [BigInt.new(146), BigInt.new(3464), BigInt.new(97), BigInt.new(545)]

diff --git a/src/big/big_int.cr b/src/big/big_int.cr
@@ -201,6 +201,23 @@ struct BigInt < Int
     BigInt.new { |mpz| LibGMP.pow_ui(mpz, self, other) }
   end
 
+  def gcd(other : BigInt) : BigInt
+    BigInt.new { |mpz| LibGMP.gcd(mpz, self, other) }
+  end
+
+  def gcd(other : Int) : Int
+    result = LibGMP.gcd_ui(nil, self, other.abs.to_u64)
+    result == 0 ? self : result
+  end
+
+  def lcm(other : BigInt) : BigInt
+    BigInt.new { |mpz| LibGMP.lcm(mpz, self, other) }
+  end
+
+  def lcm(other : Int) : BigInt
+    BigInt.new { |mpz| LibGMP.lcm_ui(mpz, self, other.abs.to_u64) }
+  end
+
   def inspect
     to_s
   end
@@ -366,6 +383,14 @@ struct Int
     to_big_i % other
   end
 
+  def gcm(other : BigInt) : Int
+    other.gcm(self)
+  end
+
+  def lcm(other : BigInt) : BigInt
+    other.lcm(self)
+  end
+
   # Returns a BigInt representing this integer.
   def to_big_i : BigInt
     BigInt.new(self)

diff --git a/src/big/lib_gmp.cr b/src/big/lib_gmp.cr
@@ -84,6 +84,13 @@ lib LibGMP
   fun cmp_ui = __gmpz_cmp_ui(op1 : MPZ*, op2 : ULong) : Int
   fun cmp_d = __gmpz_cmp_d(op1 : MPZ*, op2 : Double) : Int
 
+  # # Number Theoretic Functions
+
+  fun gcd = __gmpz_gcd(rop : MPZ*, op1 : MPZ*, op2 : MPZ*)
+  fun gcd_ui = __gmpz_gcd_ui(rop : MPZ*, op1 : MPZ*, op2 : ULong) : ULong
+  fun lcm = __gmpz_lcm(rop : MPZ*, op1 : MPZ*, op2 : MPZ*)
+  fun lcm_ui = __gmpz_lcm_ui(rop : MPZ*, op1 : MPZ*, op2 : ULong)
+
   # MPQ
   struct MPQ
     _mp_num : MPZ