Paralelización del cálculo de factorial.

factPar.scala

import util.Random.shuffle

/* Compresión de una lista de enteros
 * 
 * Agrupa los números enteros en multiplicandos BigInt
 * listos para la multiplicación final del factorial.
 *
 * Se presupone que los enteros usan 32 bits y los longs usan 64 bits.
 * Se multiplican enteros hasta justo sobrepasar 2^32, que es el
 * límite de los enteros sin signo. Este límite es seguro, aunque
 * se puede elevar imponiendo restricciones en el tamaño de los enteros.
 */
def compressRange(lst: Range): Seq[BigInt] = {

  type Int32 = Int
  type Int64 = Long
  val maxInt = (1L << 32)

  def loop(lst: List[Int32], res: List[BigInt], acc: Int64): List[BigInt] = lst match {
    case Nil => BigInt(acc) :: res
    case head :: tail =>
      val x = acc * head
      if (x <= maxInt) // No overflow
        loop(tail, res, x)
      else
        loop(tail, BigInt(acc) :: res, head)
  }

  loop(lst.toList, Nil, 1)
}

// Factorial
def fact(n: BigInt) = (BigInt(2) to n).product

// Factorial paralelizado
def factPar(n: BigInt) = (BigInt(2) to n).par.product

// Factorial paralelizado con aleatorización previa
def factParShuffle(n: BigInt) = shuffle((BigInt(2) to n).toSeq).par.product

/*
 * Factorial paralelizado con compresión de enteros
 *
 * Con la compresión de enteros se intenta atrasar el uso de BigInts
 * hasta el final. El resto de soluciones utilizan BigInt desde el
 * primer momento, lo que ralentiza las operaciones con enteros pequeños.
 */
def factParCompress(n: Int) = compressRange(2 to n).par.product

time { fact(50000) } // 6357.928105ms
time { factPar(50000) } // 1268.408428ms
time { factParShuffle(50000) } // 1213.519174ms
time { factParCompress(50000) } // 892.560851ms