-- |
-- 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 #-}
#if __GLASGOW_HASKELL__ >= 702
{-# LANGUAGE Trustworthy #-}
#endif
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

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

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

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

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

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

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

-- | Same as 'integerLog2', but without checks, saves a little time when
--   called often for known good input.
integerLog2' :: Integer -> Int
integerLog2' :: Integer -> Int
integerLog2' n :: 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' n :: 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# 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# 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 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

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

-- | 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' 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/v is a good approximation of log 2/log 10
      u :: Integer
u  = 1936274
      v :: Integer
v  = 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' 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/v is a good approximation of log 2/log 10
      u :: Integer
u  = 1936274
      v :: Integer
v  = 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' 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     -- overflow safe version of ln < 2*lb, implies n < b*b
  | 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/v is a good approximation of log 2/log b
                      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)
                      -- 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
                      1 -> Int
ln Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
v      -- a power of 2, easy
                      _ -> 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
-4))
                      -- we choose an approximation of log 2 / log (bi+1) to
                      -- be sure we underestimate
                      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/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 (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

-- | 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' 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     -- overflow safe version of ln < 2*lb, implies n < b*b
  | 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/v is a good approximation of log 2/log b
                      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)
                      -- 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
                      1 -> Int
ln Int -> Int -> Int
forall a. Integral a => a -> a -> a
`quot` Int
v      -- a power of 2, easy
                      _ -> 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
-4))
                      -- we choose an approximation of log 2 / log (bi+1) to
                      -- be sure we underestimate
                      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/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 (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

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

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

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

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

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
-- The times they are a-changing. The types of primops too :(
isTrue# :: Bool -> Bool
isTrue# = id
#endif