Add GCD function for integers (of all flavors)

3 files changed, 33 insertions, 0 deletions

diff --git a/environment.c b/environment.c
index 6182143c..cc7a92f6 100644
--- a/environment.c
+++ b/environment.c
@@ -122,6 +122,7 @@ env_t *new_compilation_unit(CORD libname)
             {"clamped", "Int$clamped", "func(x,low,high:Int -> Int)"},
             {"divided_by", "Int$divided_by", "func(x,y:Int -> Int)"},
             {"format", "Int$format", "func(i:Int, digits=0 -> Text)"},
+            {"gcd", "Int$gcd", "func(x,y:Int -> Int)"},
             {"parse", "Int$parse", "func(text:Text -> Int?)"},
             {"hex", "Int$hex", "func(i:Int, digits=0, uppercase=yes, prefix=yes -> Text)"},
             {"is_prime", "Int$is_prime", "func(x:Int,reps=50 -> Bool)"},
@@ -147,6 +148,7 @@ env_t *new_compilation_unit(CORD libname)
             {"clamped", "Int64$clamped", "func(x,low,high:Int64 -> Int64)"},
             {"divided_by", "Int64$divided_by", "func(x,y:Int64 -> Int64)"},
             {"format", "Int64$format", "func(i:Int64, digits=0 -> Text)"},
+            {"gcd", "Int64$gcd", "func(x,y:Int64 -> Int64)"},
             {"parse", "Int64$parse", "func(text:Text -> Int64?)"},
             {"hex", "Int64$hex", "func(i:Int64, digits=0, uppercase=yes, prefix=yes -> Text)"},
             {"max", "Int64$max", "Int64"},
@@ -166,6 +168,7 @@ env_t *new_compilation_unit(CORD libname)
             {"clamped", "Int32$clamped", "func(x,low,high:Int32 -> Int32)"},
             {"divided_by", "Int32$divided_by", "func(x,y:Int32 -> Int32)"},
             {"format", "Int32$format", "func(i:Int32, digits=0 -> Text)"},
+            {"gcd", "Int32$gcd", "func(x,y:Int32 -> Int32)"},
             {"parse", "Int32$parse", "func(text:Text -> Int32?)"},
             {"hex", "Int32$hex", "func(i:Int32, digits=0, uppercase=yes, prefix=yes -> Text)"},
             {"max", "Int32$max", "Int32"},
@@ -185,6 +188,7 @@ env_t *new_compilation_unit(CORD libname)
             {"clamped", "Int16$clamped", "func(x,low,high:Int16 -> Int16)"},
             {"divided_by", "Int16$divided_by", "func(x,y:Int16 -> Int16)"},
             {"format", "Int16$format", "func(i:Int16, digits=0 -> Text)"},
+            {"gcd", "Int16$gcd", "func(x,y:Int16 -> Int16)"},
             {"parse", "Int16$parse", "func(text:Text -> Int16?)"},
             {"hex", "Int16$hex", "func(i:Int16, digits=0, uppercase=yes, prefix=yes -> Text)"},
             {"max", "Int16$max", "Int16"},
@@ -204,6 +208,7 @@ env_t *new_compilation_unit(CORD libname)
             {"clamped", "Int8$clamped", "func(x,low,high:Int8 -> Int8)"},
             {"divided_by", "Int8$divided_by", "func(x,y:Int8 -> Int8)"},
             {"format", "Int8$format", "func(i:Int8, digits=0 -> Text)"},
+            {"gcd", "Int8$gcd", "func(x,y:Int8 -> Int8)"},
             {"parse", "Int8$parse", "func(text:Text -> Int8?)"},
             {"hex", "Int8$hex", "func(i:Int8, digits=0, uppercase=yes, prefix=yes -> Text)"},
             {"max", "Int8$max", "Int8"},
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)