Questions on Scala performance tunning

Question

I am new to Scala, just wrote this program:

def isPrime(num: Int, primes: scala.collection.mutable.MutableList[Int]): Boolean = {
  primes.takeWhile( i =>  i * i <= num).forall( num % _ > 0)
}
//def isPrime(num: Int, primes: scala.collection.mutable.MutableList[Int]): Boolean = {
//  !primes.forall(num%_!=0)
//}


def primeListUnder(upper: Int) = { 
  val primes=scala.collection.mutable.MutableList(2,3); 
  var num=4
  while(num<upper) {
    if(isPrime(num,primes))
    { 
      primes+=num
    }
    num+=1
  }
  primes
}

This is trying to get all the prime numbers under some specified upper bound. But it runs really slow. Any suggestions?

Added: Actually my point is to know why this program runs so slow. It's not about how to calc the prime numbers.

Edit: Changed the isPrime method to first filter out some numbers (mathematically). Now is runs much faster, takes about 10 secs on my mac to count to 2000000;

check this http://stackoverflow.com/questions/9711785/find-prime-numbers-using-scala-help-me-to-improve/13202109#13202109 — Govind Singh, Oct 31 '14 at 09:45
What is your basis for saying it runs "really slow"? There are faster approaches, but yours doesn't seem an unreasonable approach — The Archetypal Paul, Oct 31 '14 at 11:08
Taking 10 seconds to find the primes to 2 million is slow, as such a trivial task using even a naive basic Sieve of Eratosthenes takes only a few 10's of milliseconds. Part of the reason is that division as implied by your modulo ("%") operation is one of the slowest primitive integer operations a modern CPU does at 10's of CPU clock cycles per, whereas adding typically takes a fraction of a CPU clock cycle and even multiplication only takes about one clock cycle. The Sieve of Eratosthenes performs all of its inner loop operations using simple basic operations for only a few clocks per loop. — GordonBGood, Apr 02 '15 at 06:48

rtruszk · Accepted Answer · 2014-10-31T10:22:58.643

0

To list all prime numbers less then specific number you should use Sieve of Eratosthenes. It is much faster then your algorithm.

Your algorithm is so slow becouse it checks every number with all prime numbers less than it until it finds its divisor. So every number will be checked with at least one prime number. But when checked number grows, the list of primes grows and number of possible checks grows.

There will be numbers rejected after many checks. For example number 26 will be rejected after checking 2,3,5,7,11,13.

Additionally every prime number will be accepted after checking all less prime numbers.

Comparing to your algorithm, Sieve of Eratosthenes algorithm will 'touch' every number once marking it as 'prime' or 'not prime'.

edited Oct 31 '14 at 10:22

answered Oct 31 '14 at 09:34

rtruszk

3,902
13
36
53

Thanks!But to my understanding, the "forall" method will exit once it doesn't meet the predict, right? Then the "primes.forall" will exit on the first number that "num%_==0" – Stanley Shi Oct 31 '14 at 09:54
@StanleyShi, while you are correct that your program will only check until it finds a divisor that divides evenly, every prime found will require that it be tested (trial division) by every already found prime up to its square root. So, on the average the amount of work done per found prime increases quite quickly the higher the range of numbers checked for primes. This is in contrast to other algorithms such as the Sieve of Eratosthenes as mentioned where the amount of work per found prime increases very slowly with increasing range. – GordonBGood Apr 02 '15 at 06:40

score 0 · Answer 2 · edited May 23 '17 at 12:06

As mentioned by @rtruszk, the following code reposted from my answer on the other linked question for a true Sieve of Eratosthenes (SoE) will run much faster than your code for larger ranges:

object SoE {
  def makeSoE_Primes(top: Int): Iterator[Int] = {
    val topndx = (top - 3) / 2
    val nonprms = new scala.collection.mutable.BitSet(topndx + 1)
    def cullp(i: Int) = {
      import scala.annotation.tailrec; val p = i + i + 3
      @tailrec def cull(c: Int): Unit = if (c <= topndx) { nonprms += c; cull(c + p) }
      cull((p * p - 3) >>> 1)
    }
    (0 to (Math.sqrt(top).toInt - 3) >>> 1).filterNot { nonprms }.foreach { cullp }
    Iterator.single(2) ++ (0 to topndx).filterNot { nonprms }.map { i: Int => i + i + 3 }
  }
}

The above code is mostly of a functional form (using tail recursion or higher order functions as well as immutability other than for the contents of the BitSet array used for fast sieving of composite numbers). It isn't quite as fast as using the Java.util.BitSet, but the resulting code is slightly more elegant.

Questions on Scala performance tunning

2 Answers2