nth-prime (empty) → 1.0

raw patch · 5 files changed

+205/−0 lines, 5 filesdep +basedep +opentheory-primedep +opentheory-primitivesetup-changed

Dependencies added: base, opentheory-prime, opentheory-primitive

Files

LICENSE +17/−0
Setup.hs +6/−0
nth-prime.cabal +36/−0
src/Main.hs +95/−0
src/Test.hs +51/−0

+ LICENSE view

@@ -0,0 +1,17 @@+Permission is hereby granted, free of charge, to any person obtaining a copy+of this software and associated documentation files (the "Software"), to deal+in the Software without restriction, including without limitation the rights+to use, copy, modify, merge, publish, distribute, sublicense, and/or sell+copies of the Software, and to permit persons to whom the Software is+furnished to do so, subject to the following conditions:++The above copyright notice and this permission notice shall be included in+all copies or substantial portions of the Software.++THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR+IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,+FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE+AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER+LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,+OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN+THE SOFTWARE.

+ Setup.hs view

@@ -0,0 +1,6 @@+module Main(main)++import Distribution.Simple++main :: IO ()+main = defaultMain

+ nth-prime.cabal view

@@ -0,0 +1,36 @@+name: nth-prime+version: 1.0+category: Number Theory+synopsis: Computing the nth prime+license: MIT+license-file: LICENSE+cabal-version: >= 1.8.0.2+build-type: Simple+author: Joe Leslie-Hurd <joe@gilith.com>+maintainer: Joe Leslie-Hurd <joe@gilith.com>+description:+  This package implements a simple utility to compute the nth prime.++executable nth-prime+  build-depends:+    base >= 4.0 && < 5.0,+    opentheory-primitive >= 1.0 && < 2.0,+    opentheory-prime >= 1.0 && < 2.0++  hs-source-dirs: src++  ghc-options: -Wall++  main-is: Main.hs++executable nth-prime-test+  build-depends:+    base >= 4.0 && < 5.0,+    opentheory-primitive >= 1.0 && < 2.0,+    opentheory-prime >= 1.0 && < 2.0++  hs-source-dirs: src++  ghc-options: -Wall++  main-is: Test.hs

+ src/Main.hs view

@@ -0,0 +1,95 @@+{- |+module: Main+description: Computing the nth prime+license: MIT++maintainer: Joe Leslie-Hurd <joe@gilith.com>+stability: provisional+portability: portable+-}+module Main+  ( main )+where++import qualified Data.List as List+import qualified System.Environment as Environment+import System.Console.GetOpt++import qualified OpenTheory.Primitive.Natural as Natural+import qualified OpenTheory.Natural.Prime as VerifiedSieve+import qualified NaiveSieve+import qualified OptimizedSieve+import qualified GenuineSieve++type Sieve = [Natural.Natural]++verifiedSieve :: (String,Sieve)+verifiedSieve = ("verified",VerifiedSieve.primes)++sieves :: [(String,Sieve)]+sieves =+  [verifiedSieve,+   ("naive",NaiveSieve.primes),+   ("optimized",OptimizedSieve.primes),+   ("genuine",GenuineSieve.primes)]++stringToSieve :: String -> (String,Sieve)+stringToSieve s =+  case filter (List.isPrefixOf s . fst) sieves of+    [] -> usage $ "bad sieve name: " ++ s+    [x] -> x+    _ : _ : _ -> usage $ "ambiguous sieve name: " ++ s++data Options = Options+    {optSieve :: String}+  deriving Show++defaultOptions :: Options+defaultOptions =+  Options+    {optSieve = fst verifiedSieve}++options :: [OptDescr (Options -> Options)]+options =+    [Option ['s'] ["sieve"]+       (ReqArg (\s opts -> opts {optSieve = s}) "SIEVE")+       "select sieve algorithm"]++processOptions :: [String] -> Either [String] (Options,[String])+processOptions args =+    case getOpt Permute options args of+      (opts,work,[]) -> Right(foldl (flip id) defaultOptions opts, work)+      (_,_,errs) -> Left errs++processArguments :: [String] -> (Options,Int)+processArguments args =+    case processOptions args of+      Left errs -> usage (concat errs)+      Right (opts,work) ->+        let ns = case work of+                   [] -> usage "not enough arguments"+                   [x] -> x+                   _ : _ : _ -> usage "too many arguments" in+        let n = case reads ns of+                  [(x,"")] -> x+                  _ -> usage "bad N argument" in+        (opts,n)++usage :: String -> a+usage err =+    error $ err ++ "\n" ++ usageInfo header options ++ footer+  where+    header = "Usage: nth-prime [OPTION...] N"++    footer =+      "where N is an integer and SIEVE is one of\n" +++      "  {" ++ List.intercalate "," (map fst sieves) ++ "}"++main :: IO ()+main =+    do args <- Environment.getArgs+       let (opts,n) = processArguments args+       let (name,primes) = stringToSieve (optSieve opts)+       let p = primes !! n+       putStrLn $ "  prime[" ++ show n ++ "] = " ++ show p ++ "  (using " ++ name ++ " sieve)"+       return ()

+ src/Test.hs view

@@ -0,0 +1,51 @@+{- |+module: Main+description: Testing the computation of the nth prime+license: MIT++maintainer: Joe Leslie-Hurd <joe@gilith.com>+stability: provisional+portability: portable+-}+module Main+  ( main )+where++import qualified OpenTheory.Primitive.Natural as Natural+import qualified OpenTheory.Natural.Prime as VerifiedSieve+import qualified NaiveSieve+import qualified OptimizedSieve+import qualified GenuineSieve++sieves :: [[Natural.Natural]]+sieves =+  [VerifiedSieve.primes,+   NaiveSieve.primes,+   OptimizedSieve.primes,+   GenuineSieve.primes]++checkInitialPrimes :: Int -> IO ()+checkInitialPrimes k =+    case map (take k) sieves of+      [] -> error "no sieves defined"+      l : ls ->+        if all ((==) l) ls+          then putStrLn $ "  checked initial " ++ show k +++                          " primes are " ++ show l+          else error $ "wrong initial " ++ show k ++ " primes"++checkNthPrime :: Int -> IO ()+checkNthPrime k =+    case map (\s -> s !! k) sieves of+      [] -> error "no sieves defined"+      p : ps ->+        if all ((==) p) ps+          then putStrLn $ "  checked prime[" ++ show k ++ "] is " ++ show p+          else error $ "wrong prime[" ++ show k ++ "]"++main :: IO ()+main =+    do checkInitialPrimes 10+       checkNthPrime 100+       checkNthPrime 1000+       return ()