Cache intermediate powers
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.
Trac metadata
Trac field | Value |
---|---|
Version | 7.8.2 |
Type | Bug |
TypeOfFailure | OtherFailure |
Priority | normal |
Resolution | Unresolved |
Component | Compiler |
Test case | |
Differential revisions | |
BlockedBy | |
Related | |
Blocking | |
CC | |
Operating system | |
Architecture |