// Multi-threaded computing of Fibonacci numbers

public class ParFib implements Runnable {
  int n;
  int p;
  Thread t;
  long res;

  ParFib(int n, int p) {
    this.n= n;
    this.p= p;
    t= new Thread(this);
    t.start();
  }
  public void run() {
    System.out.println("Computing parallel fib("+n+")");
    res= parFib(n, p); // Changed from FutureFib
  }
  public long get() {
    try {
      t.join();
      return res;
    }
    catch (InterruptedException excp) {
      return 0;
    }
  }

  // Changed from FutureFib
  public static long parFib(int n, int p) {
    if (p<=0 || n<=2)
      return seqFib(n);
    else {
      ParFib par= new ParFib(n-2, p-1);
      long partialRes= parFib(n-1, p-1);
      return partialRes + par.get();
    }
  }

  public static long seqFib(int n) {
    if (n<=2)
      return 1;
    else
      return seqFib(n-1)+seqFib(n-2);
  }

  public static void main(String[] args) {
    if (args.length!=2)
      printUsage();
    int n= Integer.parseInt(args[0]);
    int p= Integer.parseInt(args[1]);

    { // Computing Fib sequentially
      long ini= System.currentTimeMillis();
      long f= seqFib(n);
      long delta= System.currentTimeMillis()-ini;
      System.out.println("seqFib("+n+")= "+f);
      System.out.println("elapsed time= "+delta+" millis");
    }

    { // Computing Fib sequentially
      System.out.println("Computing parallel fib("+n+")");
      long ini= System.currentTimeMillis();
      long f= parFib(n, p);
      long delta= System.currentTimeMillis()-ini;
      System.out.println("parFib("+n+")= "+f);
      System.out.println("elapsed time= "+delta+" millis");
    }
  }

  static void printUsage() {
    System.err.println("Usage: java ParFib <n> <p>");
    System.err.println("computes fib(n) in 2^p threads");
    System.exit(1);
  }
}