packages feed

primecount (empty) → 0.1.0.0

raw patch · 10 files changed

+519/−0 lines, 10 filesdep +basedep +primecountdep +silentlysetup-changed

Dependencies added: base, primecount, silently, tasty, tasty-bench, tasty-hunit

Files

+ ChangeLog.md view
@@ -0,0 +1,15 @@+# Changelog++## 0.1.0.0++### Added+* `Math.NumberTheory.Prime.Count.FFI`, with FFI bindings to all functions from the+  `primecount` library.+* `Math.NumberTheory.Prime.Count`, with high-level wrappers (`primePi`,+  `nthPrime`, and `primePhi`) around the functions in+  `Math.NumberTheory.Prime.Count.FFI`.+* Test coverage of `primePi`, `nthPrime`, and `primePhi` with `tasty-hunit`.+* Benchmarks of `primePi`, `nthPrime`, and `primePhi` with `tasty-bench`.+* Full Haddock documentation coverage.+* Support for GHC 9.2.1, 9.0.1, 8.10.7, 8.8.4, 8.6.5, and 8.4.4, and+  libprimecount v7.x, verified by GitHub Actions.
+ LICENSE view
@@ -0,0 +1,26 @@+Copyright 2021 Preetham Gujjula++Redistribution and use in source and binary forms, with or without modification,+are permitted provided that the following conditions are met:++1. Redistributions of source code must retain the above copyright notice, this+   list of conditions and the following disclaimer.++2. Redistributions in binary form must reproduce the above copyright notice,+   this list of conditions and the following disclaimer in the documentation+   and/or other materials provided with the distribution.++3. Neither the name of the copyright holder nor the names of its contributors+   may be used to endorse or promote products derived from this software without+   specific prior written permission.++THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND+ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED+WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE+DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR+ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES+(INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;+LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON+ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT+(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS+SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ README.md view
@@ -0,0 +1,58 @@+# `primecount` for Haskell+[![Haskell-CI](https://github.com/pgujjula/primecount-haskell/actions/workflows/haskell-ci.yml/badge.svg)](https://github.com/pgujjula/primecount-haskell/actions/workflows/haskell-ci.yml)++This library provides Haskell bindings to Kim Walisch's+[primecount](https://github.com/kimwalisch/primecount) library.++## Build instructions+First follow the+[directions](https://github.com/kimwalisch/primecount#installation)+for installing `libprimecount`. As stated in the directions, if you are+installing through your system's package manager, make sure to get the+development version of the primecount package, which might have a name like+`primecount-devel`. The current version of the Haskell bindings supports any+version of `libprimecount >= 7.0`.++Then you can build the Haskell bindings with Stack or Cabal, and read the+documentation.+```+# Stack+stack build+stack test+stack haddock primecount --open++# Cabal+cabal update+cabal build+cabal test+cabal haddock  # and then open the documentation manually+```++### Building `libprimecount` from source+If you build and install the original `primecount` library from source, instead+of through a package manager, then you need to make sure that your Haskell build+system knows where to find it. For example, on Linux `libprimecount` might be+installed to `/usr/local/lib64`.++Then if using Stack, add the following lines to your `stack.yaml` or your global+`~/.stack/config.yaml`:+```+extra-lib-dirs:+- /usr/local/lib64+extra-include-dirs:+- /usr/local/include+```+If using Cabal, add the following lines to your `~/.cabal/config`:+```+extra-lib-dirs:+  /usr/local/lib64+extra-include-dirs:+  /usr/local/include+```+or pass+`--extra-lib-dirs=/usr/local/lib64 --extra-include-dirs=/usr/local/include`+as an argument to Cabal.++## Bugs+Report any bugs on the Github issue tracker, or by emailing+[primecount-haskell@mail.preetham.io](mailto:primecount-haskell@mail.preetham.io).
+ Setup.hs view
@@ -0,0 +1,3 @@+import Distribution.Simple++main = defaultMain
+ bench/Main.hs view
@@ -0,0 +1,44 @@+-- |+-- Copyright   : 2022 Preetham Gujjula+-- License     : BSD-3-Clause+-- Maintainer  : primecount-haskell@mail.preetham.io+-- Stability   : experimental+module Main (main) where++import Math.NumberTheory.Prime.Count+  ( nthPrime,+    primePhi,+    primePi,+    setNumPrimecountThreads,+  )+import Test.Tasty.Bench++primePiBenchmark :: Benchmark+primePiBenchmark =+  bgroup "primePi" $ do+    i <- [(1 :: Int) .. 12]+    pure $ bench ("10^" ++ show i) $ nf primePi (10 ^ i :: Int)++nthPrimeBenchmark :: Benchmark+nthPrimeBenchmark =+  bgroup "nthPrime" $ do+    i <- [(1 :: Int) .. 12]+    pure $ bench ("10^" ++ show i) $ nf nthPrime (10 ^ i :: Int)++primePhiBenchmark :: Benchmark+primePhiBenchmark =+  bgroup "primePhi" $ do+    i <- [(2 :: Int), 4 .. 12]+    j <- [(2 :: Int), 4 .. i]+    pure $+      bench ("n = 10^" ++ show i ++ ", a = 10^" ++ show j) $+        nf (primePhi (10 ^ i :: Int)) (10 ^ j :: Int)++main :: IO ()+main = do+  setNumPrimecountThreads 1+  defaultMain+    [ primePiBenchmark,+      nthPrimeBenchmark,+      primePhiBenchmark+    ]
+ primecount.cabal view
@@ -0,0 +1,75 @@+cabal-version: 2.2++-- This file has been generated from package.yaml by hpack version 0.34.4.+--+-- see: https://github.com/sol/hpack++name:           primecount+version:        0.1.0.0+synopsis:       Bindings to the primecount library+description:    Please see the README on Github at <https://github.com/pgujjula/primecount-haskell#readme>+category:       Math, Number Theory+homepage:       https://github.com/pgujjula/primecount-haskell#readme+bug-reports:    https://github.com/pgujjula/primecount-haskell/issues+author:         Preetham Gujjula+maintainer:     primecount-haskell@mail.preetham.io+copyright:      2021 Preetham Gujjula+license:        BSD-3-Clause+license-file:   LICENSE+build-type:     Simple+tested-with:+    GHC ==8.4.4 || ==8.6.5 || ==8.8.4 || ==8.10.7 || ==9.0.1 || ==9.2.1+extra-source-files:+    README.md+    ChangeLog.md++source-repository head+  type: git+  location: https://github.com/pgujjula/primecount-haskell++library+  exposed-modules:+      Math.NumberTheory.Prime.Count+      Math.NumberTheory.Prime.Count.FFI+  hs-source-dirs:+      src+  default-extensions:+      ScopedTypeVariables+  ghc-options: -Wall -Wcompat -Wmissing-export-lists -Wincomplete-record-updates -Wpartial-fields -Wmissing-home-modules -Werror=missing-home-modules -Widentities -Wredundant-constraints -Wmissing-export-lists+  extra-libraries:+      primecount+  build-depends:+      base >=4.7 && <5.0+  default-language: Haskell2010++test-suite primecount-tests+  type: exitcode-stdio-1.0+  main-is: Main.hs+  other-modules:+      Test.Math.NumberTheory.Prime.Count+  hs-source-dirs:+      test+  default-extensions:+      ScopedTypeVariables+  ghc-options: -Wall -Wcompat -Wmissing-export-lists -Wincomplete-record-updates -Wpartial-fields -Wmissing-home-modules -Werror=missing-home-modules -Widentities -Wredundant-constraints -Wmissing-export-lists+  build-depends:+      base >=4.7 && <5.0+    , primecount+    , silently+    , tasty+    , tasty-hunit+  default-language: Haskell2010++benchmark primecount-bench+  type: exitcode-stdio-1.0+  main-is: Main.hs+  hs-source-dirs:+      bench+  default-extensions:+      ScopedTypeVariables+  ghc-options: -Wall -Wcompat -Wmissing-export-lists -Wincomplete-record-updates -Wpartial-fields -Wmissing-home-modules -Werror=missing-home-modules -Widentities -Wredundant-constraints -Wmissing-export-lists+  build-depends:+      base >=4.7 && <5.0+    , primecount+    , tasty-bench+  default-language: Haskell2010
+ src/Math/NumberTheory/Prime/Count.hs view
@@ -0,0 +1,126 @@+-- |+-- Module      : Math.NumberTheory.Prime.Count+-- Copyright   : 2021 Preetham Gujjula+-- License     : BSD-Clause+-- Maintainer  : primecount-haskell@mail.preetham.io+-- Stability   : experimental+--+-- This module provides a high-level, polymorphic interface to the primecount+-- library. For a lower-level interface, see+-- "Math.NumberTheory.Prime.Count.FFI#".+module Math.NumberTheory.Prime.Count+  ( primePi,+    primePiMaxBound,+    nthPrime,+    nthPrimeMaxBound,+    primePhi,+    getNumPrimecountThreads,+    setNumPrimecountThreads,+    primecountVersion,+  )+where++import Data.Int (Int64)+import Foreign.C.String (CString, peekCString, withCString)+import Foreign.C.Types (CSize)+import Foreign.Marshal.Array (allocaArray)+import Math.NumberTheory.Prime.Count.FFI+import System.IO.Unsafe (unsafePerformIO)+import Text.Read (readMaybe)++-- | The number of primes less than or equal to @n@. Throws an error if @n@+--   is larger than 'primePiMaxBound'. Also might throw an error if there's not+--   enough memory available to compute the result, which can happen even if @n@+--   is smaller than @primePiMaxBound@.+primePi :: Integral a => a -> a+primePi n+  | n < 0 = 0+  | n' <= bound = fromIntegral (primecount_pi (fromInteger n'))+  | n' <= primePiMaxBound = fromInteger (primePiStr n')+  | otherwise = error "primePi: input larger than primePiMaxBound"+  where+    bound :: Integer+    bound = toInteger (maxBound :: Int64)++    n' :: Integer+    n' = toInteger n++-- | The largest input supported by 'primePi'.+--+-- * 64-bit CPUs: @10^31@+-- * 32-bit CPUs: @2^63 - 1@+primePiMaxBound :: Integer+primePiMaxBound = read $ unsafePerformIO $ peekCString primecount_get_max_x+{-# NOINLINE primePiMaxBound #-}++primePiStr :: Integer -> Integer+primePiStr n = unsafePerformIO $ do+  withCString (show n) $ \nString -> do+    let len = 32 :: CSize+    allocaArray (fromIntegral len) $ \(res :: CString) -> do+      ret <- primecount_pi_str nString res len+      if ret < 0 || ret > fromIntegral len+        then error "primePi: call to primecount_pi_str failed"+        else do+          answer <- peekCString res+          maybe+            (error "primePi: couldn't parse result of primecount_pi_str")+            pure+            (readMaybe answer)+{-# NOINLINE primePiStr #-}++-- | The nth prime, starting at @nthPrime 1 == 2@.+--+--    * Throws an error if the input is less than 1.+--    * Throws an error if the input is larger than 'nthPrimeMaxBound`.+nthPrime :: Integral a => a -> a+nthPrime n+  | n < 1 = error "nthPrime: n must be >= 1"+  | n' > bound = error "nthPrime: answer cannot be packed into a 64-bit int"+  | otherwise = fromIntegral (primecount_nth_prime (fromInteger n'))+  where+    bound :: Integer+    bound = 216289611853439384++    n' :: Integer+    n' = toInteger n++-- | The largest input supported by 'nthPrime', equal to+--   @primePi ('maxBound' :: 'Int64') == 216289611853439384@.+nthPrimeMaxBound :: Integer+nthPrimeMaxBound = 216289611853439384++-- | @primePhi n a@ counts the number of positive integers @<= n@ that are not+--    divisible by any of the first @a@ primes. Throws an error if @n@ is larger+--    than @'maxBound' :: 'Int64'@.+primePhi :: Integral a => a -> a -> a+primePhi n a+  | n <= 0 = 0+  | a <= 0 = n+  | n' > bound = error "primePhi: input cannot be packed into a 64-bit int"+  | otherwise = fromIntegral (primecount_phi (fromInteger n') (fromInteger a'))+  where+    bound :: Integer+    bound = toInteger (maxBound :: Int64)++    n' :: Integer+    n' = toInteger n++    a' :: Integer+    a' = min bound (toInteger a)++-- | Get the currently set number of threads used by @libprimecount@.+getNumPrimecountThreads :: IO Int+getNumPrimecountThreads = primecount_get_num_threads++-- | Set the number of threads used by @libprimecount@. If the input is not+--   positive, the thread count is set to 1. If the input is greater than the+--   number of CPUs available, the thread count is set to the number of CPUs+--   available.+setNumPrimecountThreads :: Int -> IO ()+setNumPrimecountThreads = primecount_set_num_threads++-- | Get the @libprimecount@ version number, in the form @"i.j"@+primecountVersion :: String+primecountVersion = unsafePerformIO (peekCString primecount_version)+{-# NOINLINE primecountVersion #-}
+ src/Math/NumberTheory/Prime/Count/FFI.hs view
@@ -0,0 +1,67 @@+-- |+-- Module      : Math.NumberTheory.Prime.Count.FFI+-- Copyright   : 2021 Preetham Gujjula+-- License     : BSD-3-Clause+-- Maintainer  : primecount-haskell@mail.preetham.io+-- Stability   : experimental+--+-- This module provides direct access to the C API of the primecount library.+-- It's recommended that you use the higher-level interface in+-- "Math.NumberTheory.Prime.Count#".+--+-- Documentation adapted from the [C API reference]+-- (https://github.com/kimwalisch/primecount/blob/master/doc/libprimecount.md#c-api-reference)+-- and [@primecount.h@]+-- (https://github.com/kimwalisch/primecount/blob/master/include/primecount.h).+module Math.NumberTheory.Prime.Count.FFI+  ( primecount_pi,+    primecount_pi_str,+    primecount_nth_prime,+    primecount_phi,+    primecount_get_max_x,+    primecount_get_num_threads,+    primecount_set_num_threads,+    primecount_version,+  )+where++import Data.Int (Int64)+import Foreign.C.String (CString)+import Foreign.C.Types (CSize (..))++-- | Count the number of primes @<= x@.+foreign import ccall unsafe "primecount_pi"+  primecount_pi :: Int64 -> Int64++-- | Count the number of primes <= x (supports 128-bit).+foreign import ccall unsafe "primecount_pi_str"+  primecount_pi_str :: CString -> CString -> CSize -> IO Int++-- | Find the @n@th prime e.g.: @primecount_nth_prime 25 == 97@.+foreign import ccall unsafe "primecount_nth_prime"+  primecount_nth_prime :: Int64 -> Int64++-- | @primecount_phi x a@ counts the numbers @<= x@ that are not divisible by+--   any of the first @a@ primes.+foreign import ccall unsafe "primecount_phi"+  primecount_phi :: Int64 -> Int64 -> Int64++-- | @primecount_get_max_x@ is the largest number supported by+--   'primecount_pi_str'.+--+-- * 64-bit CPUs: @10^31@+-- * 32-bit CPUs: @2^63 - 1@+foreign import ccall unsafe "primecount_get_max_x"+  primecount_get_max_x :: CString++-- | Get the currently set number of threads used by @libprimecount@.+foreign import ccall unsafe "primecount_get_num_threads"+  primecount_get_num_threads :: IO Int++-- | Set the number of threads used by @libprimecount@.+foreign import ccall unsafe "primecount_set_num_threads"+  primecount_set_num_threads :: Int -> IO ()++-- | Get the @libprimecount@ version number, in the form @"i.j"@.+foreign import ccall unsafe "primecount_version"+  primecount_version :: CString
+ test/Main.hs view
@@ -0,0 +1,15 @@+-- |+-- Copyright   : 2021 Preetham Gujjula+-- License     : BSD-3-Clause+-- Maintainer  : primecount-haskell@mail.preetham.io+-- Stability   : experimental+module Main (main) where++import qualified Test.Math.NumberTheory.Prime.Count (tests)+import Test.Tasty (TestTree, defaultMain, testGroup)++main :: IO ()+main = defaultMain tests++tests :: TestTree+tests = testGroup "" [Test.Math.NumberTheory.Prime.Count.tests]
+ test/Test/Math/NumberTheory/Prime/Count.hs view
@@ -0,0 +1,90 @@+-- |+-- Copyright   : 2021 Preetham Gujjula+-- License     : BSD-3-Clause+-- Maintainer  : primecount-haskell@mail.preetham.io+-- Stability   : experimental+module Test.Math.NumberTheory.Prime.Count (tests) where++import Control.Exception (SomeException, catch, evaluate)+import Data.Int (Int64)+import Math.NumberTheory.Prime.Count+  ( nthPrime,+    nthPrimeMaxBound,+    primePhi,+    primePi,+    primePiMaxBound,+  )+import System.IO (stderr)+import System.IO.Silently (hSilence)+import Test.Tasty (TestTree, testGroup)+import Test.Tasty.HUnit (testCase, (@?=))++tests :: TestTree+tests =+  testGroup+    "Math.NumberTheory.Prime.Count"+    [primePiTest, nthPrimeTest, primePhiTest]++throwsException :: a -> IO Bool+throwsException thunk =+  (hSilence [stderr] (evaluate thunk) >> pure False)+    `catch` (\(_ :: SomeException) -> pure True)++primePiTest :: TestTree+primePiTest =+  testGroup+    "primePi tests"+    [ testCase "works for negative inputs" $+        primePi (-1 :: Int) @?= 0,+      testCase "works for small inputs" $ do+        primePi (5 :: Int) @?= 3+        primePi (10 :: Int) @?= 4+        primePi (100 :: Int) @?= 25,+      testCase "throws error when input is too large" $+        let tooBig :: Integer+            tooBig = primePiMaxBound + 1+         in throwsException (primePi tooBig) >>= (@?= True)+    ]++nthPrimeTest :: TestTree+nthPrimeTest =+  testGroup+    "nthPrime"+    [ testCase "throws error for non-positive inputs" $ do+        throwsException (nthPrime (0 :: Int)) >>= (@?= True)+        throwsException (nthPrime ((-1) :: Int)) >>= (@?= True),+      testCase "works for small inputs" $ do+        nthPrime (1 :: Int) @?= 2+        nthPrime (5 :: Int) @?= 11+        nthPrime (25 :: Int) @?= 97,+      testCase "throws error when input is too large" $+        let tooBig :: Integer+            tooBig = nthPrimeMaxBound + 1+         in throwsException (nthPrime tooBig) >>= (@?= True)+    ]++primePhiTest :: TestTree+primePhiTest =+  testGroup+    "primePhi"+    [ testCase "is 0 if n is not positive" $ do+        primePhi (0 :: Int) undefined @?= 0+        primePhi ((-1) :: Int) undefined @?= 0,+      testCase "is n if a is not positive" $ do+        primePhi (10 :: Int) 0 @?= 10+        primePhi (10 :: Int) (-1) @?= 10,+      testCase "works for small inputs" $ do+        primePhi (1 :: Int) 2 @?= 1+        primePhi (10 :: Int) 2 @?= 3+        primePhi (10 :: Int) 3 @?= 2+        primePhi (10 :: Int) 4 @?= 1+        primePhi (10 :: Int) 5 @?= 1,+      testCase "throws error if n is too large" $ do+        throwsException (primePhi tooBig 2) >>= (@?= True)+        throwsException (primePhi tooBig 3) >>= (@?= True),+      testCase "works even if a is too large" $+        primePhi 10 tooBig @?= 1+    ]+  where+    tooBig :: Integer+    tooBig = toInteger (maxBound :: Int64) + 1