-
-
Save Shimuuar/2050052 to your computer and use it in GitHub Desktop.
testing prime speed
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// same algorithm and data structure as prime_array | |
// gcc -o prime -std=c99 -O3 -g prime.c | |
// ./prime 500000 3.03s user 0.00s system 99% cpu 3.033 total | |
#include <stdio.h> | |
#include <stdlib.h> | |
int main(int argc, char** argv) | |
{ | |
int iMax = atoi(argv[1]); | |
int* arr = malloc(sizeof(int) * (iMax + 1)); | |
int iN = 0; | |
int n2 = 4; | |
int iMT = 0; | |
int x = 2; | |
while (iN <= iMax) { | |
if (x >= n2) { | |
++iMT; | |
n2 = arr[iMT] * arr[iMT]; | |
} | |
int prime = 1; | |
for (int i = 0; i < iMT; ++i) { | |
if (x % arr[i] == 0) { | |
prime = 0; | |
break; | |
} | |
} | |
if (prime) { | |
arr[iN++] = x; | |
} | |
++x; | |
} | |
printf("%d\n", arr[iMax]); | |
free(arr); | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
{-# LANGUAGE NoMonomorphismRestriction, BangPatterns #-} | |
module Main where | |
-- compile: ghc --make -main-is Prime.main Prime.hs -O2 | |
-- $time ./Prime i 500000 | |
-- ./Prime i 500000 4.35s user 0.00s system 99% cpu 4.453 total | |
-- ./Prime s 500000 7.69s user 0.03s system 99% cpu 7.726 total (!!!) | |
-- lookup OPT in comments about various optimization points | |
import System.Environment(getArgs) | |
import qualified Data.Vector.Generic.Mutable as M | |
import qualified Data.Vector.Unboxed as U | |
import Control.Monad.Primitive (PrimMonad,PrimState) | |
divides :: Integral a => a -> a -> Bool | |
divides n x = (x `mod` n) == 0 | |
{-# INLINE divides #-} | |
prime_dumb :: Integral a => [a] | |
prime_dumb = f [2..] | |
where | |
f (x : xs) = x : f (filter (not . divides x) xs) | |
-- this is better algorithm compared to previous. It tests divisions only up to sqrt(n) | |
-- not optimized at all, but surprisingly fast -- less than 2 times slower than the next one and less than 3 times slower than C version | |
prime_sq :: Integral a => (a -> Bool) -> [a] | |
prime_sq err = res | |
where | |
res = f 4 res (takeWhile (not . err) [2..] ++ error "overflow") | |
f n2 ~(p0 : pt@(p1 : _)) xs@(x : _) | x >= n2 = f (p1 * p1) pt (filter (not . divides p0) xs) | |
f n2 ps (x : xt) = x : f n2 ps xt | |
errNo :: b -> Bool | |
errNo = const False | |
errBound :: (Bounded a, Eq a) => a -> Bool | |
errBound = \x -> x == maxBound | |
-- the same algorithm as previous, but use unboxed array | |
-- OPT: turning on specialization makes it SLOWER (?!) same also for iter | |
-- {- SPECIALIZE prime_array :: Int -> GHC.ST.ST s (Data.Array.ST.STUArray s Int Int) -} | |
-- {- SPECIALIZE prime_array :: Int -> IO (Data.Array.IO.IOUArray Int Int) -} | |
-- prime_array :: (Integral e, Data.Array.IO.MArray a e m) => Int -> m (a Int e) | |
prime_array :: (Integral a, PrimMonad m, M.MVector v a) | |
=> Int -> m (v (PrimState m) a) | |
{-# INLINE prime_array #-} | |
prime_array iMax = | |
do arr <- M.new (iMax + 1) | |
fill arr 0 4 0 2 -- OPT: here was list [2 ..] with processor, switching to explicit iteration gave ~0.5s | |
return arr | |
where | |
fill _ iN _ _ _ | iN > iMax = return () | |
fill arr iN n2 iMT x | x >= n2 = do | |
nN0 <- M.read arr iMT | |
nN1 <- M.read arr (iMT + 1) | |
fill arr iN (nN1 * nN1) (iMT + 1) (x + 1) | |
fill arr iN n2 iMT x = do | |
isPrime <- check arr x iMT | |
-- OPT: this fix-based one is 0.5s slower | |
{- fix (\next i -> case i of | |
_ | i == iMT -> return True | |
_ -> do | |
nT <- unsafeRead arr i | |
if nT `divides` x then return False else next (i + 1)) 0 -} | |
if isPrime | |
then do | |
M.write arr iN x | |
fill arr (iN + 1) n2 iMT (x + 1) | |
else fill arr iN n2 iMT (x + 1) | |
-- -} | |
check :: (Integral a, PrimMonad m, M.MVector v a) | |
=> v (PrimState m) a -> a -> Int -> m Bool | |
{-# INLINE check #-} | |
check arr x iMT = iter 0 | |
where | |
iter i | i == iMT = return True | |
iter i = do | |
nT <- M.read arr i | |
if nT `divides` x | |
then return False | |
else iter (i + 1) | |
main :: IO () | |
main = do | |
a <- getArgs | |
let k = read (a !! 1) | |
case (a !! 0) of | |
"d" -> print $ prime_dumb !! k | |
"s" -> print (prime_sq errBound !! k :: Int) | |
"a" -> do let v = U.create (prime_array k) | |
print (v U.! k :: Int) | |
"i" -> do v <- U.unsafeFreeze =<< prime_array k | |
print (v U.! k :: Int) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment