Re: [GHC] #9617: Implement `quot` and `rem` using `quotRem`; implement `div` and `mod` using `divMod` (was: Try to replace `quot` and `rem` with `quotRem` when possible)

21 Sep 2014

      #9617: Implement `quot` and `rem` using `quotRem`; implement `div` and `mod` using
`divMod`
-------------------------------------+-------------------------------------
              Reporter:  dfeuer      |            Owner:
                  Type:  feature     |           Status:  new
  request                            |        Milestone:
              Priority:  normal      |          Version:  7.9
             Component:  Compiler    |         Keywords:
            Resolution:              |     Architecture:  Unknown/Multiple
      Operating System:              |       Difficulty:  Unknown
  Unknown/Multiple                   |       Blocked By:
       Type of failure:              |  Related Tickets:
  None/Unknown                       |
             Test Case:              |
              Blocking:              |
Differential Revisions:              |
-------------------------------------+-------------------------------------

Comment (by dfeuer):

 Good news:

 It seems it may not even be necessary (for `Int`, at least) to find a way
 to turn the `quotRemInt#` back into `quotInt#` or `remInt#`—the
 performance difference there appears to be somewhere between tiny and
 nonexistent. It's not clear to me whether that will be the same for
 `divMod`, which adds a few more operations over `div` or `mod` (but fast
 ones).

 More good news:

 After bashing my head against it for a few hours, I managed to get
 `divMod` to do what I wanted. I had to swap the divide by zero test with
 the arithmetic overflow test. I don't understand ''why'' this made it
 work, but it seems to have done the job. It looks like this:

 {{{#!hs
 divZeroError# :: Void# -> (# Int#, Int# #)
 divZeroError# a = error "Divide by zero"

 overflowError# :: Void# -> Int#
 overflowError# a = error "Arithmetic overflow: attempted to divide
 minBound by -1"

 divModInt# :: Int# -> Int# -> (# Int#, Int# #)
 x# `divModInt#` y#
  | isTrue# (y# ==# (-1#)) &&
      isTrue# (x# ==# (case minBound of I# mb -> mb))
        = (# overflowError# void#, 0# #)
  | isTrue# (y# ==# 0#) = divZeroError# void#
  | isTrue# (x# ># 0#) && isTrue# (y# <# 0#) =
                                     case (x# -# 1#) `quotRemInt#` y# of
                                       (# q, r #) -> (# q -# 1#, r +# y# +#
 1# #)
  | isTrue# (x# <# 0#) && isTrue# (y# ># 0#) =
                                     case (x# +# 1#) `quotRemInt#` y# of
                                       (# q, r #) -> (# q -# 1#, r +# y# -#
 1# #)
  | otherwise                                =
                                     x# `quotRemInt#` y#

 divModInt :: Int -> Int -> (Int, Int)
 (I# x) `divModInt` (I# y) = case x `divModInt#` y of
                             (# q, r #) -> (I# q, I# r)

 div :: Int -> Int -> Int
 {-# INLINE div #-}
 div x y = fst (divModInt x y)
 infixl 7 `div`

 mod :: Int -> Int -> Int
 {-# INLINE mod #-}
 x `mod` y = snd (divModInt x y)
 infixl 7 `mod`
 }}}

 Using these definitions, it seems things stay sufficiently similar long
 enough for CSE to do its job, so

 {{{#!hs
 divPlusMod :: Int -> Int -> Int
 divPlusMod x y = div x y + mod x y
 }}}

 compiles into something very similar to what you'd get from

 {{{#!hs
 divPlusModStandard :: Int -> Int -> Int
 divPlusModStandard x y = case divMod x y of
                            (q, r) -> q + r
 }}}

 but with the proposed definitions, I'm getting quite a bit less code
 duplication, which seems to be a small but good thing.

--
Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9617#comment:2
GHC http://www.haskell.org/ghc/
The Glasgow Haskell Compiler