Part of #5122 "Faster conversion between Rational and Double/Float" fix
[packages/integer-gmp.git] / GHC / Integer / Logarithms.hs
1 {-# LANGUAGE MagicHash, UnboxedTuples, NoImplicitPrelude #-}
2 module GHC.Integer.Logarithms
3 ( integerLogBase#
4 , integerLog2#
5 , wordLog2#
6 ) where
7
8 import GHC.Prim
9 import GHC.Integer
10 import qualified GHC.Integer.Logarithms.Internals as I
11
12 -- | Calculate the integer logarithm for an arbitrary base.
13 -- The base must be greater than 1, the second argument, the number
14 -- whose logarithm is sought, should be positive, otherwise the
15 -- result is meaningless.
16 --
17 -- > base ^ integerLogBase# base m <= m < base ^ (integerLogBase# base m + 1)
18 --
19 -- for @base > 1@ and @m > 0@.
20 integerLogBase# :: Integer -> Integer -> Int#
21 integerLogBase# b m = case step b of
22 (# _, e #) -> e
23 where
24 step pw =
25 if m `ltInteger` pw
26 then (# m, 0# #)
27 else case step (pw `timesInteger` pw) of
28 (# q, e #) ->
29 if q `ltInteger` pw
30 then (# q, 2# *# e #)
31 else (# q `quotInteger` pw, 2# *# e +# 1# #)
32
33 -- | Calculate the integer base 2 logarithm of an 'Integer'.
34 -- The calculation is more efficient than for the general case,
35 -- on platforms with 32- or 64-bit words much more efficient.
36 --
37 -- The argument must be strictly positive, that condition is /not/ checked.
38 integerLog2# :: Integer -> Int#
39 integerLog2# = I.integerLog2#
40
41 -- | This function calculates the integer base 2 logarithm of a 'Word#'.
42 wordLog2# :: Word# -> Int#
43 wordLog2# = I.wordLog2#