| 1 |
-- | |
| 2 |
-- Module: Math.NumberTheory.Powers.Integer |
| 3 |
-- Copyright: (c) 2011-2014 Daniel Fischer |
| 4 |
-- Licence: MIT |
| 5 |
-- Maintainer: Daniel Fischer <[email protected]> |
| 6 |
-- Stability: Provisional |
| 7 |
-- Portability: Non-portable (GHC extensions) |
| 8 |
-- |
| 9 |
-- Potentially faster power function for 'Integer' base and 'Int' |
| 10 |
-- or 'Word' exponent. |
| 11 |
-- |
| 12 |
{-# LANGUAGE Safe #-} |
| 13 |
module Math.NumberTheory.Powers.Integer |
| 14 |
{-# DEPRECATED "It is no faster than (^)" #-} |
| 15 |
( integerPower |
| 16 |
, integerWordPower |
| 17 |
) where |
| 18 |
|
| 19 |
-- | Power of an 'Integer' by the left-to-right repeated squaring algorithm. |
| 20 |
-- This needs two multiplications in each step while the right-to-left |
| 21 |
-- algorithm needs only one multiplication for 0-bits, but here the |
| 22 |
-- two factors always have approximately the same size, which on average |
| 23 |
-- gains a bit when the result is large. |
| 24 |
-- |
| 25 |
-- For small results, it is unlikely to be any faster than '(^)', quite |
| 26 |
-- possibly slower (though the difference shouldn't be large), and for |
| 27 |
-- exponents with few bits set, the same holds. But for exponents with |
| 28 |
-- many bits set, the speedup can be significant. |
| 29 |
-- |
| 30 |
-- /Warning:/ No check for the negativity of the exponent is performed, |
| 31 |
-- a negative exponent is interpreted as a large positive exponent. |
| 32 |
integerPower :: Integer -> Int -> Integer |
| 33 |
integerPower = (^) |
| 34 |
{-# DEPRECATED integerPower "Use (^) instead" #-} |
| 35 |
|
| 36 |
-- | Same as 'integerPower', but for exponents of type 'Word'. |
| 37 |
integerWordPower :: Integer -> Word -> Integer |
| 38 |
integerWordPower = (^) |
| 39 |
{-# DEPRECATED integerWordPower "Use (^) instead" #-} |