Debian Codegraph @

src/Math/NumberTheory/Powers/Integer.hs

raw
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" #-}