diff options
Diffstat (limited to 'stdlib')
| -rw-r--r-- | stdlib/integers.c | 26 | ||||
| -rw-r--r-- | stdlib/integers.h | 2 |
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) |