#9120: Cache intermediate powers ------------------------------------+------------------------------------- Reporter: basvandijk | Owner: Type: bug | Status: new Priority: normal | Milestone: Component: Compiler | Version: 7.8.2 Keywords: | Operating System: Unknown/Multiple Architecture: Unknown/Multiple | Type of failure: None/Unknown Difficulty: Unknown | Test Case: Blocked By: | Blocking: Related Tickets: | ------------------------------------+------------------------------------- `GHC.Float` caches powers of 2 and 10. The arrays of powers are currently constructed using: {{{ expts :: Array Int Integer expts = array (minExpt,maxExpt) [(n,2^n) | n <- [minExpt .. maxExpt]] }}} Unfortunately, the intermediate powers in the `2^n` computation are not stored back in the array, only the result is. I propose to use the following scheme that does store the intermediate powers: {{{ -- | Exponentiation with a cache for the most common numbers. expt :: Integer -> Int -> Integer expt _ e | e < 0 = error "Negative exponent" expt 2 e | e <= maxExpt2 = expts2 ! e | otherwise = expts2 ! maxExpt2 * 2^(e-maxExpt2) expt 10 e | e <= maxExpt10 = expts10 ! e | otherwise = expts10 ! maxExpt10 * 10^(e-maxExpt10) expt base e = base^e maxExpt2 :: Int maxExpt2 = 1100 maxExpt10 :: Int maxExpt10 = 324 expts2 :: Array Int Integer expts2 = expts 2 maxExpt2 expts2 expts10 :: Array Int Integer expts10 = expts 10 maxExpt10 expts10 expts :: Integer -> Int -> Array Int Integer -> Array Int Integer expts base hi arr = listArray (0, hi) $ 1 : base : go 2 where go :: Int -> [Integer] go !ix = xx : base*xx : go (ix+2) where xx = x * x x = arr ! half half = ix `unsafeShiftR` 1 }}} I will attach a patch. -- Ticket URL: http://ghc.haskell.org/trac/ghc/ticket/9120 GHC http://www.haskell.org/ghc/ The Glasgow Haskell Compiler