-- |
-- Module:      Math.NumberTheory.Logarithms
-- Copyright:   (c) 2011 Daniel Fischer
-- Licence:     MIT
-- Maintainer:  Daniel Fischer <daniel.is.fischer@googlemail.com>
-- Stability:   Provisional
-- Portability: Non-portable (GHC extensions)
--
-- Integer Logarithms. For efficiency, the internal representation of 'Integer's
-- from integer-gmp is used.
--
{-# LANGUAGE CPP #-}
{-# LANGUAGE MagicHash #-}
{-# LANGUAGE Trustworthy #-}
module Math.NumberTheory.Logarithms
    ( -- * Integer logarithms with input checks
      integerLogBase
    , integerLog2
    , integerLog10

    , naturalLogBase
    , naturalLog2
    , naturalLog10

    , intLog2
    , wordLog2

      -- * Integer logarithms without input checks
      --
      -- | These functions are total, however, don't rely on the values with out-of-domain arguments.
    , integerLogBase'
    , integerLog2'
    , integerLog10'

    , intLog2'
    , wordLog2'
    ) where

import GHC.Exts

import Data.Bits
import Data.Array.Unboxed
import Numeric.Natural

#ifdef MIN_VERSION_ghc_bignum
import qualified GHC.Num.Natural as BN
#endif

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

-- | Calculate the integer logarithm for an arbitrary base.
--   The base must be greater than 1, the second argument, the number
--   whose logarithm is sought, must be positive, otherwise an error is thrown.
--   If @base == 2@, the specialised version is called, which is more
--   efficient than the general algorithm.
--
--   Satisfies:
--
-- > base ^ integerLogBase base m <= m < base ^ (integerLogBase base m + 1)
--
-- for @base > 1@ and @m > 0@.
integerLogBase :: Integer -> Integer -> Int
integerLogBase :: Integer -> Integer -> Int
integerLogBase Integer
b Integer
n
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
1       = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Logarithms.integerLogBase: argument must be positive."
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
b       = Int
0
  | Integer
b Integer -> Integer -> Bool
forall a. Eq a => a -> a -> Bool
== Integer
2      = Integer -> Int
integerLog2' Integer
n
  | Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
2       = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Logarithms.integerLogBase: base must be greater than one."
  | Bool
otherwise   = Integer -> Integer -> Int
integerLogBase' Integer
b Integer
n

-- | Calculate the integer logarithm of an 'Integer' to base 2.
--   The argument must be positive, otherwise an error is thrown.
integerLog2 :: Integer -> Int
integerLog2 :: Integer -> Int
integerLog2 Integer
n
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
1       = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Logarithms.integerLog2: argument must be positive"
  | Bool
otherwise   = Int# -> Int
I# (Integer -> Int#
integerLog2# Integer
n)

-- | Cacluate the integer logarithm for an arbitrary base.
--   The base must be greater than 1, the second argument, the number
--   whose logarithm is sought, must be positive, otherwise an error is thrown.
--   If @base == 2@, the specialised version is called, which is more
--   efficient than the general algorithm.
--
--   Satisfies:
--
-- > base ^ integerLogBase base m <= m < base ^ (integerLogBase base m + 1)
--
-- for @base > 1@ and @m > 0@.
naturalLogBase :: Natural -> Natural -> Int
naturalLogBase :: Natural -> Natural -> Int
naturalLogBase Natural
b Natural
n
  | Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Natural
1       = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Logarithms.naturalLogBase: argument must be positive."
  | Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Natural
b       = Int
0
  | Natural
b Natural -> Natural -> Bool
forall a. Eq a => a -> a -> Bool
== Natural
2      = Natural -> Int
naturalLog2' Natural
n
  | Natural
b Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Natural
2       = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Logarithms.naturalLogBase: base must be greater than one."
  | Bool
otherwise   = Natural -> Natural -> Int
naturalLogBase' Natural
b Natural
n

-- | Calculate the natural logarithm of an 'Natural' to base 2.
--   The argument must be non-zero, otherwise an error is thrown.
naturalLog2 :: Natural -> Int
naturalLog2 :: Natural -> Int
naturalLog2 Natural
n
  | Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Natural
1       = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Logarithms.naturalLog2: argument must be non-zero"
  | Bool
otherwise   = Int# -> Int
I# (Natural -> Int#
naturalLog2# Natural
n)

-- | Calculate the integer logarithm of an 'Int' to base 2.
--   The argument must be positive, otherwise an error is thrown.
intLog2 :: Int -> Int
intLog2 :: Int -> Int
intLog2 (I# Int#
i#)
  | Int# -> Bool
isTrue# (Int#
i# Int# -> Int# -> Int#
<# Int#
1#)  = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Logarithms.intLog2: argument must be positive"
  | Bool
otherwise           = Int# -> Int
I# (Word# -> Int#
wordLog2# (Int# -> Word#
int2Word# Int#
i#))

-- | Calculate the integer logarithm of a 'Word' to base 2.
--   The argument must be positive, otherwise an error is thrown.
wordLog2 :: Word -> Int
wordLog2 :: Word -> Int
wordLog2 (W# Word#
w#)
  | Int# -> Bool
isTrue# (Word#
w# Word# -> Word# -> Int#
`eqWord#` Word#
0##)  = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Logarithms.wordLog2: argument must not be 0."
  | Bool
otherwise                   = Int# -> Int
I# (Word# -> Int#
wordLog2# Word#
w#)

-- | Same as 'integerLog2', but without checks, saves a little time when
--   called often for known good input.
integerLog2' :: Integer -> Int
integerLog2' :: Integer -> Int
integerLog2' Integer
n = Int# -> Int
I# (Integer -> Int#
integerLog2# Integer
n)

-- | Same as 'naturalLog2', but without checks, saves a little time when
--   called often for known good input.
naturalLog2' :: Natural -> Int
naturalLog2' :: Natural -> Int
naturalLog2' Natural
n = Int# -> Int
I# (Natural -> Int#
naturalLog2# Natural
n)

-- | Same as 'intLog2', but without checks, saves a little time when
--   called often for known good input.
intLog2' :: Int -> Int
intLog2' :: Int -> Int
intLog2' (I# Int#
i#) = Int# -> Int
I# (Word# -> Int#
wordLog2# (Int# -> Word#
int2Word# Int#
i#))

-- | Same as 'wordLog2', but without checks, saves a little time when
--   called often for known good input.
wordLog2' :: Word -> Int
wordLog2' :: Word -> Int
wordLog2' (W# Word#
w#) = Int# -> Int
I# (Word# -> Int#
wordLog2# Word#
w#)

-- | Calculate the integer logarithm of an 'Integer' to base 10.
--   The argument must be positive, otherwise an error is thrown.
integerLog10 :: Integer -> Int
integerLog10 :: Integer -> Int
integerLog10 Integer
n
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
1     = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Logarithms.integerLog10: argument must be positive"
  | Bool
otherwise = Integer -> Int
integerLog10' Integer
n

-- | Calculate the integer logarithm of an 'Integer' to base 10.
--   The argument must be not zero, otherwise an error is thrown.
naturalLog10 :: Natural -> Int
naturalLog10 :: Natural -> Int
naturalLog10 Natural
n
  | Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Natural
1     = [Char] -> Int
forall a. HasCallStack => [Char] -> a
error [Char]
"Math.NumberTheory.Logarithms.naturalaLog10: argument must be non-zero"
  | Bool
otherwise = Natural -> Int
naturalLog10' Natural
n

-- | Same as 'integerLog10', but without a check for a positive
--   argument. Saves a little time when called often for known good
--   input.
integerLog10' :: Integer -> Int
integerLog10' :: Integer -> Int
integerLog10' Integer
n
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
10      = Int
0
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
100     = Int
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` Integer
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/v is a good approximation of log 2/log 10
      u :: Integer
u  = Integer
1936274
      v :: Integer
v  = Integer
6432163
      -- so ex is a good approximation to integerLogBase 10 n
      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)

-- | Same as 'naturalLog10', but without a check for a positive
--   argument. Saves a little time when called often for known good
--   input.
naturalLog10' :: Natural -> Int
naturalLog10' :: Natural -> Int
naturalLog10' Natural
n
  | Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Natural
10      = Int
0
  | Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Natural
100     = Int
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` Natural
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/v is a good approximation of log 2/log 10
      u :: Integer
u  = Integer
1936274
      v :: Integer
v  = Integer
6432163
      -- so ex is a good approximation to naturalLogBase 10 n
      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)

-- | Same as 'integerLogBase', but without checks, saves a little time when
--   called often for known good input.
integerLogBase' :: Integer -> Integer -> Int
integerLogBase' :: Integer -> Integer -> Int
integerLogBase' Integer
b Integer
n
  | Integer
n Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
b       = Int
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  = Int
1     -- overflow safe version of ln < 2*lb, implies n < b*b
  | Integer
b Integer -> Integer -> Bool
forall a. Ord a => a -> a -> Bool
< Integer
33      = let bi :: Int
bi = Integer -> Int
forall a. Num a => Integer -> a
fromInteger Integer
b
                      ix :: Int
ix = Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
biInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
4
                      -- u/v is a good approximation of log 2/log b
                      u :: Int
u  = UArray Int Int
logArr UArray Int Int -> Int -> Int
forall i. Ix i => UArray i 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 i. Ix i => UArray i 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
+Int
1)
                      -- hence ex is a rather good approximation of integerLogBase b n
                      -- most of the time, it will already be exact
                      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
                      Int
1 -> Int
ln Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
v      -- a power of 2, easy
                      Int
_ -> 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 -- shift b so that 16 <= bi < 32
                      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
-Int
4))
                      -- we choose an approximation of log 2 / log (bi+1) to
                      -- be sure we underestimate
                      ix :: Int
ix = Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
biInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
2
                      -- u/w is a reasonably good approximation to log 2/log b
                      -- it is too small, but not by much, so the recursive call
                      -- should most of the time be caught by one of the first
                      -- two guards unless n is huge, but then it'd still be
                      -- a call with a much smaller second argument.
                      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 i. Ix i => UArray i 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 i. Ix i => UArray i 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
+Int
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
-Int
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

-- | Same as 'naturalLogBase', but without checks, saves a little time when
--   called often for known good input.
naturalLogBase' :: Natural -> Natural -> Int
naturalLogBase' :: Natural -> Natural -> Int
naturalLogBase' Natural
b Natural
n
    | Natural
n Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Natural
b       = Int
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  = Int
1     -- overflow safe version of ln < 2*lb, implies n < b*b
  | Natural
b Natural -> Natural -> Bool
forall a. Ord a => a -> a -> Bool
< Natural
33      = let bi :: Int
bi = Natural -> Int
forall a b. (Integral a, Num b) => a -> b
fromIntegral Natural
b
                      ix :: Int
ix = Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
biInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
4
                      -- u/v is a good approximation of log 2/log b
                      u :: Int
u  = UArray Int Int
logArr UArray Int Int -> Int -> Int
forall i. Ix i => UArray i 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 i. Ix i => UArray i 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
+Int
1)
                      -- hence ex is a rather good approximation of integerLogBase b n
                      -- most of the time, it will already be exact
                      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
                      Int
1 -> Int
ln Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
v      -- a power of 2, easy
                      Int
_ -> 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 -- shift b so that 16 <= bi < 32
                      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
-Int
4))
                      -- we choose an approximation of log 2 / log (bi+1) to
                      -- be sure we underestimate
                      ix :: Int
ix = Int
2Int -> Int -> Int
forall a. Num a => a -> a -> a
*Int
biInt -> Int -> Int
forall a. Num a => a -> a -> a
-Int
2
                      -- u/w is a reasonably good approximation to log 2/log b
                      -- it is too small, but not by much, so the recursive call
                      -- should most of the time be caught by one of the first
                      -- two guards unless n is huge, but then it'd still be
                      -- a call with a much smaller second argument.
                      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 i. Ix i => UArray i 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 i. Ix i => UArray i 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
+Int
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
-Int
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

-- Lookup table for logarithms of 2 <= k <= 32
-- In each row "x , y", x/y is a good rational approximation of log 2  / log k.
-- For the powers of 2, it is exact, otherwise x/y < log 2/log k, since we don't
-- want to overestimate integerLogBase b n = floor $ (log 2/log b)*logBase 2 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 (Int
0, Int
61)
          [ Int
1 , Int
1,
            Int
190537 , Int
301994,
            Int
1 , Int
2,
            Int
1936274 , Int
4495889,
            Int
190537 , Int
492531,
            Int
91313 , Int
256348,
            Int
1 , Int
3,
            Int
190537 , Int
603988,
            Int
1936274 , Int
6432163,
            Int
1686227 , Int
5833387,
            Int
190537 , Int
683068,
            Int
5458 , Int
20197,
            Int
91313 , Int
347661,
            Int
416263 , Int
1626294,
            Int
1 , Int
4,
            Int
32631 , Int
133378,
            Int
190537 , Int
794525,
            Int
163451 , Int
694328,
            Int
1936274 , Int
8368437,
            Int
1454590 , Int
6389021,
            Int
1686227 , Int
7519614,
            Int
785355 , Int
3552602,
            Int
190537 , Int
873605,
            Int
968137 , Int
4495889,
            Int
5458 , Int
25655,
            Int
190537 , Int
905982,
            Int
91313 , Int
438974,
            Int
390321 , Int
1896172,
            Int
416263 , Int
2042557,
            Int
709397 , Int
3514492,
            Int
1 , Int
5
          ]

-------------------------------------------------------------------------------
-- Unsafe
-------------------------------------------------------------------------------

#if CheckBounds
unsafeAt :: (IArray a e, Ix i) => a i e -> i -> e
unsafeAt = (!)
#endif

-------------------------------------------------------------------------------
-- Natural helpers
-------------------------------------------------------------------------------

fromNatural :: Num a => Natural -> a
fromNatural :: forall a. Num a => Natural -> a
fromNatural = Natural -> a
forall a b. (Integral a, Num b) => a -> b
fromIntegral

naturalLog2# :: Natural -> Int#
#ifdef MIN_VERSION_ghc_bignum
naturalLog2# :: Natural -> Int#
naturalLog2# Natural
n = Word# -> Int#
word2Int# (Natural -> Word#
BN.naturalLog2# Natural
n)
#else
#if MIN_VERSION_base(4,8,0) && defined(MIN_VERSION_integer_gmp)
naturalLog2# (NatS# b) = wordLog2# b
naturalLog2# (NatJ# n) = integerLog2# (Jp# n)
#else
naturalLog2# n = integerLog2# (toInteger n)
#endif
#endif