    -- |
    -- 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