diff options
Diffstat (limited to 'gcc/wide-int.h')
| -rw-r--r-- | gcc/wide-int.h | 22 |
1 files changed, 22 insertions, 0 deletions
diff --git a/gcc/wide-int.h b/gcc/wide-int.h index 6e0275f..ff15679 100644 --- a/gcc/wide-int.h +++ b/gcc/wide-int.h @@ -507,6 +507,7 @@ namespace wi BINARY_FUNCTION div_round (const T1 &, const T2 &, signop, bool * = 0); BINARY_FUNCTION divmod_trunc (const T1 &, const T2 &, signop, WI_BINARY_RESULT (T1, T2) *); + BINARY_FUNCTION gcd (const T1 &, const T2 &, signop = UNSIGNED); BINARY_FUNCTION mod_trunc (const T1 &, const T2 &, signop, bool * = 0); BINARY_FUNCTION smod_trunc (const T1 &, const T2 &); BINARY_FUNCTION umod_trunc (const T1 &, const T2 &); @@ -2643,6 +2644,27 @@ wi::divmod_trunc (const T1 &x, const T2 &y, signop sgn, return quotient; } +/* Compute the greatest common divisor of two numbers A and B using + Euclid's algorithm. */ +template <typename T1, typename T2> +inline WI_BINARY_RESULT (T1, T2) +wi::gcd (const T1 &a, const T2 &b, signop sgn) +{ + T1 x, y, z; + + x = wi::abs (a); + y = wi::abs (b); + + while (gt_p (x, 0, sgn)) + { + z = mod_trunc (y, x, sgn); + y = x; + x = z; + } + + return y; +} + /* Compute X / Y, rouding towards 0, and return the remainder. Treat X and Y as having the signedness given by SGN. Indicate in *OVERFLOW if the division overflows. */ |