Tuesday, January 17, 2017

Big fibs

import java.util.*;
import java.math.*;

//=========================
// Custom Timeout Exception
//=========================

class TimeoutException extends Exception {

  public TimeoutException() {
    super();
  }

  public TimeoutException(String message) {
    super(message);
  }

}

//=====================================
// Utility that Adds, Counts, and Times
//=====================================

class Util {

  public static Integer timeLimitMs = 500;
  public static Long count = 0L;
  private static Long t0 = 0L;

  public static BigInteger add(BigInteger a, BigInteger b)
  throws TimeoutException {
    count++;
    if (count % 10000 == 0) {
      checkTime();
    }
    return a.add(b);
  }

  public static void start() {
    count = 0L;
    t0 = System.nanoTime();
  }

  public static Double stop() {
    return elapsedMs();
  }

  private static Double elapsedMs() {
    return (System.nanoTime() - t0)/1000000d;
  }

  private static void checkTime()
  throws TimeoutException {
    if (elapsedMs() > timeLimitMs) {
      throw new TimeoutException(timeLimitMs + " ms limit exceeded.");
    }
  }

}

//==========================
// Generic Abstract Function
//==========================

abstract class Func<In, Out> {

  public abstract Out call(Func<In, Out> self, In x)
  throws TimeoutException;

  public Out call(In x)
  throws TimeoutException {
    return this.call(this, x);
  }

}

//==========================
// Generic Memoized Function
//==========================

class MemoizedFunc<In, Out> extends Func<In, Out> {

  private Map<In, Out> cache = new HashMap<In, Out>();
  private Func<In, Out> otherFunc;

  public MemoizedFunc(Func<In, Out> func) {
    this.otherFunc = func;
  }

  public Out call(Func<In, Out> self, In x)
  throws TimeoutException {
    if (!cache.containsKey(x)) {
      cache.put(x, otherFunc.call(self, x)); 
    }
    return cache.get(x);
  }

}

//============================
// Abstract Fibonacci Function
//============================

abstract class Fib extends Func<Integer, BigInteger> {

}

//============================
// Memoized Fibonacci Function
//============================

abstract class MemoizedFib extends MemoizedFunc<Integer, BigInteger> {

  MemoizedFib(Fib func) {
    super(func);
  }

}

//===========================
// Amnesic Fibonacci Function
//===========================

class AmnesicFib extends Fib {

  public BigInteger call(Func<Integer, BigInteger> self, Integer i)
  throws TimeoutException {

    BigInteger NEG1 = BigInteger.valueOf(-1);

    if (i == 0) { // return first Fibonacci number
      return BigInteger.valueOf(0);
    }
    else if (i == 1) { // return second Fibonacci number
      return BigInteger.valueOf(1);
    }
    else if (i > 0) { // return ith Fibonacci number
      return Util.add(
        self.call(self, i-2),
        self.call(self, i-1));
    }
    else { // return ith "negafibonacci" number
      return Util.add(
        self.call(self, i+2),
        self.call(self, i+1).multiply(NEG1));
    }
  }

}

//===========================
// Eidetic Fibonacci Function
//===========================

class EideticFib extends MemoizedFib {

  EideticFib() {
    super(new AmnesicFib());
  }

}

//===========================
// Grinder Fibonacci Function
//===========================

class GrinderFib extends Fib {

  public BigInteger call(Func<Integer, BigInteger> self, Integer i)
  throws TimeoutException {

    //----------------------------------------
    //  1 multiplier => Fibonacci number
    // -1 multiplier => "negafibonacci" number
    //  0 is the "bipolafibonacci" number
    //----------------------------------------

    Integer multiplier = i < 0 ? -1 : 1;
    BigInteger MULTIPLIER = BigInteger.valueOf(multiplier);

    Integer magnitude = multiplier * i;

    BigInteger f2 = BigInteger.valueOf(-1);
    BigInteger f1 = BigInteger.valueOf(1);
    BigInteger f0 = BigInteger.valueOf(0);

    for (Integer j = 0; j < magnitude; j++) {
      f2 = f1;
      f1 = f0;
      f0 = Util.add(f2, (f1.multiply(MULTIPLIER)));        
    }

    return f0;
  }

}

//===========================
// Unitary Fibonacci Function
//===========================

class UnitaryFib extends MemoizedFib {

  UnitaryFib() {
    super(new GrinderFib());
  }

}

//===========================
// Lacunar Fibonacci Function
//===========================

class LacunarFib extends Fib {

  public BigInteger call(Func<Integer, BigInteger> self, Integer i)
  throws TimeoutException {

    // HACK
    final MathContext mcL = new MathContext(128, RoundingMode.HALF_UP);
    final MathContext mcM = new MathContext(32, RoundingMode.HALF_UP);
    final MathContext mcS = new MathContext(2, RoundingMode.HALF_UP);
    
    final BigDecimal ONE = BigDecimal.valueOf(1);
    final BigDecimal NEG1 = BigDecimal.valueOf(-1);
    final BigDecimal TWO = BigDecimal.valueOf(2);
    final BigDecimal SQRT5 = BigDecimal.valueOf(Math.sqrt(5));
    final BigDecimal PHI = (ONE.add(SQRT5)).divide(TWO, mcL);
    final BigDecimal PHIHAT = NEG1.divide(PHI, mcL);
    final BigDecimal PHIPOWI = PHI.pow(i, mcL);
    final BigDecimal PHIHATPOWI = PHIHAT.pow(i, mcL);
    final BigDecimal DIFF = PHIPOWI.subtract(PHIHATPOWI);
    
    // HACK
    final BigDecimal FIB = DIFF.abs().doubleValue() < 10 ?
      DIFF.divide(SQRT5, mcS) : DIFF.divide(SQRT5, mcM);
    
    final BigInteger BIGFIB = FIB.toBigInteger();
    return BIGFIB;
  }

}

//=======
// Report
//=======

public class BigFibs {

  private final static int STACK_OVERFLOW = 1;
  private final static int DATATYPE_OVERFLOW = 2;
  private final static int TIMEOUT = 3;

  private final static String[] PRTF = { "%5s", "%55s", "%12d", "%12.3f" };
  private final static String[] PRTH = { "%5s", "%55s", "%12s", "%12s" };

  private static void printData
  (Func<Integer, BigInteger> F, String[] seqNums, int i0) {

    String  nm = F.getClass().getName();
    Integer n;
    BigInteger Fn = null;   // nth Fibonacci number
    Double  dt = 0d;     // delta (change in) time in ms
    Double  sumTm = 0d;  // sum of times
    Long    sumCt = 0L;  // sum of counts (number of operations)
    Integer err;         // error code

    //---------------------------------------
    // print one data row per sequence number
    //---------------------------------------

    for (Integer i = i0; i < seqNums.length; i++) {
      err = 0;
      n = Integer.parseInt(seqNums[i]);
      Util.start();
      try {
        Fn = F.call(n);
      }
      catch(StackOverflowError soe) {
        Fn = null;
        err = STACK_OVERFLOW;
      }
      catch(TimeoutException toe) {
        Fn = null;
        err = TIMEOUT;
      }
      catch(Exception e) {
        Fn = null;
        err = DATATYPE_OVERFLOW;
      }
      dt = Util.stop();
      sumTm += dt;
      sumCt += Util.count;
      printDataRow(n, Fn, Util.count, dt, nm, err);
    }

    //----------------------------------------------------
    // if more than one sequence number, print summary row
    //----------------------------------------------------

    if (seqNums.length - i0 > 1) {
      printDataRow(null, null, sumCt, sumTm, "TOTALS", 0);
      System.out.println();
    }
  }

  private static void printHeaderRow() {
    System.out.println("BigFibs: " + (new Date()).toString());
    System.out.println();
    System.out.printf(PRTH[0], "i");
    System.out.printf(PRTH[1], "Fib(i)");
    System.out.printf(PRTH[2], "operations");
    System.out.printf(PRTH[3], "time (ms)");
    System.out.println();
    System.out.printf(PRTH[0], "-----");
    System.out.printf(PRTH[1], "------------------------------------------------------");
    System.out.printf(PRTH[2], "-----------");
    System.out.printf(PRTH[3], "-----------");
    System.out.println();
  }

  private static void printDataRow
  (Integer n, BigInteger Fn, Long ct, Double dt, String name, Integer err) {
    if (n != null) {
      System.out.printf(PRTF[0], n.toString());
    }
    else {
      System.out.printf(PRTF[0], "");
    }
    if (Fn == null && err == 0) {
      System.out.printf(PRTF[1], "");
    }
    else {
      switch(err) {
      case 0:
        System.out.printf(PRTF[1], Fn);
        break;
      case STACK_OVERFLOW:
        System.out.printf(PRTF[1], "STACK_OVERFLOW");
        break;
      case DATATYPE_OVERFLOW:
        System.out.printf(PRTF[1], "DATATYPE_OVERFLOW");
        break;
      case TIMEOUT:
        System.out.printf(PRTF[1], "TIMEOUT");
        break;
      default:
        System.out.printf(PRTF[1], "UNEXPECTED_ERROR");
        break;
      }
    }
    System.out.printf(PRTF[2], ct);
    System.out.printf(PRTF[3], dt);
    System.out.print(' ');
    System.out.print(name);
    System.out.println();
  }

  public static void unoReport
  (Func<Integer, BigInteger> fib, String[] args, int i0) {
    printHeaderRow();
    printData(fib, args, i0);
    if (args.length == 1) {
      System.out.println();
    }
  }

  public static void comboReport(String[] args, int i0) {
    printHeaderRow();
    printData(new AmnesicFib(), args, i0);
    printData(new EideticFib(), args, i0);
    printData(new GrinderFib(), args, i0);
    printData(new UnitaryFib(), args, i0);
    printData(new LacunarFib(), args, i0);
    if (args.length == 1) {
      System.out.println();
    }
  }

  public static void main(String[] args) {
    if (args.length == 0) {
      return;
    }
    switch(args[0].toLowerCase()) {
    case "amnesic":
      unoReport(new AmnesicFib(), args, 1);
      break;
    case "eidetic":
      unoReport(new EideticFib(), args, 1);
      break;
    case "grinder":
      unoReport(new GrinderFib(), args, 1);
      break;
    case "unitary":
      unoReport(new UnitaryFib(), args, 1);
      break;
    case "lacunar":
      unoReport(new LacunarFib(), args, 1);
      break;
    default:
      comboReport(args, 0);
      break;
    }
  }

}