6

I wrote isPrime function. It checks if a given number is prime or not. The last "prime" list is given separately.

prime :: [Integer]
prime = 2 : filter isPrime [3..]
isPrime :: Integer -> Bool
isPrime n | n < 2 = False
isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime

I thought it was always better to consolidate two functions into one if possible..so I consolidated isPrime and prime into one function isPrime2. But the isPrime2's performance is very bad. 

isPrime2 :: Integer -> Bool
isPrime2 n | n < 2 = False
isPrime2 n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : filter isPrime2 [3..]

isPrime 40000000000000000001

=> 0.5 second

isPrime2 40000000000000000001

=> 19.8 seconds

My machine is Ubuntu 17.10 x86-64. I am using ghc 8.2.1. Does anyone know why?

Will Ness
  • 70,110
  • 9
  • 98
  • 181
Jihyun
  • 883
  • 5
  • 17
  • My guess would be that since `prime` is a constant, it gets memoised, whereas `isPrime2` is a function, so it doesn't. That's only a guess, however... – MathematicalOrchid Oct 30 '17 at 10:23
  • Thanks! Your explanation gave me insights. – Jihyun Oct 30 '17 at 11:10
  • @eii0000 are you testing it compiled or interpreted? how does it compare if you simplify your `isPrime2 n` as ``all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : [3,5..]``? – Will Ness Oct 31 '17 at 08:33
  • all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ 2 : [3,5..] is very fast... in my machine it took 0.025 second. I also tried all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ [2,3,5]++[6*x+y|x<-[1..],y<-[1,5]], which is slightly faster than 2:[3,5..] – Jihyun Oct 31 '17 at 13:56
  • I compiled it. thanks! – Jihyun Oct 31 '17 at 17:49
  • ok, thanks. now, what happens if you test the same number 10 times (or 100), with your 1st function vs with the function in the answer? (can you tell, without running it?) @eii0000 (when you respond, use @ sign so I get pinged :) ) – Will Ness Nov 01 '17 at 19:29

1 Answers1

6

The first snippet will keep only one list of primes in memory.

The second snippet will compute its own prime until n^2 every single time isPrime2 is called. Previously discovered primes are discarded and recomputed from scratch at every call. Since isPrime2 is recursive this leads to a blow-up.

An intermediate approach can be this one:

isPrime2 :: Integer -> Bool
isPrime2 m = isPrime m
   where
   prime :: [Integer]
   prime = 2 : filter isPrime [3..]
   isPrime :: Integer -> Bool
   isPrime n | n < 2 = False
   isPrime n = all (\p -> n `mod` p /= 0) . takeWhile ((<=n) . (^2)) $ prime

This will recompute prime at every call of isPrime2, but will not lead to a blow-up since each call of the inner isPrime will share the same list of primes.

chi
  • 111,837
  • 3
  • 133
  • 218
  • great... your isPrime2 is 0.5 second too.. Thanks! – Jihyun Oct 30 '17 at 11:09
  • Won't GHC usually float `prime` and `isPrime` out to the top level during optimisation? – Benjamin Hodgson Oct 30 '17 at 11:57
  • @BenjaminHodgson No, GHC is conservative here since it is not always an optimization. I believe this transformation is called (or related to) the "full laziness" transformation, where `\x -> let y = ... in ....` becomes `let y= ... in \x -> ...` provided that `y` does not depend on `x`. The semantics is preserved, but it is hard to predict which one has the best performance (IIRC). – chi Oct 30 '17 at 12:05