Bignum: implement extended GCD (#18427)

13 files changed, 1415 insertions, 30 deletions

diff --git a/libraries/ghc-bignum/cbits/gmp_wrappers.c b/libraries/ghc-bignum/cbits/gmp_wrappers.c
index cbcf768391..56075fd1f7 100644
--- a/libraries/ghc-bignum/cbits/gmp_wrappers.c
+++ b/libraries/ghc-bignum/cbits/gmp_wrappers.c
@@ -280,30 +280,32 @@ integer_gmp_mpn_gcd(mp_limb_t r[],
 /* wraps mpz_gcdext()
  *
  * Set g={g0,gn} to the greatest common divisor of x={x0,xn} and
- * y={y0,yn}, and in addition set s={s0,sn} to coefficient
- * satisfying x*s + y*t = g.
- *
- * The g0 array is zero-padded (so that gn is fixed).
+ * y={y0,yn}, and in addition set s={s0,sn} and t={t0,tn} to
+ * coefficients satisfying x*s + y*t = g.
  *
  * g0 must have space for exactly gn=min(xn,yn) limbs.
  * s0 must have space for at least yn limbs.
+ * t0 must have space for at least xn limbs.
+ *
+ * Actual sizes are returned by pointers.
  *
- * return value: signed 'sn' of s={s0,sn} where |sn| >= 1
  */
-mp_size_t
-integer_gmp_gcdext(mp_limb_t s0[], mp_limb_t g0[],
+void
+integer_gmp_gcdext(mp_limb_t s0[], int32_t * ssn,
+                   mp_limb_t t0[], int32_t * stn,
+                   mp_limb_t g0[], int32_t * gn,
                    const mp_limb_t x0[], const mp_size_t xn,
                    const mp_limb_t y0[], const mp_size_t yn)
 {
-  const mp_size_t gn0 = mp_size_minabs(xn, yn);
   const mpz_t x = CONST_MPZ_INIT(x0, mp_limb_zero_p(x0,xn) ? 0 : xn);
   const mpz_t y = CONST_MPZ_INIT(y0, mp_limb_zero_p(y0,yn) ? 0 : yn);
 
-  mpz_t g, s;
+  mpz_t g, s, t;
   mpz_init (g);
   mpz_init (s);
+  mpz_init (t);
 
-  mpz_gcdext (g, s, NULL, x, y);
+  mpz_gcdext (g, s, t, x, y);
 
   // g must be positive (0 <= gn).
   // According to the docs for mpz_gcdext(), we have:
@@ -311,28 +313,31 @@ integer_gmp_gcdext(mp_limb_t s0[], mp_limb_t g0[],
   // -->   g < min(|y|, |x|)
   // -->   gn <= min(yn, xn)
   // <->   gn <= gn0
-  const mp_size_t gn = g[0]._mp_size;
-  assert(0 <= gn && gn <= gn0);
-  memset(g0, 0, gn0*sizeof(mp_limb_t));
-  memcpy(g0, g[0]._mp_d, gn*sizeof(mp_limb_t));
+  const mp_size_t gn0 = mp_size_minabs(xn, yn);
+  *gn = g[0]._mp_size;
+  assert(0 <= *gn && *gn <= gn0);
+  memcpy(g0, g[0]._mp_d, *gn * sizeof(mp_limb_t));
   mpz_clear (g);
 
   // According to the docs for mpz_gcdext(), we have:
   //       |s| < |y| / 2g
   // -->   |s| < |y|         (note g > 0)
   // -->   sn <= yn
-  const mp_size_t ssn = s[0]._mp_size;
-  const mp_size_t sn  = mp_size_abs(ssn);
+  *ssn = s[0]._mp_size;
+  const mp_size_t sn  = mp_size_abs(*ssn);
   assert(sn <= mp_size_abs(yn));
   memcpy(s0, s[0]._mp_d, sn*sizeof(mp_limb_t));
   mpz_clear (s);
 
-  if (!sn) {
-    s0[0] = 0;
-    return 1;
-  }
-
-  return ssn;
+  // According to the docs for mpz_gcdext(), we have:
+  //       |t| < |x| / 2g
+  // -->   |t| < |x|         (note g > 0)
+  // -->   st <= xn
+  *stn = t[0]._mp_size;
+  const mp_size_t tn  = mp_size_abs(*stn);
+  assert(tn <= mp_size_abs(xn));
+  memcpy(t0, t[0]._mp_d, tn*sizeof(mp_limb_t));
+  mpz_clear (t);
 }
 
 /* Truncating (i.e. rounded towards zero) integer division-quotient of MPN */
diff --git a/libraries/ghc-bignum/src/GHC/Num/Backend/Check.hs b/libraries/ghc-bignum/src/GHC/Num/Backend/Check.hs
index 73f8366ad0..a8ee366312 100644
--- a/libraries/ghc-bignum/src/GHC/Num/Backend/Check.hs
+++ b/libraries/ghc-bignum/src/GHC/Num/Backend/Check.hs
@@ -16,6 +16,7 @@ import GHC.Prim
 import GHC.Types
 import GHC.Num.WordArray
 import GHC.Num.Primitives
+import {-# SOURCE #-} GHC.Num.Integer
 import qualified GHC.Num.Backend.Native   as Native
 import qualified GHC.Num.Backend.Selected as Other
 
@@ -453,3 +454,18 @@ bignat_powmod_words b e m =
    in case gr `eqWord#` nr of
        1# -> gr
        _  -> unexpectedValue_Word# (# #)
+
+integer_gcde
+   :: Integer
+   -> Integer
+   -> (# Integer, Integer, Integer #)
+integer_gcde a b =
+   let
+      !(# g0,x0,y0 #) = Other.integer_gcde a b
+      !(# g1,x1,y1 #) = Native.integer_gcde a b
+   in if isTrue# (integerEq# x0 x1
+                  &&# integerEq# y0 y1
+                  &&# integerEq# g0 g1)
+         then (# g0, x0, y0 #)
+         else case unexpectedValue of
+            !_ -> (# integerZero, integerZero, integerZero #)
diff --git a/libraries/ghc-bignum/src/GHC/Num/Backend/FFI.hs b/libraries/ghc-bignum/src/GHC/Num/Backend/FFI.hs
index a049cfe332..3fddd19098 100644
--- a/libraries/ghc-bignum/src/GHC/Num/Backend/FFI.hs
+++ b/libraries/ghc-bignum/src/GHC/Num/Backend/FFI.hs
@@ -19,6 +19,7 @@ import GHC.Prim
 import GHC.Types
 import GHC.Num.WordArray
 import GHC.Num.Primitives
+import qualified GHC.Num.Backend.Native as Native
 
 default ()
 
@@ -579,3 +580,19 @@ bignat_powmod_words = ghc_bignat_powmod_words
 foreign import ccall unsafe ghc_bignat_powmod_words
    :: Word# -> Word# -> Word# -> Word#
 
+
+-- | Return extended GCD of two non-zero integers.
+--
+-- I.e. integer_gcde a b returns (g,x,y) so that ax + by = g
+--
+-- Input: a and b are non zero.
+-- Output: g must be > 0
+--
+integer_gcde
+   :: Integer
+   -> Integer
+   -> (# Integer, Integer, Integer #)
+integer_gcde = Native.integer_gcde
+   -- for now we use Native's implementation. If some FFI backend user needs a
+   -- specific implementation, we'll need to determine a prototype to pass and
+   -- return BigNat signs and sizes via FFI.
diff --git a/libraries/ghc-bignum/src/GHC/Num/Backend/GMP.hs b/libraries/ghc-bignum/src/GHC/Num/Backend/GMP.hs
index a340db573e..10242dfdc7 100644
--- a/libraries/ghc-bignum/src/GHC/Num/Backend/GMP.hs
+++ b/libraries/ghc-bignum/src/GHC/Num/Backend/GMP.hs
@@ -8,6 +8,9 @@
 {-# LANGUAGE UnliftedFFITypes #-}
 {-# LANGUAGE NegativeLiterals #-}
 {-# LANGUAGE BlockArguments #-}
+{-# LANGUAGE LambdaCase #-}
+
+{-# OPTIONS_GHC -Wno-name-shadowing #-}
 
 -- | Backend based on the GNU GMP library.
 --
@@ -22,6 +25,9 @@ import GHC.Num.WordArray
 import GHC.Num.Primitives
 import GHC.Prim
 import GHC.Types
+import GHC.Magic (runRW#)
+import {-# SOURCE #-} GHC.Num.Integer
+import {-# SOURCE #-} GHC.Num.BigNat
 
 default ()
 
@@ -352,6 +358,70 @@ bignat_powmod r b e m s =
    case ioInt# (integer_gmp_powm# r b (wordArraySize# b) e (wordArraySize# e) m (wordArraySize# m)) s of
       (# s', n #) -> mwaSetSize# r (narrowGmpSize# n) s'
 
+integer_gcde
+   :: Integer
+   -> Integer
+   -> (# Integer, Integer, Integer #)
+integer_gcde a b = case runRW# io of (# _, a #) -> a
+   where
+      !(# sa, ba #) = integerToBigNatSign# a
+      !(# sb, bb #) = integerToBigNatSign# b
+      !sza          = bigNatSize# ba
+      !szb          = bigNatSize# bb
+      -- signed sizes of a and b
+      !ssa          = case sa of
+                           0# -> sza
+                           _  -> negateInt# sza
+      !ssb          = case sb of
+                        0# -> szb
+                        _  -> negateInt# szb
+
+      -- gcd(a,b) < min(a,b)
+      !g_init_sz = minI# sza szb
+
+      -- According to https://gmplib.org/manual/Number-Theoretic-Functions.html#index-mpz_005fgcdext
+      -- a*x + b*y = g
+      -- abs(x) < abs(b) / (2 g) < abs(b)
+      -- abs(y) < abs(a) / (2 g) < abs(a)
+      !x_init_sz = szb
+      !y_init_sz = sza
+
+      io s =
+         -- allocate output arrays
+         case newWordArray# g_init_sz s     of { (# s, mbg #) ->
+         case newWordArray# x_init_sz s     of { (# s, mbx #) ->
+         case newWordArray# y_init_sz s     of { (# s, mby #) ->
+         -- allocate space to return sizes (3x4 = 12)
+         case newPinnedByteArray# 12# s     of { (# s, mszs #) ->
+         case unsafeFreezeByteArray# mszs s of { (# s, szs #) ->
+         let !ssx_ptr = byteArrayContents# szs in
+         let !ssy_ptr = ssx_ptr `plusAddr#` 4# in
+         let !sg_ptr  = ssy_ptr `plusAddr#` 4# in
+         -- call GMP
+         case ioVoid (integer_gmp_gcdext# mbx ssx_ptr mby ssy_ptr mbg sg_ptr ba ssa bb ssb) s of { s ->
+         -- read sizes
+         case readInt32OffAddr# ssx_ptr 0# s of { (# s, ssx #) ->
+         case readInt32OffAddr# ssy_ptr 0# s of { (# s, ssy #) ->
+         case readInt32OffAddr# sg_ptr  0# s of { (# s, sg #) ->
+         case touch# szs s of { s ->
+         -- shrink x, y and g to their actual sizes and freeze them
+         let !sx = absI# ssx in
+         let !sy = absI# ssy in
+         case mwaSetSize# mbx sx s of { s ->
+         case mwaSetSize# mby sy s of { s ->
+         case mwaSetSize# mbg sg s of { s ->
+
+         -- return x, y and g as Integer
+         case unsafeFreezeByteArray# mbx s of { (# s, bx #) ->
+         case unsafeFreezeByteArray# mby s of { (# s, by #) ->
+         case unsafeFreezeByteArray# mbg s of { (# s, bg #) ->
+
+         (# s, (# integerFromBigNat# bg
+               ,  integerFromBigNatSign# (ssx <# 0#) bx
+               ,  integerFromBigNatSign# (ssy <# 0#) by #) #)
+         }}}}}}}}}}}}}}}}
+
+
 
 ----------------------------------------------------------------------
 -- FFI ccall imports
@@ -366,10 +436,13 @@ foreign import ccall unsafe "integer_gmp_mpn_gcd"
   c_mpn_gcd# :: MutableByteArray# s -> ByteArray# -> GmpSize#
                 -> ByteArray# -> GmpSize# -> IO GmpSize
 
-foreign import ccall unsafe "integer_gmp_gcdext"
-  integer_gmp_gcdext# :: MutableByteArray# s -> MutableByteArray# s
-                         -> ByteArray# -> GmpSize#
-                         -> ByteArray# -> GmpSize# -> IO GmpSize
+foreign import ccall unsafe "integer_gmp_gcdext" integer_gmp_gcdext#
+  :: MutableByteArray# s -> Addr#
+  -> MutableByteArray# s -> Addr#
+  -> MutableByteArray# s -> Addr#
+  -> ByteArray# -> GmpSize#
+  -> ByteArray# -> GmpSize#
+  -> IO ()
 
 -- mp_limb_t mpn_add_1 (mp_limb_t *rp, const mp_limb_t *s1p, mp_size_t n,
 --                      mp_limb_t s2limb)
diff --git a/libraries/ghc-bignum/src/GHC/Num/Backend/Native.hs b/libraries/ghc-bignum/src/GHC/Num/Backend/Native.hs
index 1169af41d6..db4196f51f 100644
--- a/libraries/ghc-bignum/src/GHC/Num/Backend/Native.hs
+++ b/libraries/ghc-bignum/src/GHC/Num/Backend/Native.hs
@@ -17,9 +17,11 @@ module GHC.Num.Backend.Native where
 #if defined(BIGNUM_NATIVE) || defined(BIGNUM_CHECK)
 import {-# SOURCE #-} GHC.Num.BigNat
 import {-# SOURCE #-} GHC.Num.Natural
+import {-# SOURCE #-} GHC.Num.Integer
 #else
 import GHC.Num.BigNat
 import GHC.Num.Natural
+import GHC.Num.Integer
 #endif
 import GHC.Num.WordArray
 import GHC.Num.Primitives
@@ -717,3 +719,21 @@ bignat_powmod_words b e m =
    bignat_powmod_word (wordArrayFromWord# b)
                       (wordArrayFromWord# e)
                       m
+
+
+integer_gcde
+   :: Integer
+   -> Integer
+   -> (# Integer, Integer, Integer #)
+integer_gcde a b = f (# a,integerOne,integerZero #) (# b,integerZero,integerOne #)
+  where
+    -- returned "g" must be positive
+    fix (# g, x, y #)
+       | integerIsNegative g = (# integerNegate g, integerNegate x, integerNegate y #)
+       | True                = (# g,x,y #)
+
+    f old@(# old_g, old_s, old_t #) new@(# g, s, t #)
+      | integerIsZero g = fix old
+      | True            = case integerQuotRem# old_g g of
+                              !(# q, r #) -> f new (# r , old_s `integerSub` (q `integerMul` s)
+                                                        , old_t `integerSub` (q `integerMul` t) #)
diff --git a/libraries/ghc-bignum/src/GHC/Num/BigNat.hs-boot b/libraries/ghc-bignum/src/GHC/Num/BigNat.hs-boot
index 90a3f11ea1..37edb97582 100644
--- a/libraries/ghc-bignum/src/GHC/Num/BigNat.hs-boot
+++ b/libraries/ghc-bignum/src/GHC/Num/BigNat.hs-boot
@@ -10,6 +10,7 @@ import GHC.Prim
 type BigNat# = WordArray#
 data BigNat = BN# { unBigNat :: BigNat# }
 
+bigNatSize# :: BigNat# -> Int#
 bigNatSubUnsafe :: BigNat# -> BigNat# -> BigNat#
 bigNatMulWord# :: BigNat# -> Word# -> BigNat#
 bigNatRem :: BigNat# -> BigNat# -> BigNat#
diff --git a/libraries/ghc-bignum/src/GHC/Num/Integer.hs b/libraries/ghc-bignum/src/GHC/Num/Integer.hs
index 04dd57b291..43e4a18cdd 100644
--- a/libraries/ghc-bignum/src/GHC/Num/Integer.hs
+++ b/libraries/ghc-bignum/src/GHC/Num/Integer.hs
@@ -6,6 +6,7 @@
 {-# LANGUAGE NegativeLiterals #-}
 {-# LANGUAGE BinaryLiterals #-}
 {-# LANGUAGE BlockArguments #-}
+{-# LANGUAGE LambdaCase #-}
 
 -- |
 -- Module      :  GHC.Num.Integer
@@ -31,6 +32,7 @@ import GHC.Magic
 import GHC.Num.Primitives
 import GHC.Num.BigNat
 import GHC.Num.Natural
+import qualified GHC.Num.Backend as Backend
 
 #if WORD_SIZE_IN_BITS < 64
 import GHC.IntWord64
@@ -113,6 +115,17 @@ integerFromBigNatSign# !sign !bn
    | True
    = integerFromBigNatNeg# bn
 
+-- | Convert an Integer into a sign-bit and a BigNat
+integerToBigNatSign# :: Integer -> (# Int#, BigNat# #)
+integerToBigNatSign# = \case
+   IS x
+      | isTrue# (x >=# 0#)
+      -> (# 0#, bigNatFromWord# (int2Word# x) #)
+      | True
+      -> (# 1#, bigNatFromWord# (int2Word# (negateInt# x)) #)
+   IP x -> (# 0#, x #)
+   IN x -> (# 1#, x #)
+
 -- | Convert an Integer into a BigNat.
 --
 -- Return 0 for negative Integers.
@@ -853,7 +866,7 @@ integerDivMod# :: Integer -> Integer -> (# Integer, Integer #)
 {-# NOINLINE integerDivMod# #-}
 integerDivMod# !n !d
   | isTrue# (integerSignum# r ==# negateInt# (integerSignum# d))
-     = let !q' = integerAdd q (IS -1#) -- TODO: optimize
+     = let !q' = integerSub q (IS 1#)
            !r' = integerAdd r d
        in (# q', r' #)
   | True = qr
@@ -1169,3 +1182,35 @@ integerFromByteArray# sz ba off e s = case bigNatFromByteArray# sz ba off e s of
 integerFromByteArray :: Word# -> ByteArray# -> Word# -> Bool# -> Integer
 integerFromByteArray sz ba off e = case runRW# (integerFromByteArray# sz ba off e) of
    (# _, i #) -> i
+
+
+-- | Get the extended GCD of two integers.
+--
+-- `integerGcde# a b` returns (# g,x,y #) where
+--    * ax + by = g = |gcd a b|
+integerGcde#
+   :: Integer
+   -> Integer
+   -> (# Integer, Integer, Integer #)
+integerGcde# a b
+   | integerIsZero a && integerIsZero b    =     (# integerZero, integerZero, integerZero #)
+   | integerIsZero a                       = fix (# b          , integerZero, integerOne #)
+   | integerIsZero b                       = fix (# a          , integerOne,  integerZero #)
+   | integerAbs a `integerEq` integerAbs b = fix (# b          , integerZero, integerOne #)
+   | True                                  = Backend.integer_gcde a b
+   where
+      -- returned "g" must be positive
+      fix (# g, x, y #)
+         | integerIsNegative g = (# integerNegate g, integerNegate x, integerNegate y #)
+         | True                = (# g,x,y #)
+
+-- | Get the extended GCD of two integers.
+--
+-- `integerGcde a b` returns (g,x,y) where
+--    * ax + by = g = |gcd a b|
+integerGcde
+   :: Integer
+   -> Integer
+   -> ( Integer, Integer, Integer)
+integerGcde a b = case integerGcde# a b of
+   (# g,x,y #) -> (g,x,y)
diff --git a/libraries/ghc-bignum/src/GHC/Num/Integer.hs-boot b/libraries/ghc-bignum/src/GHC/Num/Integer.hs-boot
new file mode 100644
index 0000000000..a07b9b7548
--- /dev/null
+++ b/libraries/ghc-bignum/src/GHC/Num/Integer.hs-boot
@@ -0,0 +1,30 @@
+{-# LANGUAGE NoImplicitPrelude #-}
+{-# LANGUAGE UnboxedTuples #-}
+{-# LANGUAGE MagicHash #-}
+
+module GHC.Num.Integer where
+
+import GHC.Types
+import GHC.Prim
+import {-# SOURCE #-} GHC.Num.BigNat
+
+data Integer
+
+integerZero :: Integer
+integerOne :: Integer
+
+integerEq# :: Integer -> Integer -> Int#
+integerEq :: Integer -> Integer -> Bool
+integerGt :: Integer -> Integer -> Bool
+integerIsZero :: Integer -> Bool
+integerIsNegative :: Integer -> Bool
+
+integerSub :: Integer -> Integer -> Integer
+integerMul :: Integer -> Integer -> Integer
+integerNegate :: Integer -> Integer
+integerDivMod# :: Integer -> Integer -> (# Integer, Integer #)
+integerQuotRem# :: Integer -> Integer -> (# Integer, Integer #)
+
+integerToBigNatSign# :: Integer -> (# Int#, BigNat# #)
+integerFromBigNatSign# :: Int# -> BigNat# -> Integer
+integerFromBigNat# :: BigNat# -> Integer
diff --git a/libraries/integer-gmp/src/GHC/Integer/GMP/Internals.hs b/libraries/integer-gmp/src/GHC/Integer/GMP/Internals.hs
index e414846d96..3d5fabe6c0 100644
--- a/libraries/integer-gmp/src/GHC/Integer/GMP/Internals.hs
+++ b/libraries/integer-gmp/src/GHC/Integer/GMP/Internals.hs
@@ -29,6 +29,7 @@ module GHC.Integer.GMP.Internals
 
       -- ** Additional 'Integer' operations
     , gcdInteger
+    , gcdExtInteger
     , lcmInteger
     , sqrInteger
 
@@ -170,6 +171,12 @@ isValidInteger# = I.integerCheck#
 gcdInteger :: Integer -> Integer -> Integer
 gcdInteger = I.integerGcd
 
+{-# DEPRECATED gcdExtInteger "Use integerGcde instead" #-}
+gcdExtInteger :: Integer -> Integer -> (# Integer, Integer #)
+gcdExtInteger a b = case I.integerGcde# a b of
+   (# g, s, _t #) -> (# g, s #)
+
+
 {-# DEPRECATED lcmInteger "Use integerLcm instead" #-}
 lcmInteger :: Integer -> Integer -> Integer
 lcmInteger = I.integerLcm
diff --git a/testsuite/tests/lib/integer/all.T b/testsuite/tests/lib/integer/all.T
index 0e32d11981..45270453a1 100644
--- a/testsuite/tests/lib/integer/all.T
+++ b/testsuite/tests/lib/integer/all.T
@@ -5,11 +5,12 @@ test('integerConstantFolding', normal, makefile_test, ['integerConstantFolding']
 test('fromToInteger', [], makefile_test, ['fromToInteger'])
 test('IntegerConversionRules', [], makefile_test, ['IntegerConversionRules'])
 test('gcdInteger', normal, compile_and_run, [''])
+test('gcdeInteger', normal, compile_and_run, [''])
 test('integerPowMod', [], compile_and_run, [''])
+test('integerGcdExt', [omit_ways(['ghci'])], compile_and_run, [''])
 
 # skip ghci as it doesn't support unboxed tuples
 test('integerImportExport', [omit_ways(['ghci'])], compile_and_run, [''])
 
 # Disable GMP only tests
-#test('integerGcdExt', [omit_ways(['ghci'])], compile_and_run, [''])
 #test('integerGmpInternals', [], compile_and_run, [''])
diff --git a/testsuite/tests/lib/integer/gcdeInteger.hs b/testsuite/tests/lib/integer/gcdeInteger.hs
new file mode 100644
index 0000000000..9fabc2cbce
--- /dev/null
+++ b/testsuite/tests/lib/integer/gcdeInteger.hs
@@ -0,0 +1,114 @@
+
+{-# LANGUAGE MagicHash #-}
+{-# LANGUAGE MultiWayIf #-}
+
+module Main (main) where
+
+import GHC.Base
+import GHC.Num.Integer
+import Control.Monad
+import System.Exit
+
+main :: IO ()
+main = do
+
+   let test a b = do
+         putStrLn $ "GCDE " ++ show a ++ " " ++ show b
+         let r@(g,x,y) = integerGcde a b
+         putStrLn $ "   -> g = " ++ show g
+         putStrLn $ "   -> x = " ++ show x
+         putStrLn $ "   -> y = " ++ show y
+         let sign a | a >= 0    = 1
+                    | otherwise = -1
+         let assert text cond term
+               | not cond  = return ()
+               | term      = return ()
+               | otherwise = do
+                  putStrLn $ "FAILED: " ++ text
+                  putStrLn $ "a*x + b*y = g"
+                  putStrLn $ "a = " ++ show a
+                  putStrLn $ "b = " ++ show b
+                  putStrLn $ "x = " ++ show x
+                  putStrLn $ "y = " ++ show y
+                  putStrLn $ "g = " ++ show g
+                  putStrLn $ "expected g = " ++ show (abs (integerGcd a b))
+                  exitFailure
+
+         -- check properties
+         assert "g >= 0"            True (g >= 0)
+         assert "a*x + b*y = g"     True (a*x + b*y == g)
+         assert "g = abs (gcd a b)" True (g == abs (integerGcd a b))
+
+         if -- special cases
+            | a == 0 && b == 0 -> do
+               assert "a == 0 && b ==0 ==> g == 0" (a == 0 && b == 0) (g == 0)
+
+            | abs a == abs b -> do
+               assert "abs a == abs b ==> x == 0 && y == sign b && g == abs a"
+                  (abs a == abs b) (x == 0 && y == sign b && g == abs a)
+
+            -- non special cases
+            | otherwise -> do
+               assert "b == 0 ==> x=sign a"
+                  (b == 0)
+                  (x == sign a)
+
+               assert "abs b == 2g ==> x=sign a"
+                  (abs b == 2*g)
+                  (x == sign a)
+
+               assert "b /= 0 ==> abs x <= abs b / 2*g"
+                  (b /= 0)
+                  (abs x <= abs b `div` 2 * g)
+
+               assert "a /= 0 ==> abs y <= abs a / 2*g"
+                  (a /= 0)
+                  (abs y <= abs a `div` 2 * g)
+
+               assert "a == 0 ==> y=sign b"
+                  (a == 0)
+                  (y == sign b)
+
+               assert "abs a == 2g ==> y==sign b"
+                  (abs a == 2*g)
+                  (y == sign b)
+
+               assert "x == 0 ==> g == abs b"
+                  (x == 0)
+                  (g == abs b)
+
+       nums =
+            [ 0
+            , 1
+            , 7
+            , 14
+            , 123
+            , 1230
+            , 123456789456789456789456789456789456789465789465456789465454645789
+            , 4 * 123456789456789456789456789456789456789465789465456789465454645789
+            , -1
+            , -123
+            , -123456789456789456789456789456789456789465789465456789465454645789
+            , 4567897897897897899789897897978978979789
+            , 2988348162058574136915891421498819466320163312926952423791023078876139
+            , 2351399303373464486466122544523690094744975233415544072992656881240319
+            , 5328841272400314897981163497728751426
+            , 32052182750761975518649228050096851724
+            ]
+
+   forM_ nums $ \a ->
+      forM_ nums $ \b ->
+         test a b
+
+   -- see #15350
+   do
+       let a = 2
+           b = 2^65 + 1
+       test a b
+       test a (-b)
+       test (-a) b
+       test (-a) (-b)
+       test b a
+       test b (-a)
+       test (-b) a
+       test (-b) (-a)
diff --git a/testsuite/tests/lib/integer/gcdeInteger.stdout b/testsuite/tests/lib/integer/gcdeInteger.stdout
new file mode 100644
index 0000000000..f4854ddb08
--- /dev/null
+++ b/testsuite/tests/lib/integer/gcdeInteger.stdout
@@ -0,0 +1,1056 @@
+GCDE 0 0
+   -> g = 0
+   -> x = 0
+   -> y = 0
+GCDE 0 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 0 7
+   -> g = 7
+   -> x = 0
+   -> y = 1
+GCDE 0 14
+   -> g = 14
+   -> x = 0
+   -> y = 1
+GCDE 0 123
+   -> g = 123
+   -> x = 0
+   -> y = 1
+GCDE 0 1230
+   -> g = 1230
+   -> x = 0
+   -> y = 1
+GCDE 0 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = 1
+GCDE 0 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 493827157827157827157827157827157827157863157861827157861818583156
+   -> x = 0
+   -> y = 1
+GCDE 0 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 0 -123
+   -> g = 123
+   -> x = 0
+   -> y = -1
+GCDE 0 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = -1
+GCDE 0 4567897897897897899789897897978978979789
+   -> g = 4567897897897897899789897897978978979789
+   -> x = 0
+   -> y = 1
+GCDE 0 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> x = 0
+   -> y = 1
+GCDE 0 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> x = 0
+   -> y = 1
+GCDE 0 5328841272400314897981163497728751426
+   -> g = 5328841272400314897981163497728751426
+   -> x = 0
+   -> y = 1
+GCDE 0 32052182750761975518649228050096851724
+   -> g = 32052182750761975518649228050096851724
+   -> x = 0
+   -> y = 1
+GCDE 1 0
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 1 7
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 14
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 123
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 1230
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 1 -123
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 1 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = 1
+   -> y = 0
+GCDE 7 0
+   -> g = 7
+   -> x = 1
+   -> y = 0
+GCDE 7 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 7 7
+   -> g = 7
+   -> x = 0
+   -> y = 1
+GCDE 7 14
+   -> g = 7
+   -> x = 1
+   -> y = 0
+GCDE 7 123
+   -> g = 1
+   -> x = -35
+   -> y = 2
+GCDE 7 1230
+   -> g = 1
+   -> x = -527
+   -> y = 3
+GCDE 7 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -52910052624338338624052909767195481481199624056624338342337705338
+   -> y = 3
+GCDE 7 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = 70546736832451118165403879689593975308266165408832451123116940451
+   -> y = -1
+GCDE 7 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 7 -123
+   -> g = 1
+   -> x = -35
+   -> y = -2
+GCDE 7 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -52910052624338338624052909767195481481199624056624338342337705338
+   -> y = -3
+GCDE 7 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -1305113685113685114225685113708279708511
+   -> y = 2
+GCDE 7 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 1280720640882246058678239180642351199851498562682979610196152748089774
+   -> y = -3
+GCDE 7 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -671828372392418424704606441292482884212850066690155449426473394640091
+   -> y = 2
+GCDE 7 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 2283789116742992099134784356169464897
+   -> y = -3
+GCDE 7 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -13736649750326560936563954878612936453
+   -> y = 3
+GCDE 14 0
+   -> g = 14
+   -> x = 1
+   -> y = 0
+GCDE 14 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 14 7
+   -> g = 7
+   -> x = 0
+   -> y = 1
+GCDE 14 14
+   -> g = 14
+   -> x = 0
+   -> y = 1
+GCDE 14 123
+   -> g = 1
+   -> x = 44
+   -> y = -5
+GCDE 14 1230
+   -> g = 2
+   -> x = 88
+   -> y = -1
+GCDE 14 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -26455026312169169312026454883597740740599812028312169171168852669
+   -> y = 3
+GCDE 14 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 2
+   -> x = 70546736832451118165403879689593975308266165408832451123116940451
+   -> y = -2
+GCDE 14 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 14 -123
+   -> g = 1
+   -> x = 44
+   -> y = 5
+GCDE 14 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -26455026312169169312026454883597740740599812028312169171168852669
+   -> y = -3
+GCDE 14 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 1631392106392106392782106392135349635639
+   -> y = -5
+GCDE 14 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 640360320441123029339119590321175599925749281341489805098076374044887
+   -> y = -3
+GCDE 14 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 839785465490523030880758051615603605266062583362694311783091743300114
+   -> y = -5
+GCDE 14 5328841272400314897981163497728751426
+   -> g = 2
+   -> x = -380631519457165349855797392694910816
+   -> y = 1
+GCDE 14 32052182750761975518649228050096851724
+   -> g = 2
+   -> x = 2289441625054426822760659146435489409
+   -> y = -1
+GCDE 123 0
+   -> g = 123
+   -> x = 1
+   -> y = 0
+GCDE 123 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 123 7
+   -> g = 1
+   -> x = 2
+   -> y = -35
+GCDE 123 14
+   -> g = 1
+   -> x = -5
+   -> y = 44
+GCDE 123 123
+   -> g = 123
+   -> x = 0
+   -> y = 1
+GCDE 123 1230
+   -> g = 123
+   -> x = 1
+   -> y = 0
+GCDE 123 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -49181973035631572216938070596607181973039216941523436453717704420
+   -> y = 49
+GCDE 123 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = -172638762492421029006394860053396638762505006406980225919172350209
+   -> y = 43
+GCDE 123 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 123 -123
+   -> g = 123
+   -> x = 0
+   -> y = -1
+GCDE 123 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -49181973035631572216938070596607181973039216941523436453717704420
+   -> y = -49
+GCDE 123 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 854159769525623184513558143524524524676
+   -> y = -23
+GCDE 123 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 1360548756709594729002357069950682033446578418893571835221929206642795
+   -> y = -56
+GCDE 123 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -1108789915411877562723862663271333540611451736082126473443691862698687
+   -> y = 58
+GCDE 123 5328841272400314897981163497728751426
+   -> g = 3
+   -> x = 606534778972393565623872268034166829
+   -> y = -14
+GCDE 123 32052182750761975518649228050096851724
+   -> g = 3
+   -> x = 1042347406528844732313796034149491113
+   -> y = -4
+GCDE 1230 0
+   -> g = 1230
+   -> x = 1
+   -> y = 0
+GCDE 1230 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 1230 7
+   -> g = 1
+   -> x = 3
+   -> y = -527
+GCDE 1230 14
+   -> g = 2
+   -> x = -1
+   -> y = 88
+GCDE 1230 123
+   -> g = 123
+   -> x = 0
+   -> y = 1
+GCDE 1230 1230
+   -> g = 1230
+   -> x = 0
+   -> y = 1
+GCDE 1230 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -4918197303563157221693807059660718197303921694152343645371770442
+   -> y = 49
+GCDE 1230 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 2
+   -> x = 113620394849663142346069175337468020394857946077152102174711104905
+   -> y = -283
+GCDE 1230 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 1230 -123
+   -> g = 123
+   -> x = 0
+   -> y = -1
+GCDE 1230 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -4918197303563157221693807059660718197303921694152343645371770442
+   -> y = -49
+GCDE 1230 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -1741743182206596841464603344839139139448
+   -> y = 469
+GCDE 1230 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -1358119205358327595557710003754341529815423814574119028373318618773790
+   -> y = 559
+GCDE 1230 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 594540799470851589667450497029973674362347396416450574553427878102227
+   -> y = -311
+GCDE 1230 5328841272400314897981163497728751426
+   -> g = 6
+   -> x = 298934998207822543057479903531125080
+   -> y = -69
+GCDE 1230 32052182750761975518649228050096851724
+   -> g = 6
+   -> x = -1928342702078362754780522663176558559
+   -> y = 74
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 0
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 1
+   -> y = 0
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 7
+   -> g = 1
+   -> x = 3
+   -> y = -52910052624338338624052909767195481481199624056624338342337705338
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 14
+   -> g = 1
+   -> x = 3
+   -> y = -26455026312169169312026454883597740740599812028312169171168852669
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 123
+   -> g = 1
+   -> x = 49
+   -> y = -49181973035631572216938070596607181973039216941523436453717704420
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 1230
+   -> g = 1
+   -> x = 49
+   -> y = -4918197303563157221693807059660718197303921694152343645371770442
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = 1
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 1
+   -> y = 0
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 -123
+   -> g = 1
+   -> x = 49
+   -> y = 49181973035631572216938070596607181973039216941523436453717704420
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = -1
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -142355531505412253555567593395647545708
+   -> y = 3847449587076097018280777909186630028091235782450380442052224817
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 501499981494162622976489092493961483514126808861435716131179868189595
+   -> y = -20718328076357217180814970215022985846592184263422313201087532586
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 608000101055682152473830041965606704242079033852469328931798308452101
+   -> y = -31922158162609726789179865549911873484290325403318594248193251952
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = -233831227202814412604649442847121617
+   -> y = 5417322661629453658993420651614628087475941267504880682551205239
+GCDE 123456789456789456789456789456789456789465789465456789465454645789 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = 2649042575281623182157985423209129457
+   -> y = -10203432759063496909071922280945854833629276496909075027106202353
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 0
+   -> g = 493827157827157827157827157827157827157863157861827157861818583156
+   -> x = 1
+   -> y = 0
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 7
+   -> g = 1
+   -> x = -1
+   -> y = 70546736832451118165403879689593975308266165408832451123116940451
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 14
+   -> g = 2
+   -> x = -2
+   -> y = 70546736832451118165403879689593975308266165408832451123116940451
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 123
+   -> g = 1
+   -> x = 43
+   -> y = -172638762492421029006394860053396638762505006406980225919172350209
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 1230
+   -> g = 2
+   -> x = -283
+   -> y = 113620394849663142346069175337468020394857946077152102174711104905
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = 1
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 493827157827157827157827157827157827157863157861827157861818583156
+   -> x = 0
+   -> y = 1
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 -123
+   -> g = 1
+   -> x = 43
+   -> y = 172638762492421029006394860053396638762505006406980225919172350209
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = -1
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -35588882876353063388891898348911886427
+   -> y = 3847449587076097018280777909186630028091235782450380442052224817
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -621712045141102878484850582251214495701509126016379176914960802671636
+   -> y = 102738461380432239608641819241766470942873605202034476264367113203
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 739849851107286659734988146622324199746763566817003350481113797423105
+   -> y = -155378947619399183578636655006701330273756114868775383713647897741
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 5328841272400314897981163497728751426
+   -> g = 2
+   -> x = 1215294704498671518192966153008627048
+   -> y = -112622144133530549471469948153560200614513906930447028100352235311
+GCDE 493827157827157827157827157827157827157863157861827157861818583156 32052182750761975518649228050096851724
+   -> g = 4
+   -> x = 2649042575281623182157985423209129457
+   -> y = -40813731036253987636287689123783419334517105987636300108424809412
+GCDE -1 0
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE -1 7
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 14
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 123
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 1230
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE -1 -123
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -1 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -1
+   -> y = 0
+GCDE -123 0
+   -> g = 123
+   -> x = -1
+   -> y = 0
+GCDE -123 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE -123 7
+   -> g = 1
+   -> x = -2
+   -> y = -35
+GCDE -123 14
+   -> g = 1
+   -> x = 5
+   -> y = 44
+GCDE -123 123
+   -> g = 123
+   -> x = 0
+   -> y = 1
+GCDE -123 1230
+   -> g = 123
+   -> x = -1
+   -> y = 0
+GCDE -123 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 49181973035631572216938070596607181973039216941523436453717704420
+   -> y = 49
+GCDE -123 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = 172638762492421029006394860053396638762505006406980225919172350209
+   -> y = 43
+GCDE -123 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE -123 -123
+   -> g = 123
+   -> x = 0
+   -> y = -1
+GCDE -123 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 49181973035631572216938070596607181973039216941523436453717704420
+   -> y = -49
+GCDE -123 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -854159769525623184513558143524524524676
+   -> y = -23
+GCDE -123 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -1360548756709594729002357069950682033446578418893571835221929206642795
+   -> y = -56
+GCDE -123 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 1108789915411877562723862663271333540611451736082126473443691862698687
+   -> y = 58
+GCDE -123 5328841272400314897981163497728751426
+   -> g = 3
+   -> x = -606534778972393565623872268034166829
+   -> y = -14
+GCDE -123 32052182750761975518649228050096851724
+   -> g = 3
+   -> x = -1042347406528844732313796034149491113
+   -> y = -4
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 0
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = -1
+   -> y = 0
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 7
+   -> g = 1
+   -> x = -3
+   -> y = -52910052624338338624052909767195481481199624056624338342337705338
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 14
+   -> g = 1
+   -> x = -3
+   -> y = -26455026312169169312026454883597740740599812028312169171168852669
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 123
+   -> g = 1
+   -> x = -49
+   -> y = -49181973035631572216938070596607181973039216941523436453717704420
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 1230
+   -> g = 1
+   -> x = -49
+   -> y = -4918197303563157221693807059660718197303921694152343645371770442
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = 1
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = -1
+   -> y = 0
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 -123
+   -> g = 1
+   -> x = -49
+   -> y = 49181973035631572216938070596607181973039216941523436453717704420
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 123456789456789456789456789456789456789465789465456789465454645789
+   -> x = 0
+   -> y = -1
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 142355531505412253555567593395647545708
+   -> y = 3847449587076097018280777909186630028091235782450380442052224817
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -501499981494162622976489092493961483514126808861435716131179868189595
+   -> y = -20718328076357217180814970215022985846592184263422313201087532586
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -608000101055682152473830041965606704242079033852469328931798308452101
+   -> y = -31922158162609726789179865549911873484290325403318594248193251952
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 233831227202814412604649442847121617
+   -> y = 5417322661629453658993420651614628087475941267504880682551205239
+GCDE -123456789456789456789456789456789456789465789465456789465454645789 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -2649042575281623182157985423209129457
+   -> y = -10203432759063496909071922280945854833629276496909075027106202353
+GCDE 4567897897897897899789897897978978979789 0
+   -> g = 4567897897897897899789897897978978979789
+   -> x = 1
+   -> y = 0
+GCDE 4567897897897897899789897897978978979789 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 4567897897897897899789897897978978979789 7
+   -> g = 1
+   -> x = 2
+   -> y = -1305113685113685114225685113708279708511
+GCDE 4567897897897897899789897897978978979789 14
+   -> g = 1
+   -> x = -5
+   -> y = 1631392106392106392782106392135349635639
+GCDE 4567897897897897899789897897978978979789 123
+   -> g = 1
+   -> x = -23
+   -> y = 854159769525623184513558143524524524676
+GCDE 4567897897897897899789897897978978979789 1230
+   -> g = 1
+   -> x = 469
+   -> y = -1741743182206596841464603344839139139448
+GCDE 4567897897897897899789897897978978979789 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 3847449587076097018280777909186630028091235782450380442052224817
+   -> y = -142355531505412253555567593395647545708
+GCDE 4567897897897897899789897897978978979789 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = 3847449587076097018280777909186630028091235782450380442052224817
+   -> y = -35588882876353063388891898348911886427
+GCDE 4567897897897897899789897897978978979789 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 4567897897897897899789897897978978979789 -123
+   -> g = 1
+   -> x = -23
+   -> y = -854159769525623184513558143524524524676
+GCDE 4567897897897897899789897897978978979789 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 3847449587076097018280777909186630028091235782450380442052224817
+   -> y = 142355531505412253555567593395647545708
+GCDE 4567897897897897899789897897978978979789 4567897897897897899789897897978978979789
+   -> g = 4567897897897897899789897897978978979789
+   -> x = 0
+   -> y = 1
+GCDE 4567897897897897899789897897978978979789 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -1015458101705415789288140664792006324531958465967800433101537202119645
+   -> y = 1552198297064637650702543759558133740654
+GCDE 4567897897897897899789897897978978979789 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 683642522828502349233122722282318495240860998440822891959775694494728
+   -> y = -1328064203498637654577318574253233256089
+GCDE 4567897897897897899789897897978978979789 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 729028905639966888803280268153493563
+   -> y = -624925651816157654399317122483041604031
+GCDE 4567897897897897899789897897978978979789 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -12910967943414004413956938074429250463
+   -> y = 1839998972523827338782593728961148005767
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 0
+   -> g = 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> x = 1
+   -> y = 0
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 7
+   -> g = 1
+   -> x = -3
+   -> y = 1280720640882246058678239180642351199851498562682979610196152748089774
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 14
+   -> g = 1
+   -> x = -3
+   -> y = 640360320441123029339119590321175599925749281341489805098076374044887
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 123
+   -> g = 1
+   -> x = -56
+   -> y = 1360548756709594729002357069950682033446578418893571835221929206642795
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 1230
+   -> g = 1
+   -> x = 559
+   -> y = -1358119205358327595557710003754341529815423814574119028373318618773790
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -20718328076357217180814970215022985846592184263422313201087532586
+   -> y = 501499981494162622976489092493961483514126808861435716131179868189595
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = 102738461380432239608641819241766470942873605202034476264367113203
+   -> y = -621712045141102878484850582251214495701509126016379176914960802671636
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 -123
+   -> g = 1
+   -> x = -56
+   -> y = -1360548756709594729002357069950682033446578418893571835221929206642795
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -20718328076357217180814970215022985846592184263422313201087532586
+   -> y = -501499981494162622976489092493961483514126808861435716131179868189595
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 1552198297064637650702543759558133740654
+   -> y = -1015458101705415789288140664792006324531958465967800433101537202119645
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> x = 0
+   -> y = 1
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -238164827888328100873319793437342927637138278785737103723156342382925
+   -> y = 302679100340807588460107986194035692812415103244388831792688023418704
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 88969837841661133174308363831195241
+   -> y = -49893182739334638874406212208356173614356037934509167748717979955473
+GCDE 2988348162058574136915891421498819466320163312926952423791023078876139 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -2926808101621088968857550652617123241
+   -> y = 272877565911469778893036529750941765793334087149670477404511983087875
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 0
+   -> g = 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> x = 1
+   -> y = 0
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 7
+   -> g = 1
+   -> x = 2
+   -> y = -671828372392418424704606441292482884212850066690155449426473394640091
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 14
+   -> g = 1
+   -> x = -5
+   -> y = 839785465490523030880758051615603605266062583362694311783091743300114
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 123
+   -> g = 1
+   -> x = 58
+   -> y = -1108789915411877562723862663271333540611451736082126473443691862698687
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 1230
+   -> g = 1
+   -> x = -311
+   -> y = 594540799470851589667450497029973674362347396416450574553427878102227
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -31922158162609726789179865549911873484290325403318594248193251952
+   -> y = 608000101055682152473830041965606704242079033852469328931798308452101
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 1
+   -> x = -155378947619399183578636655006701330273756114868775383713647897741
+   -> y = 739849851107286659734988146622324199746763566817003350481113797423105
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 -123
+   -> g = 1
+   -> x = 58
+   -> y = 1108789915411877562723862663271333540611451736082126473443691862698687
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -31922158162609726789179865549911873484290325403318594248193251952
+   -> y = -608000101055682152473830041965606704242079033852469328931798308452101
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -1328064203498637654577318574253233256089
+   -> y = 683642522828502349233122722282318495240860998440822891959775694494728
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 302679100340807588460107986194035692812415103244388831792688023418704
+   -> y = -238164827888328100873319793437342927637138278785737103723156342382925
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> x = 0
+   -> y = 1
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 5328841272400314897981163497728751426
+   -> g = 1
+   -> x = 1320061761887019753142991170712833225
+   -> y = -582489165775607532361449347744188527071103823360367325716372563952699
+GCDE 2351399303373464486466122544523690094744975233415544072992656881240319 32052182750761975518649228050096851724
+   -> g = 1
+   -> x = -3459287250911140032199362006422486237
+   -> y = 253778836069059554551347740010931350716760250644753514181097821250371
+GCDE 5328841272400314897981163497728751426 0
+   -> g = 5328841272400314897981163497728751426
+   -> x = 1
+   -> y = 0
+GCDE 5328841272400314897981163497728751426 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 5328841272400314897981163497728751426 7
+   -> g = 1
+   -> x = -3
+   -> y = 2283789116742992099134784356169464897
+GCDE 5328841272400314897981163497728751426 14
+   -> g = 2
+   -> x = 1
+   -> y = -380631519457165349855797392694910816
+GCDE 5328841272400314897981163497728751426 123
+   -> g = 3
+   -> x = -14
+   -> y = 606534778972393565623872268034166829
+GCDE 5328841272400314897981163497728751426 1230
+   -> g = 6
+   -> x = -69
+   -> y = 298934998207822543057479903531125080
+GCDE 5328841272400314897981163497728751426 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 5417322661629453658993420651614628087475941267504880682551205239
+   -> y = -233831227202814412604649442847121617
+GCDE 5328841272400314897981163497728751426 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 2
+   -> x = -112622144133530549471469948153560200614513906930447028100352235311
+   -> y = 1215294704498671518192966153008627048
+GCDE 5328841272400314897981163497728751426 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 5328841272400314897981163497728751426 -123
+   -> g = 3
+   -> x = -14
+   -> y = -606534778972393565623872268034166829
+GCDE 5328841272400314897981163497728751426 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = 5417322661629453658993420651614628087475941267504880682551205239
+   -> y = 233831227202814412604649442847121617
+GCDE 5328841272400314897981163497728751426 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = -624925651816157654399317122483041604031
+   -> y = 729028905639966888803280268153493563
+GCDE 5328841272400314897981163497728751426 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = -49893182739334638874406212208356173614356037934509167748717979955473
+   -> y = 88969837841661133174308363831195241
+GCDE 5328841272400314897981163497728751426 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = -582489165775607532361449347744188527071103823360367325716372563952699
+   -> y = 1320061761887019753142991170712833225
+GCDE 5328841272400314897981163497728751426 5328841272400314897981163497728751426
+   -> g = 5328841272400314897981163497728751426
+   -> x = 0
+   -> y = 1
+GCDE 5328841272400314897981163497728751426 32052182750761975518649228050096851724
+   -> g = 92889294
+   -> x = 115110207004456909698806038261
+   -> y = -19137667681784054624628973533
+GCDE 32052182750761975518649228050096851724 0
+   -> g = 32052182750761975518649228050096851724
+   -> x = 1
+   -> y = 0
+GCDE 32052182750761975518649228050096851724 1
+   -> g = 1
+   -> x = 0
+   -> y = 1
+GCDE 32052182750761975518649228050096851724 7
+   -> g = 1
+   -> x = 3
+   -> y = -13736649750326560936563954878612936453
+GCDE 32052182750761975518649228050096851724 14
+   -> g = 2
+   -> x = -1
+   -> y = 2289441625054426822760659146435489409
+GCDE 32052182750761975518649228050096851724 123
+   -> g = 3
+   -> x = -4
+   -> y = 1042347406528844732313796034149491113
+GCDE 32052182750761975518649228050096851724 1230
+   -> g = 6
+   -> x = 74
+   -> y = -1928342702078362754780522663176558559
+GCDE 32052182750761975518649228050096851724 123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -10203432759063496909071922280945854833629276496909075027106202353
+   -> y = 2649042575281623182157985423209129457
+GCDE 32052182750761975518649228050096851724 493827157827157827157827157827157827157863157861827157861818583156
+   -> g = 4
+   -> x = -40813731036253987636287689123783419334517105987636300108424809412
+   -> y = 2649042575281623182157985423209129457
+GCDE 32052182750761975518649228050096851724 -1
+   -> g = 1
+   -> x = 0
+   -> y = -1
+GCDE 32052182750761975518649228050096851724 -123
+   -> g = 3
+   -> x = -4
+   -> y = -1042347406528844732313796034149491113
+GCDE 32052182750761975518649228050096851724 -123456789456789456789456789456789456789465789465456789465454645789
+   -> g = 1
+   -> x = -10203432759063496909071922280945854833629276496909075027106202353
+   -> y = -2649042575281623182157985423209129457
+GCDE 32052182750761975518649228050096851724 4567897897897897899789897897978978979789
+   -> g = 1
+   -> x = 1839998972523827338782593728961148005767
+   -> y = -12910967943414004413956938074429250463
+GCDE 32052182750761975518649228050096851724 2988348162058574136915891421498819466320163312926952423791023078876139
+   -> g = 1
+   -> x = 272877565911469778893036529750941765793334087149670477404511983087875
+   -> y = -2926808101621088968857550652617123241
+GCDE 32052182750761975518649228050096851724 2351399303373464486466122544523690094744975233415544072992656881240319
+   -> g = 1
+   -> x = 253778836069059554551347740010931350716760250644753514181097821250371
+   -> y = -3459287250911140032199362006422486237
+GCDE 32052182750761975518649228050096851724 5328841272400314897981163497728751426
+   -> g = 92889294
+   -> x = -19137667681784054624628973533
+   -> y = 115110207004456909698806038261
+GCDE 32052182750761975518649228050096851724 32052182750761975518649228050096851724
+   -> g = 32052182750761975518649228050096851724
+   -> x = 0
+   -> y = 1
+GCDE 2 36893488147419103233
+   -> g = 1
+   -> x = -18446744073709551616
+   -> y = 1
+GCDE 2 -36893488147419103233
+   -> g = 1
+   -> x = -18446744073709551616
+   -> y = -1
+GCDE -2 36893488147419103233
+   -> g = 1
+   -> x = 18446744073709551616
+   -> y = 1
+GCDE -2 -36893488147419103233
+   -> g = 1
+   -> x = 18446744073709551616
+   -> y = -1
+GCDE 36893488147419103233 2
+   -> g = 1
+   -> x = 1
+   -> y = -18446744073709551616
+GCDE 36893488147419103233 -2
+   -> g = 1
+   -> x = 1
+   -> y = 18446744073709551616
+GCDE -36893488147419103233 2
+   -> g = 1
+   -> x = -1
+   -> y = -18446744073709551616
+GCDE -36893488147419103233 -2
+   -> g = 1
+   -> x = -1
+   -> y = 18446744073709551616
diff --git a/testsuite/tests/lib/integer/integerGcdExt.hs b/testsuite/tests/lib/integer/integerGcdExt.hs
index d060c2d3b2..2457b1ced2 100644
--- a/testsuite/tests/lib/integer/integerGcdExt.hs
+++ b/testsuite/tests/lib/integer/integerGcdExt.hs
@@ -9,10 +9,10 @@ import Control.Monad
 
 import GHC.Word
 import GHC.Base
-import qualified GHC.Integer.GMP.Internals as I
+import qualified GHC.Num.Integer as I
 
 gcdExtInteger :: Integer -> Integer -> (Integer, Integer)
-gcdExtInteger a b = case I.gcdExtInteger a b of (# g, s #) -> (g, s)
+gcdExtInteger a b = case I.integerGcde a b of ( g, s, _t ) -> (g, s)
 
 main :: IO ()
 main = do