{-# LANGUAGE CPP #-}
{-# LANGUAGE MagicHash #-}
#if __GLASGOW_HASKELL__ >= 702
{-# LANGUAGE Trustworthy #-}
#endif
module Math.NumberTheory.Logarithms
(
integerLogBase
, integerLog2
, integerLog10
, naturalLogBase
, naturalLog2
, naturalLog10
, intLog2
, wordLog2
, integerLogBase'
, integerLog2'
, integerLog10'
, intLog2'
, wordLog2'
) where
import GHC.Exts
import Data.Bits
import Data.Array.Unboxed
import Numeric.Natural
import GHC.Integer.Logarithms.Compat
#if MIN_VERSION_base(4,8,0) && defined(MIN_VERSION_integer_gmp)
import GHC.Integer.GMP.Internals (Integer (..))
import GHC.Natural
#endif
#if CheckBounds
import Data.Array.IArray (IArray, (!))
#else
import Data.Array.Base (unsafeAt)
#endif
integerLogBase :: Integer -> Integer -> Int
integerLogBase :: Integer -> Integer -> Int
integerLogBase b :: Integer
b n :: Integer
n
| Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 1 = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error "Math.NumberTheory.Logarithms.integerLogBase: argument must be positive."
| Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
b = 0
| Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== 2 = Integer -> Int
integerLog2' Integer
n
| Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 2 = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error "Math.NumberTheory.Logarithms.integerLogBase: base must be greater than one."
| Bool
otherwise = Integer -> Integer -> Int
integerLogBase' Integer
b Integer
n
integerLog2 :: Integer -> Int
integerLog2 :: Integer -> Int
integerLog2 n :: Integer
n
| Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 1 = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error "Math.NumberTheory.Logarithms.integerLog2: argument must be positive"
| Bool
otherwise = Int# -> Int
I# (Integer -> Int#
integerLog2# Integer
n)
naturalLogBase :: Natural -> Natural -> Int
naturalLogBase :: Natural -> Natural -> Int
naturalLogBase b :: Natural
b n :: Natural
n
| Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< 1 = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error "Math.NumberTheory.Logarithms.naturalLogBase: argument must be positive."
| Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Natural
b = 0
| Natural
b Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
== 2 = Natural -> Int
naturalLog2' Natural
n
| Natural
b Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< 2 = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error "Math.NumberTheory.Logarithms.naturalLogBase: base must be greater than one."
| Bool
otherwise = Natural -> Natural -> Int
naturalLogBase' Natural
b Natural
n
naturalLog2 :: Natural -> Int
naturalLog2 :: Natural -> Int
naturalLog2 n :: Natural
n
| Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< 1 = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error "Math.NumberTheory.Logarithms.naturalLog2: argument must be non-zero"
| Bool
otherwise = Int# -> Int
I# (Natural -> Int#
naturalLog2# Natural
n)
intLog2 :: Int -> Int
intLog2 :: Int -> Int
intLog2 (I# i# :: Int#
i#)
| Int# -> Bool
isTrue# (Int#
i# Int# -> Int# -> Int#
<# 1#) = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error "Math.NumberTheory.Logarithms.intLog2: argument must be positive"
| Bool
otherwise = Int# -> Int
I# (Word# -> Int#
wordLog2# (Int# -> Word#
int2Word# Int#
i#))
wordLog2 :: Word -> Int
wordLog2 :: Word -> Int
wordLog2 (W# w# :: Word#
w#)
| Int# -> Bool
isTrue# (Word#
w# Word# -> Word# -> Int#
`eqWord#` 0##) = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error "Math.NumberTheory.Logarithms.wordLog2: argument must not be 0."
| Bool
otherwise = Int# -> Int
I# (Word# -> Int#
wordLog2# Word#
w#)
integerLog2' :: Integer -> Int
integerLog2' :: Integer -> Int
integerLog2' n :: Integer
n = Int# -> Int
I# (Integer -> Int#
integerLog2# Integer
n)
naturalLog2' :: Natural -> Int
naturalLog2' :: Natural -> Int
naturalLog2' n :: Natural
n = Int# -> Int
I# (Natural -> Int#
naturalLog2# Natural
n)
intLog2' :: Int -> Int
intLog2' :: Int -> Int
intLog2' (I# i# :: Int#
i#) = Int# -> Int
I# (Word# -> Int#
wordLog2# (Int# -> Word#
int2Word# Int#
i#))
wordLog2' :: Word -> Int
wordLog2' :: Word -> Int
wordLog2' (W# w# :: Word#
w#) = Int# -> Int
I# (Word# -> Int#
wordLog2# Word#
w#)
integerLog10 :: Integer -> Int
integerLog10 :: Integer -> Int
integerLog10 n :: Integer
n
| Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 1 = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error "Math.NumberTheory.Logarithms.integerLog10: argument must be positive"
| Bool
otherwise = Integer -> Int
integerLog10' Integer
n
naturalLog10 :: Natural -> Int
naturalLog10 :: Natural -> Int
naturalLog10 n :: Natural
n
| Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< 1 = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error "Math.NumberTheory.Logarithms.naturalaLog10: argument must be non-zero"
| Bool
otherwise = Natural -> Int
naturalLog10' Natural
n
integerLog10' :: Integer -> Int
integerLog10' :: Integer -> Int
integerLog10' n :: Integer
n
| Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 10 = 0
| Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 100 = 1
| Bool
otherwise = Int
ex Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Integer -> Int
integerLog10' (Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`quot` 10 Integer -> Int -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
ex)
where
ln :: Int
ln = Int# -> Int
I# (Integer -> Int#
integerLog2# Integer
n)
u :: Integer
u = 1936274
v :: Integer
v = 6432163
ex :: Int
ex = Integer -> Int
forall a. Num a => Integer -> a
fromInteger ((Integer
u Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
ln) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`quot` Integer
v)
naturalLog10' :: Natural -> Int
naturalLog10' :: Natural -> Int
naturalLog10' n :: Natural
n
| Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< 10 = 0
| Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< 100 = 1
| Bool
otherwise = Int
ex Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Natural -> Int
naturalLog10' (Natural
n Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
`quot` 10 Natural -> Int -> Natural
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
ex)
where
ln :: Int
ln = Int# -> Int
I# (Natural -> Int#
naturalLog2# Natural
n)
u :: Integer
u = 1936274
v :: Integer
v = 6432163
ex :: Int
ex = Integer -> Int
forall a. Num a => Integer -> a
fromInteger ((Integer
u Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
ln) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`quot` Integer
v)
integerLogBase' :: Integer -> Integer -> Int
integerLogBase' :: Integer -> Integer -> Int
integerLogBase' b :: Integer
b n :: Integer
n
| Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
b = 0
| Int
lnInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
lb Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
lb = 1
| Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< 33 = let bi :: Int
bi = Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
b
ix :: Int
ix = 2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
biInt -> Int -> Int
forall a. Num a => a -> a -> a
-4
u :: Int
u = UArray Int Int
logArr UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` Int
ix
v :: Int
v = UArray Int Int
logArr UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` (Int
ixInt -> Int -> Int
forall a. Num a => a -> a -> a
+1)
ex :: Int
ex = Integer -> Int
forall a. Num a => Integer -> a
fromInteger ((Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
u Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
ln) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`quot` Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
v)
in case Int
u of
1 -> Int
ln Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
v
_ -> Int
ex Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Integer -> Integer -> Int
integerLogBase' Integer
b (Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`quot` Integer
b Integer -> Int -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
ex)
| Bool
otherwise = let
bi :: Int
bi = Integer -> Int
forall a. Num a => Integer -> a
fromInteger (Integer
b Integer -> Int -> Integer
forall a. Bits a => a -> Int -> a
`shiftR` (Int
lbInt -> Int -> Int
forall a. Num a => a -> a -> a
-4))
ix :: Int
ix = 2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
biInt -> Int -> Int
forall a. Num a => a -> a -> a
-2
u :: Integer
u = Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Integer) -> Int -> Integer
forall a b. (a -> b) -> a -> b
$ UArray Int Int
logArr UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` Int
ix
v :: Integer
v = Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Integer) -> Int -> Integer
forall a b. (a -> b) -> a -> b
$ UArray Int Int
logArr UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` (Int
ixInt -> Int -> Int
forall a. Num a => a -> a -> a
+1)
w :: Integer
w = Integer
v Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
+ Integer
uInteger -> Integer -> Integer
forall a. Num a => a -> a -> a
*Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
lbInt -> Int -> Int
forall a. Num a => a -> a -> a
-4)
ex :: Int
ex = Integer -> Int
forall a. Num a => Integer -> a
fromInteger ((Integer
u Integer -> Integer -> Integer
forall a. Num a => a -> a -> a
* Int -> Integer
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
ln) Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`quot` Integer
w)
in Int
ex Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Integer -> Integer -> Int
integerLogBase' Integer
b (Integer
n Integer -> Integer -> Integer
forall a. Integral a => a -> a -> a
`quot` Integer
b Integer -> Int -> Integer
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
ex)
where
lb :: Int
lb = Integer -> Int
integerLog2' Integer
b
ln :: Int
ln = Integer -> Int
integerLog2' Integer
n
naturalLogBase' :: Natural -> Natural -> Int
naturalLogBase' :: Natural -> Natural -> Int
naturalLogBase' b :: Natural
b n :: Natural
n
| Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Natural
b = 0
| Int
lnInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
lb Int -> Int -> Bool
forall a. Ord a => a -> a -> Bool
< Int
lb = 1
| Natural
b Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< 33 = let bi :: Int
bi = Natural -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Natural
b
ix :: Int
ix = 2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
biInt -> Int -> Int
forall a. Num a => a -> a -> a
-4
u :: Int
u = UArray Int Int
logArr UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` Int
ix
v :: Int
v = UArray Int Int
logArr UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` (Int
ixInt -> Int -> Int
forall a. Num a => a -> a -> a
+1)
ex :: Int
ex = Natural -> Int
forall a. Num a => Natural -> a
fromNatural ((Int -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
u Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
* Int -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
ln) Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
`quot` Int -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
v)
in case Int
u of
1 -> Int
ln Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
v
_ -> Int
ex Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Natural -> Natural -> Int
naturalLogBase' Natural
b (Natural
n Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
`quot` Natural
b Natural -> Int -> Natural
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
ex)
| Bool
otherwise = let
bi :: Int
bi = Natural -> Int
forall a. Num a => Natural -> a
fromNatural (Natural
b Natural -> Int -> Natural
forall a. Bits a => a -> Int -> a
`shiftR` (Int
lbInt -> Int -> Int
forall a. Num a => a -> a -> a
-4))
ix :: Int
ix = 2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
biInt -> Int -> Int
forall a. Num a => a -> a -> a
-2
u :: Natural
u = Int -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Natural) -> Int -> Natural
forall a b. (a -> b) -> a -> b
$ UArray Int Int
logArr UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` Int
ix
v :: Natural
v = Int -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int -> Natural) -> Int -> Natural
forall a b. (a -> b) -> a -> b
$ UArray Int Int
logArr UArray Int Int -> Int -> Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
a i e -> Int -> e
`unsafeAt` (Int
ixInt -> Int -> Int
forall a. Num a => a -> a -> a
+1)
w :: Natural
w = Natural
v Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
+ Natural
uNatural -> Natural -> Natural
forall a. Num a => a -> a -> a
*Int -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral (Int
lbInt -> Int -> Int
forall a. Num a => a -> a -> a
-4)
ex :: Int
ex = Natural -> Int
forall a. Num a => Natural -> a
fromNatural ((Natural
u Natural -> Natural -> Natural
forall a. Num a => a -> a -> a
* Int -> Natural
forall a b. (Integral a, Num b) => a -> b
fromIntegral Int
ln) Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
`quot` Natural
w)
in Int
ex Int -> Int -> Int
forall a. Num a => a -> a -> a
+ Natural -> Natural -> Int
naturalLogBase' Natural
b (Natural
n Natural -> Natural -> Natural
forall a. Integral a => a -> a -> a
`quot` Natural
b Natural -> Int -> Natural
forall a b. (Num a, Integral b) => a -> b -> a
^ Int
ex)
where
lb :: Int
lb = Natural -> Int
naturalLog2' Natural
b
ln :: Int
ln = Natural -> Int
naturalLog2' Natural
n
logArr :: UArray Int Int
logArr :: UArray Int Int
logArr = (Int, Int) -> [Int] -> UArray Int Int
forall (a :: * -> * -> *) e i.
(IArray a e, Ix i) =>
(i, i) -> [e] -> a i e
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
]
#if CheckBounds
unsafeAt :: (IArray a e, Ix i) => a i e -> i -> e
unsafeAt = (!)
#endif
fromNatural :: Num a => Natural -> a
fromNatural :: Natural -> a
fromNatural = Natural -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral
naturalLog2# :: Natural -> Int#
#if MIN_VERSION_base(4,8,0) && defined(MIN_VERSION_integer_gmp)
naturalLog2# :: Natural -> Int#
naturalLog2# (NatS# b :: Word#
b) = Word# -> Int#
wordLog2# Word#
b
naturalLog2# (NatJ# n :: BigNat
n) = Integer -> Int#
integerLog2# (BigNat -> Integer
Jp# BigNat
n)
#else
naturalLog2# n = integerLog2# (toInteger n)
#endif
#if __GLASGOW_HASKELL__ < 707
isTrue# :: Bool -> Bool
isTrue# = id
#endif