arithmoi 0.4.0.4 → 0.4.1.0
raw patch · 4 files changed
+61/−12 lines, 4 filesdep ~integer-gmp
Dependency ranges changed: integer-gmp
Files
- Changes +3/−0
- Math/NumberTheory/Logarithms.hs +30/−2
- Math/NumberTheory/Powers/Integer.hs +26/−8
- arithmoi.cabal +2/−2
Changes view
@@ -1,3 +1,6 @@+0.4.1.0:+ Add integerLog10 variants at Bas van Dijk's request and expose+ Math.NumberTheory.Powers.Integer, with an added integerWordPower. 0.4.0.4: Update for GHC-7.8, the type of some primops changed, they return Int# now instead of Bool.
Math/NumberTheory/Logarithms.hs view
@@ -14,11 +14,16 @@ ( -- * Integer logarithms with input checks integerLogBase , integerLog2+ , integerLog10+ , intLog2 , wordLog2+ -- * Integer logarithms without input checks , integerLogBase' , integerLog2'+ , integerLog10'+ , intLog2' , wordLog2' ) where@@ -94,6 +99,29 @@ wordLog2' :: Word -> Int wordLog2' (W# w#) = I# (wordLog2# 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 n+ | n < 1 = error "Math.NumberTheory.Logarithms.integerLog10: argument must be positive"+ | otherwise = integerLog10' 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' n+ | n < 10 = 0+ | n < 100 = 1+ | otherwise = ex + integerLog10' (n `quot` integerPower 10 ex)+ where+ ln = I# (integerLog2# n)+ -- u/v is a good approximation of log 2/log 10+ u = 1936274+ v = 6432163+ -- so ex is a good approximation to integerLogBase 10 n+ ex = fromInteger ((u * fromIntegral ln) `quot` v)+ -- | Same as 'integerLogBase', but without checks, saves a little time when -- called often for known good input. integerLogBase' :: Integer -> Integer -> Int@@ -127,8 +155,8 @@ ex = fromInteger ((u * fromIntegral ln) `quot` w) in ex + integerLogBase' b (n `quot` integerPower b ex) where- lb = integerLog2 b- ln = integerLog2 n+ lb = integerLog2' b+ ln = integerLog2' 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.
Math/NumberTheory/Powers/Integer.hs view
@@ -1,20 +1,24 @@ -- | -- Module: Math.NumberTheory.Powers.Integer--- Copyright: (c) 2011 Daniel Fischer+-- Copyright: (c) 2011-2014 Daniel Fischer -- Licence: MIT -- Maintainer: Daniel Fischer <daniel.is.fischer@googlemail.com> -- Stability: Provisional -- Portability: Non-portable (GHC extensions) ----- Slightly faster power function for Integer base and Int exponent.+-- Potentially faster power function for 'Integer' base and 'Int'+-- or 'Word' exponent. -- {-# LANGUAGE MagicHash, BangPatterns, CPP #-}-{-# OPTIONS_HADDOCK hide #-} module Math.NumberTheory.Powers.Integer ( integerPower+ , integerWordPower ) where import GHC.Base+#if __GLASGOW_HASKELL__ < 705+import GHC.Word+#endif import Math.NumberTheory.Logarithms.Internal ( wordLog2# ) #if __GLASGOW_HASKELL__ < 707@@ -25,14 +29,28 @@ -- 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.+-- 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.+--+-- /Warning:/ No check for the negativity of the exponent is performed,+-- a negative exponent is interpreted as a large positive exponent. integerPower :: Integer -> Int -> Integer-integerPower b (I# e#)- | isTrue# (e# ==# 0#) = 1- | isTrue# (e# ==# 1#) = b+integerPower b (I# e#) = power b (int2Word# e#)++-- | Same as 'integerPower', but for exponents of type 'Word'.+integerWordPower :: Integer -> Word -> Integer+integerWordPower b (W# w#) = power b w#++power :: Integer -> Word# -> Integer+power b w#+ | isTrue# (w# `eqWord#` 0##) = 1+ | isTrue# (w# `eqWord#` 1##) = b | otherwise = go (wordLog2# w# -# 1#) b (b*b) where- !w# = int2Word# e# go 0# l h = if isTrue# ((w# `and#` 1##) `eqWord#` 0##) then l*l else (l*h) go i# l h | w# `hasBit#` i# = go (i# -# 1#) (l*h) (h*h)
arithmoi.cabal view
@@ -1,5 +1,5 @@ name : arithmoi-version : 0.4.0.4+version : 0.4.1.0 cabal-version : >= 1.6 author : Daniel Fischer copyright : (c) 2011 Daniel Fischer@@ -47,6 +47,7 @@ Math.NumberTheory.Powers.Cubes Math.NumberTheory.Powers.Fourth Math.NumberTheory.Powers.General+ Math.NumberTheory.Powers.Integer Math.NumberTheory.Primes Math.NumberTheory.Primes.Sieve Math.NumberTheory.Primes.Factorisation@@ -57,7 +58,6 @@ Math.NumberTheory.Primes.Heap other-modules : Math.NumberTheory.Utils Math.NumberTheory.Logarithms.Internal- Math.NumberTheory.Powers.Integer Math.NumberTheory.Primes.Counting.Impl Math.NumberTheory.Primes.Counting.Approximate Math.NumberTheory.Primes.Factorisation.Montgomery