module Math.NumberTheory.Logarithms
(
integerLogBase
, integerLog2
, integerLog10
, intLog2
, wordLog2
, integerLogBase'
, integerLog2'
, integerLog10'
, intLog2'
, wordLog2'
) where
import GHC.Base
#if __GLASGOW_HASKELL__ < 705
import GHC.Word (Word(..))
#endif
import Data.Bits
import Data.Array.Unboxed
import Data.Array.Base (unsafeAt)
import Math.NumberTheory.Logarithms.Internal
import Math.NumberTheory.Powers.Integer
#if __GLASGOW_HASKELL__ < 707
import Math.NumberTheory.Utils (isTrue#)
#endif
integerLogBase :: Integer -> Integer -> Int
integerLogBase b n
| n < 1 = error "Math.NumberTheory.Logarithms.integerLogBase: argument must be positive."
| n < b = 0
| b == 2 = integerLog2' n
| b < 2 = error "Math.NumberTheory.Logarithms.integerLogBase: base must be greater than one."
| otherwise = integerLogBase' b n
integerLog2 :: Integer -> Int
integerLog2 n
| n < 1 = error "Math.NumberTheory.Logarithms.integerLog2: argument must be positive"
| otherwise = I# (integerLog2# n)
intLog2 :: Int -> Int
intLog2 (I# i#)
| isTrue# (i# <# 1#) = error "Math.NumberTheory.Logarithms.intLog2: argument must be positive"
| otherwise = I# (wordLog2# (int2Word# i#))
wordLog2 :: Word -> Int
wordLog2 (W# w#)
| isTrue# (w# `eqWord#` 0##) = error "Math.NumberTheory.Logarithms.wordLog2: argument must not be 0."
| otherwise = I# (wordLog2# w#)
integerLog2' :: Integer -> Int
integerLog2' n = I# (integerLog2# n)
intLog2' :: Int -> Int
intLog2' (I# i#) = I# (wordLog2# (int2Word# i#))
wordLog2' :: Word -> Int
wordLog2' (W# w#) = I# (wordLog2# w#)
integerLog10 :: Integer -> Int
integerLog10 n
| n < 1 = error "Math.NumberTheory.Logarithms.integerLog10: argument must be positive"
| otherwise = integerLog10' n
integerLog10' :: Integer -> Int
integerLog10' n
| n < 10 = 0
| n < 100 = 1
| otherwise = ex + integerLog10' (n `quot` integerPower 10 ex)
where
ln = I# (integerLog2# n)
u = 1936274
v = 6432163
ex = fromInteger ((u * fromIntegral ln) `quot` v)
integerLogBase' :: Integer -> Integer -> Int
integerLogBase' b n
| n < b = 0
| lnlb < lb = 1
| b < 33 = let bi = fromInteger b
ix = 2*bi4
u = logArr `unsafeAt` ix
v = logArr `unsafeAt` (ix+1)
ex = fromInteger ((fromIntegral u * fromIntegral ln) `quot` fromIntegral v)
in case u of
1 -> ln `quot` v
_ -> ex + integerLogBase' b (n `quot` integerPower b ex)
| otherwise = let
bi = fromInteger (b `shiftR` (lb4))
ix = 2*bi2
u = fromIntegral $ logArr `unsafeAt` ix
v = fromIntegral $ logArr `unsafeAt` (ix+1)
w = v + u*fromIntegral (lb4)
ex = fromInteger ((u * fromIntegral ln) `quot` w)
in ex + integerLogBase' b (n `quot` integerPower b ex)
where
lb = integerLog2' b
ln = integerLog2' n
logArr :: UArray Int Int
logArr = listArray (0, 61)
[ 1 , 1,
190537 , 301994,
1 , 2,
1936274 , 4495889,
190537 , 492531,
91313 , 256348,
1 , 3,
190537 , 603988,
1936274 , 6432163,
1686227 , 5833387,
190537 , 683068,
5458 , 20197,
91313 , 347661,
416263 , 1626294,
1 , 4,
32631 , 133378,
190537 , 794525,
163451 , 694328,
1936274 , 8368437,
1454590 , 6389021,
1686227 , 7519614,
785355 , 3552602,
190537 , 873605,
968137 , 4495889,
5458 , 25655,
190537 , 905982,
91313 , 438974,
390321 , 1896172,
416263 , 2042557,
709397 , 3514492,
1 , 5
]