module Math.NumberTheory.GCD.LowLevel
(
gcdInt
, gcdWord
, gcdInt#
, gcdWord#
, coprimeInt
, coprimeWord
, coprimeInt#
, coprimeWord#
) where
import GHC.Base
#if __GLASGOW_HASKELL__ < 705
import GHC.Word (Word(..))
#endif
import Math.NumberTheory.Utils
gcdInt :: Int -> Int -> Int
gcdInt (I# a#) (I# b#) = I# (gcdInt# a# b#)
coprimeInt :: Int -> Int -> Bool
coprimeInt (I# a#) (I# b#) = coprimeInt# a# b#
gcdWord :: Word -> Word -> Word
gcdWord (W# a#) (W# b#) = W# (gcdWord# a# b#)
coprimeWord :: Word -> Word -> Bool
coprimeWord (W# a#) (W# b#) = coprimeWord# a# b#
gcdInt# :: Int# -> Int# -> Int#
gcdInt# a# b# = word2Int# (gcdWord# (int2Word# (absInt# a#)) (int2Word# (absInt# b#)))
coprimeInt# :: Int# -> Int# -> Bool
coprimeInt# a# b# = coprimeWord# (int2Word# (absInt# a#)) (int2Word# (absInt# b#))
gcdWord# :: Word# -> Word# -> Word#
gcdWord# a# 0## = a#
gcdWord# 0## b# = b#
gcdWord# a# b# =
case shiftToOddCount# a# of
(# za#, oa# #) ->
case shiftToOddCount# b# of
(# zb#, ob# #) -> gcdWordOdd# oa# ob# `uncheckedShiftL#` (if isTrue# (za# <# zb#) then za# else zb#)
coprimeWord# :: Word# -> Word# -> Bool
coprimeWord# a# b# =
(isTrue# (a# `eqWord#` 1##) || isTrue# (b# `eqWord#` 1##))
|| (isTrue# (((a# `or#` b#) `and#` 1##) `eqWord#` 1##)
&& ((isTrue# (a# `neWord#` 0##) && isTrue# (b# `neWord#` 0##))
&& isTrue# (gcdWordOdd# (shiftToOdd# a#) (shiftToOdd# b#) `eqWord#` 1##)))
gcdWordOdd# :: Word# -> Word# -> Word#
gcdWordOdd# a# b#
| isTrue# (a# `eqWord#` 1##) || isTrue# (b# `eqWord#` 1##) = 1##
| isTrue# (a# `eqWord#` b#) = a#
| isTrue# (a# `ltWord#` b#) = oddGCD# b# a#
| otherwise = oddGCD# a# b#
oddGCD# :: Word# -> Word# -> Word#
oddGCD# a# b# =
case shiftToOdd# (a# `minusWord#` b#) of
1## -> 1##
c# | isTrue# (c# `ltWord#` b#) -> oddGCD# b# c#
| isTrue# (c# `gtWord#` b#) -> oddGCD# c# b#
| otherwise -> c#
absInt# :: Int# -> Int#
absInt# i#
| isTrue# (i# <# 0#) = negateInt# i#
| otherwise = i#