[GHC] #9120: Cache intermediate powers

[GHC]

#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