Tuesday, September 7, 2010

Perfect Number implementation using Scala Actor, Spring Integration, Java Executors, Kilim based Actor

A Simple non-threaded (and non-optimized) java implementation for figuring out if a number is a perfect number is the following:

public class SimplePerfectNumberUtil implements PerfectNumberUtil{

 @Override
 public boolean isPerfect(int aNumber) {
  return sumOfFactors(aNumber)==2*aNumber;
    }
 
 private int sumOfFactors(int aNumber){
  int sum = 0;
  for (int i=1;i<=aNumber;i++){
   if (aNumber%i==0){
    sum+=i;
   }
  }
  
  return sum;
 }

}



Programming Scala book provides a sample scala actor implementation for this by breaking up the task of determining whether a large number is a perfect number by breaking up the large number into a range of smaller numbers - eg. a number like 3000 can be split up into say 0-1000, 1001-2000, 2001-3000, with a task responsible for summing up the factors in each of these ranges and summing up the result.

A slightly modified implementation based on the Programming Scala book is the following:

class PerfectUtilScala {

  def isPerfect(candidate: Int) = {
    val RANGE = 10000000
    val numberOfPartitions = (candidate.toDouble / RANGE).ceil.toInt
    val caller = self
    
    
    val sumoffactorsActor = actor{
     loop {
      react {
    case msg:FactorsRangeForCandidate =>
     caller ! sumOfFactorsInRange(msg.lower, msg.upper, msg.candidate)
   }  
  } 
    }


    for (i <- 0 until numberOfPartitions) {
      val lower = i * RANGE + 1;
      val upper = candidate min (i + 1) * RANGE
      
      sumoffactorsActor ! new FactorsRangeForCandidate(lower, upper, candidate)
    }

    val sum = (0 /: (0 until numberOfPartitions)) { (partialSum, i) =>
      receive {
        case sumInRange: Int => partialSum + sumInRange
      }
    }

    2 * candidate == sum
  }

  private def sumOfFactorsInRange(lower: Int, upper: Int, number: Int) = {
    (0 /: (lower to upper)) { (sum, i) => if (number % i == 0) sum + i else sum }
  }

}


class FactorsRangeForCandidate(val lower:Int, val upper:Int, val candidate:Int)

A Java Executors based implementation is the following:
public class ThreadPoolPerfectNumberUtil implements PerfectNumberUtil{ 
 private ExecutorService threadpool = Executors.newFixedThreadPool(3);
 @SuppressWarnings("unchecked")
    public boolean isPerfect(int aNumber) {
     int RANGE = Constants.RANGE;
     int numberOfPartitions = new Double(Math.ceil(aNumber * 1.0 / RANGE)).intValue();
     Future[] sumOfFactors = new Future[numberOfPartitions];
     
     for (int i=0;i{

 private final int lower;
 private final int upper;
 private final int anumber;
 
 
 public SumOfFactorsTask(int lower, int upper, int anumber){
  this.lower = lower;
  this.upper = upper;
  this.anumber = anumber;
 }
 
 
 @Override
    public Integer call() {
  int sum=0;
  for (int i=lower;i<=upper;i++){
   if (anumber%i==0){
    sum+=i;
   }
  }  
  
  return sum;
    }

}
And a Kilim based actor implementation:

public class ActorsPerfectNumberUtil extends Task implements PerfectNumberUtil {

 private Mailbox mailbox;
 private Mailbox resultmailbox;
 private SumOfFactorsActor sumOfFactors;

 public ActorsPerfectNumberUtil() {
  mailbox = new Mailbox();
  resultmailbox = new Mailbox();
  sumOfFactors = new SumOfFactorsActor(mailbox, resultmailbox);
  sumOfFactors.start();

 }

 public boolean isPerfect(int aNumber) {
  int RANGE = Constants.RANGE;
  int numberOfPartitions = new Double(Math.ceil(aNumber * 1.0 / RANGE)).intValue();

  for (int i = 0; i < numberOfPartitions; i++) {
   int lower = i * RANGE + 1;
   int upper = (i + 1) * RANGE;
   if (aNumber < upper)
    upper = aNumber;
   mailbox.putnb(new FactorsRange(lower, upper, aNumber));
  }

  int sum = 0;
  for (int i = 0; i < numberOfPartitions; i++) {
    sum += resultmailbox.getb();
  }

  if (sum == 2*aNumber)
   return true;

  return false;
 }
}
The codebase along with the Spring Integration based implementation is available at this Git location:
git://github.com/bijukunjummen/Perfect-Number.git

No comments:

Post a Comment