Optimisation algorithms with huge collections with huge numbers (in a functional way)

Question

I started learning scala recently and found an interesting task. The challenge is to find the biggest palindrome number (e.g. 144858441) which is a product of two 5-digits primes. Moreover, I needed to return both multipliers too. I solved it this way:

case class PrimesHolder(a:Int, b:Int, palindrome:BigInt) 

object palindromeFinder {
  def find(from:Int, to:Int) = {
    // getting all primes between FROM and TO 
    val primes = calculatePrimesStreamBetween(from, to)

    // getting all possible compositions of primes and filtering non-palindromes, 
    //   result is a list of tuples (BigInt, Int), first val is palindrome, second is one of prime multipliers (we'll get the second one by division)
    val palindromes = multiplyAll(primes).filter(palindromeFilter)

    // looking for maximum  
    val res = if (palindromes.nonEmpty) palindromes.maxBy(_._1) else (BigInt(0), 0)

    // return statement
    if (res._2 != 0) PrimesHolder(res._2, (res._1 / res._2).toInt, res._1) else PrimesHolder(0, 0, 0)
  }

  // it's The Sieve Eratosthen implementation 
  private def calculatePrimesStreamBetween(from:Int, to: Int): List[Int] = {
    val odds = Stream.from(3, 2).takeWhile(_ <= Math.sqrt(to).toInt)
    val composites = odds.flatMap(i => Stream.from(i * i, 2 * i).takeWhile(_ <= to))
    Stream.from(3, 2).takeWhile(i => i >= from && i <= to).diff(composites).toList
  }

  // multiplies values in lists "each by each", yields list of tuples (BigInt, Int)
  private def multiplyAll(a:List[Int]) = a.flatMap(item => a.filter(j => j >= item).map(i => (BigInt(i) * item, i)))

  // palindrome filter function for passing to .filter((BigInt, Int) => Boolean)
  private def palindromeFilter(num:(BigInt, Int)):Boolean = {
    if (num._1.toString.head != num._1.toString.last) false else num._1.toString == num._1.toString.reverse
  }
}  

/////////////////////////////////////////////////////////
object Main {
  def main(args: Array[String]): Unit = {
    val res = palindromeFinder.find(10000, 99999)
    println(s"${res.palindrome} = ${res.a} * ${res.b}")
  }
}

But this code requires too much memory and takes ~30 sec on my computer. To get the result I need to put -J-Xms1024m -J-Xmx3000m parameters before execution. How can I optimize my code in a functional way? Thank you!

Answer 1

I don´t know scala, but here are some tips:

• The answer must have an odd amount of digits. This is because if the answer has an even amount of digits, it would be divisible by 11. As you are never generating numbers with 11 as a factor, answer must have odd amount of digits (9).
• A sieve is not necessary, the range is small and numbers are small, standard way should be enough to find all 8363 primes in that range in under 1 second.
• We will need to do up to 8363 * 8363 multiplications, which is not that bad but the most expensive part is checking if the multiplication is a palindrome. We need to try to reduce these checks as most as possible.
• For each prime number, if you multiply it by the other primes in a descending order, the first palindrome you find will be the highest possible for that prime number, so its not necessary to iterate the rest
• If the multiplication is lower than highest palindrome found, checking if it is palindrome is not necessary

Not sure how many of these tips you can apply to your code in a functional way, but here is a javascript non functional approach that makes full use of these ideas and takes less than 1 second:

var start = new Date().getTime();

function isPrime(n) {
    if (n % 2 == 0) return false;
    for (var i = 3; i <= Math.sqrt(n); i += 2) {
        if (n % i == 0) return false;
    }
    return true;
}

var primes = []

for (var i = 99999; i >= 10000; i--) {
    if (isPrime(i)) primes.push(i)
}

var max = 0;

const isPalindrome = (string) => string == string.split('').reverse().join('');

var max = 0;

for (var i = 0; i < primes.length; i++) {
    var prime1 = primes[i];
    for (var j = i; j < primes.length; j++) {
        var prime2 = primes[j];
        var mul = prime1 * prime2
        if (mul > 999999999) continue;
        if (max > mul) break;
        if (isPalindrome(mul.toString())) {
            max = mul;
        }
    }
}


console.log(max, "took " + (new Date().getTime() - start) + " ms");

Additional tip: It could be further optimized by calculating with binary search the first prime2 that will cause prime1 to have 9 digits instead of 10, that way skipping a lot of iterations over primes2

Answer 2

juvian gave a great answer outlining some algorithmic strategies. Here's some of those ideas but implemented in scala, purely functionally:

def primes(min: Int, max: Int): List[Int] = {
  val primeCandidates = 2 #:: Stream.from(3, 2)
  def isPrime(n: Int): Boolean = {
    primeCandidates.takeWhile(x => x * x <= n).forall(x => n % x != 0)
  }
  primeCandidates.dropWhile(_ < min).takeWhile(_ < max).filter(isPrime).toList
}

@scala.annotation.tailrec
final def findLargestPalindrome(primesDesc: List[Int], bestSoFar: Option[(Int, Int, Long)]): Option[(Int, Int, Long)] = primesDesc match {
  case p1 :: rest => {
    val needToCheck = bestSoFar match {
      case Some((_, _, product)) => rest.takeWhile(_.toLong * p1 > product)
      case None => rest
    }
    val result = needToCheck.find { p2 =>
      val product = p1.toLong * p2
      val str = product.toString
      str == str.reverse
    }
    val newBest = result.map(p2 => (p1, p2, p1.toLong * p2)).orElse(bestSoFar)
    findLargestPalindrome(rest, newBest)
  }
  case Nil => bestSoFar
}

val primesDesc = primes(10000, 100000).reverse
findLargestPalindrome(primesDesc, None)

I think within findLargestPalindrome I'm probably redoing the multiplication too many times, so you could look into tightening that up, but in practice it's pretty fast anyway.

It finds 33211 * 30109 = 999949999, which due to the point about it needing to be an odd number of digits, seems extremely likely to be correct.