#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