Why is my algorithm for Project Euler Problem 12 so slow?

Question

Hi,

I have created solution for PE P12 in Scala but is very very slow. Can somebody can tell me why? How to optimize this? calculateDevisors() - naive approach and calculateNumberOfDivisors() - divisor function has the same speed :/

import annotation.tailrec

def isPrime(number: Int): Boolean = {
  if (number < 2 || (number != 2 && number % 2 == 0) || (number != 3 && number % 3 == 0))
    false
  else {
    val sqrtOfNumber = math.sqrt(number) toInt

    @tailrec def isPrimeInternal(divisor: Int, increment: Int): Boolean = {
      if (divisor > sqrtOfNumber)
        true
      else if (number % divisor == 0)
        false
      else
        isPrimeInternal(divisor + increment, 6 - increment)
    }

    isPrimeInternal(5, 2)
  }
}

def generatePrimeNumbers(count: Int): List[Int] = {
  @tailrec def generatePrimeNumbersInternal(number: Int = 3, index: Int = 0,
                                            primeNumbers: List[Int] = List(2)): List[Int] = {
    if (index == count)
      primeNumbers
    else if (isPrime(number))
      generatePrimeNumbersInternal(number + 2, index + 1, primeNumbers :+ number)
    else
      generatePrimeNumbersInternal(number + 2, index, primeNumbers)
  }

  generatePrimeNumbersInternal();
}

val primes = Stream.cons(2, Stream.from(3, 2) filter {isPrime(_)})

def calculateDivisors(number: Int) = {
  for {
    divisor &lt;- 1 to number
    if (number % divisor == 0)
  } yield divisor
}

@inline def decomposeToPrimeNumbers(number: Int) = {
  val sqrtOfNumber = math.sqrt(number).toInt

  @tailrec def decomposeToPrimeNumbersInternal(number: Int, primeNumberIndex: Int = 0,
                                               factors: List[Int] = List.empty[Int]): List[Int] = {
    val primeNumber = primes(primeNumberIndex)

    if (primeNumberIndex > sqrtOfNumber)
      factors
    else if (number % primeNumber == 0)
      decomposeToPrimeNumbersInternal(number / primeNumber, primeNumberIndex, factors :+ primeNumber)
    else
      decomposeToPrimeNumbersInternal(number, primeNumberIndex + 1, factors)
  }

  decomposeToPrimeNumbersInternal(number) groupBy {n => n} map {case (n: Int, l: List[Int]) => (n, l size)}
}

@inline def calculateNumberOfDivisors(number: Int) = {
  decomposeToPrimeNumbers(number) map {case (primeNumber, exponent) => exponent + 1} product
}

@tailrec def calculate(number: Int = 12300): Int = {
  val triangleNumber = ((number * number) + number) / 2
  val startTime = System.currentTimeMillis()
  val numberOfDivisors = calculateNumberOfDivisors(triangleNumber)
  val elapsedTime = System.currentTimeMillis() - startTime

  printf("%d: V: %d D: %d T: %dms\n", number, triangleNumber, numberOfDivisors, elapsedTime)

  if (numberOfDivisors > 500)
    triangleNumber
  else
    calculate(number + 1)
}

println(calculate())

Answer 1

calculateDivisors can be greatly improved by only checking for divisors up to the square root of the number. Each time you find a divisor below the sqrt, you also find one above.

def calculateDivisors(n: Int) = {
  var res = 1
  val intSqrt = Math.sqrt(n).toInt
  for (i <- 2 until intSqrt) {
      if (n % i == 0) {
          res += 2
      }
  }
  if (n == intSqrt * intSqrt) {
      res += 1
  }
  res
}

Answer 2

Slow compared to....? How do you know it's an issue with Scala, and not with your algorithm?

An admittedly quick read of the code suggests you might be recalculating primes and other values over and over. isPrimeInternal jumps out as a possible case where this might be a problem.

Answer 3

Your code is not compilable, some parts are missing, so I'm guessing here. Some thing that frequently hurts performance is boxing/unboxing taking place in collections. Another thing that I noted is that you cunstruct your primes as a Stream - which is a good thing - but don't take advantage of this in your isPrime function, which uses a primitive 2,3-wheel (1 and 5 mod 6) instead. I might be wrong, but try to replace it by

def isPrime(number: Int): Boolean = {
  val sq = math.sqrt(number + 0.5).toInt
  ! primes.takeWhile(_ <= sq).exists(p => number % p == 0)
}

Answer 4

You could first check what is slow. Your prime calculation, for instance, is very, very slow. For each number n, you try to divide n by each each number from 5 to sqrt(n), skipping multiples of 2 and 3. Not only you do not skip numbers you already know are not primes, but even if you fix this, the complexity of this algorithm is much worse than the traditional Sieve of Eratosthenes. See one Scala implementation for the Sieve here.

That is not to say that the rest of your code isn't suboptimal as well, but I'll leave that for others.

EDIT

Indeed, indexed access to Stream is terrible. Here's a rewrite that works with Stream, instead of converting everything to Array. Also, note the remark before the first if for a possible bug in your code.

  @tailrec def decomposeToPrimeNumbersInternal(number: Int, primes: Stream[Int],
                                               factors: List[Int] = List.empty[Int]): List[Int] = {
    val primeNumber = primes.head

    // Comparing primeNumberIndex with sqrtOfNumber didn't make any sense
    if (primeNumber > sqrtOfNumber) 
      factors
    else if (number % primeNumber == 0)
      decomposeToPrimeNumbersInternal(number / primeNumber, primes, factors :+ primeNumber)
    else
      decomposeToPrimeNumbersInternal(number, primes.tail, factors)
  }