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;
}
}
}
