[GHC] #1687: A faster (^)-function.

[GHC]

#1687: A faster (^)-function.
--------------------------------------------+-----------------------------
        Reporter:  moonlite@…               |                Owner:
            Type:  bug                      |               Status:  new
        Priority:  normal                   |            Milestone:  ⊥
       Component:  Prelude                  |              Version:  6.6.1
      Resolution:                           |             Keywords:
Operating System:  Linux                    |         Architecture:  x86
 Type of failure:  Runtime performance bug  |            Test Case:
      Blocked By:                           |             Blocking:
 Related Tickets:                           |  Differential Rev(s):
       Wiki Page:                           |
--------------------------------------------+-----------------------------

Comment (by siddhanathan):

 rwbarton explained this earlier, but it took a while to wrap my head
 around it.

 I find this a bit clearer to understand:


 {{{
 {-# SPECIALISE [1] (^) ::
         Integer -> Integer -> Integer,
         Integer -> Int -> Integer,
         Int -> Int -> Int #-}
 {-# INLINABLE [1] (^) #-}    -- See Note [Inlining (^)]
 (^) :: (Num a, Integral b) => a -> b -> a
 x0 ^ y0 | y0 < 0    = errorWithoutStackTrace "Negative exponent"
         | y0 == 0   = 1
         | otherwise = f x0 y0 1
     where
           f x y z | even y    = let k = f x (y `quot` 2) z in k * k
                   | y == 1    = x * z
                   | otherwise = let k = f x ((y - 1) `quot` 2) z in k * k
 * x

 }}}

 This has identical performance to the version in the description above.

 This makes use of the fact that x^2a^ = x^a+a^ = x^a^ * x^a^ ; and x^2a+1^
 = x^a^ * x^a^ * x

--
Ticket URL: <http://ghc.haskell.org/trac/ghc/ticket/1687#comment:18>
GHC <http://www.haskell.org/ghc/>
The Glasgow Haskell Compiler