Add GCD function for integers (of all flavors)

2 files changed, 28 insertions, 0 deletions

diff --git a/stdlib/integers.c b/stdlib/integers.c
index 42345618..33e967cb 100644
--- a/stdlib/integers.c
+++ b/stdlib/integers.c
@@ -304,6 +304,22 @@ public Int_t Int$power(Int_t base, Int_t exponent)
     return Int$from_mpz(result);
 }
 
+public Int_t Int$gcd(Int_t x, Int_t y)
+{
+    if (likely(x.small & y.small & 0x1))
+        return I_small(Int32$gcd(x.small >> 2, y.small >> 2));
+
+    mpz_t result;
+    mpz_init(result);
+    if (x.small & 0x1)
+        mpz_gcd_ui(result, *y.big, (uint64_t)labs(x.small>>2));
+    else if (y.small & 0x1)
+        mpz_gcd_ui(result, *x.big, (uint64_t)labs(y.small>>2));
+    else
+        mpz_gcd(result, *x.big, *y.big);
+    return Int$from_mpz(result);
+}
+
 public OptionalInt_t Int$sqrt(Int_t i)
 {
     if (Int$compare_value(i, I(0)) < 0)
@@ -510,6 +526,16 @@ public void Int32$deserialize(FILE *in, void *outval, Array_t*, const TypeInfo_t
         } \
         return (Optional ## KindOfInt ## _t){.i=Int_to_ ## KindOfInt(full_int, true)}; \
     } \
+    public CONSTFUNC c_type KindOfInt ## $gcd(c_type x, c_type y) { \
+        if (x == 0 || y == 0) return 0; \
+        x = KindOfInt##$abs(x); \
+        y = KindOfInt##$abs(y); \
+        while (x != y) { \
+            if (x > y) x -= y; \
+            else y -= x; \
+        } \
+        return x; \
+    } \
     public const c_type KindOfInt##$min = min_val; \
     public const c_type KindOfInt##$max = max_val; \
     public const TypeInfo_t KindOfInt##$info = { \
diff --git a/stdlib/integers.h b/stdlib/integers.h
index 52e04418..20457556 100644
--- a/stdlib/integers.h
+++ b/stdlib/integers.h
@@ -39,6 +39,7 @@
     MACROLIKE PUREFUNC c_type type_name ## $clamped(c_type x, c_type min, c_type max) { \
         return x < min ? min : (x > max ? max : x); \
     } \
+    CONSTFUNC c_type type_name ## $gcd(c_type x, c_type y); \
     extern const c_type type_name ## $min, type_name##$max; \
     extern const TypeInfo_t type_name ## $info; \
     MACROLIKE c_type type_name ## $divided_by(c_type D, c_type d) { \
@@ -105,6 +106,7 @@ OptionalInt_t Int$from_str(const char *str);
 OptionalInt_t Int$parse(Text_t text);
 Int_t Int$abs(Int_t x);
 Int_t Int$power(Int_t base, Int_t exponent);
+Int_t Int$gcd(Int_t x, Int_t y);
 OptionalInt_t Int$sqrt(Int_t i);
 
 #define BIGGEST_SMALL_INT ((1<<29)-1)