-- Hoogle documentation, generated by Haddock
-- See Hoogle, http://www.haskell.org/hoogle/


-- | Integer logarithms.
--   
--   <a>Math.NumberTheory.Logarithms</a> and
--   <a>Math.NumberTheory.Powers.Integer</a> from the arithmoi package.
--   
--   Also provides <a>GHC.Integer.Logarithms.Compat</a> and
--   <a>Math.NumberTheory.Power.Natural</a> modules, as well as some
--   additional functions in migrated modules.
@package integer-logarithms
@version 1.0.2


-- | Potentially faster power function for <a>Natural</a> base and
--   <a>Int</a> or <a>Word</a> exponent.

-- | <i>Deprecated: It is no faster than (^)</i>
module Math.NumberTheory.Powers.Natural

-- | Power of an <a>Natural</a> by the left-to-right repeated squaring
--   algorithm. This needs two multiplications in each step while the
--   right-to-left algorithm needs only one multiplication for 0-bits, but
--   here the two factors always have approximately the same size, which on
--   average gains a bit when the result is large.
--   
--   For small results, it is unlikely to be any faster than '(^)', quite
--   possibly slower (though the difference shouldn't be large), and for
--   exponents with few bits set, the same holds. But for exponents with
--   many bits set, the speedup can be significant.
--   
--   <i>Warning:</i> No check for the negativity of the exponent is
--   performed, a negative exponent is interpreted as a large positive
--   exponent.
naturalPower :: Natural -> Int -> Natural

-- | Same as <a>naturalPower</a>, but for exponents of type <a>Word</a>.
naturalWordPower :: Natural -> Word -> Natural


-- | Potentially faster power function for <a>Integer</a> base and
--   <a>Int</a> or <a>Word</a> exponent.

-- | <i>Deprecated: It is no faster than (^)</i>
module Math.NumberTheory.Powers.Integer

-- | Power of an <a>Integer</a> by the left-to-right repeated squaring
--   algorithm. This needs two multiplications in each step while the
--   right-to-left algorithm needs only one multiplication for 0-bits, but
--   here the two factors always have approximately the same size, which on
--   average gains a bit when the result is large.
--   
--   For small results, it is unlikely to be any faster than '(^)', quite
--   possibly slower (though the difference shouldn't be large), and for
--   exponents with few bits set, the same holds. But for exponents with
--   many bits set, the speedup can be significant.
--   
--   <i>Warning:</i> No check for the negativity of the exponent is
--   performed, a negative exponent is interpreted as a large positive
--   exponent.
integerPower :: Integer -> Int -> Integer

-- | Same as <a>integerPower</a>, but for exponents of type <a>Word</a>.
integerWordPower :: Integer -> Word -> Integer


-- | Low level stuff for integer logarithms.
module GHC.Integer.Logarithms.Compat

-- | Calculate the integer logarithm for an arbitrary base.
--   
--   The base must be greater than <tt>1</tt>, the second argument, the
--   number whose logarithm is sought, shall be positive, otherwise the
--   result is meaningless.
--   
--   The following property holds
--   
--   <pre>
--   base ^ <a>integerLogBase#</a> base m &lt;= m &lt; base ^(<a>integerLogBase#</a> base m + 1)
--   </pre>
--   
--   for <tt>base &gt; 1</tt> and <tt>m &gt; 0</tt>.
--   
--   Note: Internally uses <a>integerLog2#</a> for base 2
integerLogBase# :: Integer -> Integer -> Int#

-- | Calculate the integer base 2 logarithm of an <a>Integer</a>. The
--   calculation is more efficient than for the general case, on platforms
--   with 32- or 64-bit words much more efficient.
--   
--   The argument must be strictly positive, that condition is <i>not</i>
--   checked.
integerLog2# :: Integer -> Int#

-- | Compute base-2 log of <a>Word#</a>
--   
--   This is internally implemented as count-leading-zeros machine
--   instruction.
wordLog2# :: Word# -> Int#


-- | Integer Logarithms. For efficiency, the internal representation of
--   <a>Integer</a>s from integer-gmp is used.
module Math.NumberTheory.Logarithms

-- | 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 <tt>base ==
--   2</tt>, the specialised version is called, which is more efficient
--   than the general algorithm.
--   
--   Satisfies:
--   
--   <pre>
--   base ^ integerLogBase base m &lt;= m &lt; base ^ (integerLogBase base m + 1)
--   </pre>
--   
--   for <tt>base &gt; 1</tt> and <tt>m &gt; 0</tt>.
integerLogBase :: Integer -> Integer -> Int

-- | Calculate the integer logarithm of an <a>Integer</a> to base 2. The
--   argument must be positive, otherwise an error is thrown.
integerLog2 :: Integer -> Int

-- | Calculate the integer logarithm of an <a>Integer</a> to base 10. The
--   argument must be positive, otherwise an error is thrown.
integerLog10 :: Integer -> Int

-- | 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 <tt>base ==
--   2</tt>, the specialised version is called, which is more efficient
--   than the general algorithm.
--   
--   Satisfies:
--   
--   <pre>
--   base ^ integerLogBase base m &lt;= m &lt; base ^ (integerLogBase base m + 1)
--   </pre>
--   
--   for <tt>base &gt; 1</tt> and <tt>m &gt; 0</tt>.
naturalLogBase :: Natural -> Natural -> Int

-- | Calculate the natural logarithm of an <a>Natural</a> to base 2. The
--   argument must be non-zero, otherwise an error is thrown.
naturalLog2 :: Natural -> Int

-- | Calculate the integer logarithm of an <a>Integer</a> to base 10. The
--   argument must be not zero, otherwise an error is thrown.
naturalLog10 :: Natural -> Int

-- | Calculate the integer logarithm of an <a>Int</a> to base 2. The
--   argument must be positive, otherwise an error is thrown.
intLog2 :: Int -> Int

-- | Calculate the integer logarithm of a <a>Word</a> to base 2. The
--   argument must be positive, otherwise an error is thrown.
wordLog2 :: Word -> Int

-- | Same as <a>integerLogBase</a>, but without checks, saves a little time
--   when called often for known good input.
integerLogBase' :: Integer -> Integer -> Int

-- | Same as <a>integerLog2</a>, but without checks, saves a little time
--   when called often for known good input.
integerLog2' :: Integer -> Int

-- | Same as <a>integerLog10</a>, but without a check for a positive
--   argument. Saves a little time when called often for known good input.
integerLog10' :: Integer -> Int

-- | Same as <a>intLog2</a>, but without checks, saves a little time when
--   called often for known good input.
intLog2' :: Int -> Int

-- | Same as <a>wordLog2</a>, but without checks, saves a little time when
--   called often for known good input.
wordLog2' :: Word -> Int