PiEstimator (multithreaded monte carlo)

gistfile1.scala

import java.util.concurrent.Executors
import scala.util.Random
import java.util.concurrent.ExecutorService
import java.util.concurrent.Callable
import java.util.concurrent.FutureTask
import java.util.concurrent.ExecutorCompletionService
import scala.collection.mutable.MutableList

object PiEstimator extends App {

  def estimatePi(numSamples: Int): Double = {
    require(numSamples >= 0, "num samples was negative: " + numSamples)

    val rand = new Random()

    // streams are cached internally, iterator is the real lazy eval like seq in f#
    val insideCircle = (0 to numSamples).iterator
      .map { x => (rand.nextDouble(), rand.nextDouble()) }
      .count(t => (t._1 * t._1 + t._2 * t._2) <= 1)

    insideCircle.toDouble / numSamples * 4.0
  }

  def estimatePiConcurrent(numSamples: Long): Double = {
    val numThreads = Math.min(numSamples.intValue(), Runtime.getRuntime.availableProcessors())
    val shardSamples = (numSamples / numThreads).intValue()
    val threadPool = Executors.newFixedThreadPool(numThreads)
    val completionService = new ExecutorCompletionService[Double](threadPool)
    try {

      for (i <- (0 until numThreads)) {
        val callable = new Callable[Double]() {
          def call(): Double = {
            estimatePi(shardSamples)
          }
        }
        completionService.submit(callable)
      }

      val mutableList = new MutableList[Double]()
      for (i <- (0 until numThreads)) {
        mutableList += completionService.take().get()
      }

      mutableList.sum / numThreads
    } finally {
      threadPool.shutdown()
    }
  }

  val sampleSizes = (1 to 10).toList.map { x => math.pow(10, x).toLong }

  for (numSamples <- sampleSizes) {

    val start = System.currentTimeMillis()

    val pi = estimatePiConcurrent(numSamples)

    val duration = System.currentTimeMillis() - start
    println(f"Samples: $numSamples, pi: $pi, duration: $duration millis")
  }
}

some results:

Samples: 10, pi: 6.0, duration: 10 millis
Samples: 100, pi: 3.25, duration: 1 millis
Samples: 1000, pi: 3.1559999999999997, duration: 3 millis
Samples: 10000, pi: 3.126, duration: 6 millis
Samples: 100000, pi: 3.13772, duration: 21 millis
Samples: 1000000, pi: 3.141028, duration: 32 millis
Samples: 10000000, pi: 3.1416863999999998, duration: 126 millis
Samples: 100000000, pi: 3.14173224, duration: 1177 millis
Samples: 1000000000, pi: 3.1416308920000002, duration: 15607 millis
Samples: 10000000000, pi: 3.1415774024000003, duration: 88608 millis