Fix gcdExtInteger (trac#15350)
authorBodigrim <andrew.lelechenko@gmail.com>
Fri, 6 Jul 2018 23:20:10 +0000 (00:20 +0100)
committerBen Gamari <ben@smart-cactus.org>
Thu, 23 Aug 2018 19:16:21 +0000 (15:16 -0400)
(cherry picked from commit 7c207c86ab0de955ebec70eeeb366ba0d94acc4a)

libraries/integer-gmp/src/GHC/Integer/Type.hs

index 9ea7c06..9636b9f 100644 (file)
@@ -1389,7 +1389,9 @@ gcdExtSBigNat x y = case runS go of (g,s) -> (# g, s #)
   where
     go = do
         g@(MBN# g#) <- newBigNat# gn0#
-        s@(MBN# s#) <- newBigNat# (absI# xn#)
+        -- According to https://gmplib.org/manual/Number-Theoretic-Functions.html#index-mpz_005fgcdext
+        -- abs(s) < abs(y) / (2 g)
+        s@(MBN# s#) <- newBigNat# (absI# yn#)
         I# ssn_# <- liftIO (integer_gmp_gcdext# s# g# x# xn# y# yn#)
         let ssn# = narrowGmpSize# ssn_#
             sn#  = absI# ssn#