Dense? Dense, you say?

5 comments on “Dense? Dense, you say?”

1. Phil Trelford says:

   2009-12-01 at 03:47

   I like the revised Haskell code! That truly is short!

   Phil

   P.S. Its good that you are distrustful of my measurements, however if you look at the code attached to the post then you will see each function was run 1000 times to get the value and then divided by 1000 which should be reasonably satisfactory.

2. Ian says:

   2009-12-01 at 12:25

   Why do you test every number from 2 up?

   I don’t know haskell, so I’m not sure if there’s a better way of doing this, but
   isPrime x = null (filter ((==0) . mod x) ([2]++[3,5..floor . sqrt $ fromIntegral x]))

   Tests only odd numbers. Change the top line to
   ltps = take 4260 $ ps 1 [2]

   As I say, I don’t know haskell, so the only way I was able to run this and time it was to put:
   main = print (take 2000 ltps)

   and run “time ./primes > /dev/null”.

   Getting 2000 takes 1.461s by testing every number and 0.794 by testing only odd numbers.

3. Joe says:

   2009-12-01 at 23:16

   Minor point: you need “tail” to skip 0.

   On my (apparently aging) computer, the 2800th takes 19s. @Ian’s version, unsurprisingly, took half as long. I spent 2 lines on a full sieve, and it takes under 3s:

   http://hpaste.org/fastcgi/hpaste.fcgi/view?id=13484

4. coeus says:

   2009-12-06 at 16:23

   are you all crazy?! aAaaAhhh… never ever forget to write the types!! it hurts to see the mistakes of one’s own past. ;p
   “Integral a => a” defaults to infinite-bit Integer, not 64-bit Int.
   this additional one line might speed everything up:

   ltps :: [Int]

   @Ian:

   buggyIsPrime :: Int -> Bool
   buggyIsPrime x = all ((/=0) . mod x) [(2::Int),3..round . sqrt $ (fromIntegral x::Float)]

   this has to be compared to the c++ version, which tests every even number, too.
   not only that: the function has to state that every number below 2 is prime. (this is only a bug, if you reuse code, …which you probably want to do. copypasting it will cause the bug to proliferate. one to one reimplemented imperative code is seldom less bugprone than its imperative original.)

   @all:
   rounding floor might not be enough, i’d use ceiling, because Int is 64-bit and Double is less exakt. the c++ version uses 32-bit Float, anyway.

   does anyone know, how c++ casts float to int?
   does it ceiling, floor, elementary-school-round, or does it round towards that nearest number which has less 1s in its binary representation?
   haskell rounds elementary-school-round, unless it is sth like int+0.5, then it rounds to the nearest even number.

   there might still be another bug in the c++ version: the loop runs with the condition “i<sqrt" and not with "i<=sqrt". so, sth like this might happen iff (int)1.9f==1 :

   sqrtf 4 == 1.999999f
   int sqrt = 1 + 1.999999f == 2
   for (int i=2; i yep, 4 must be prime.
   it will probably happen only with big numbers, where 32-bit floats are not exact anymore.

   probably you already thought of this, and so you reimplemented this bug with floor on doubles. in that case, never mind.

   regards
   – marc

5. Dan says:

   2010-01-11 at 12:01

   Joining late the fry, but nonetheless…

   @coeus
   The c++ code does not test all numbers, but only the numbers that end with 2, 3, 5, and 7, since they have to be left-truncatable primes.

   Testing only odd numbers seems appropriate to me, and even then it will test more numbers than the C++ version

   – Dan