Skip to content

Instantly share code, notes, and snippets.

@cristobal
Created April 1, 2014 12:29
Show Gist options
  • Save cristobal/9912984 to your computer and use it in GitHub Desktop.
Save cristobal/9912984 to your computer and use it in GitHub Desktop.
Fibonacci Module, resolving Fib in Java.
import java.lang.reflect.InvocationTargetException;
import java.util.WeakHashMap;
import java.util.concurrent.TimeUnit;
// @see http://java67.blogspot.sg/2012/07/java-program-fibonacci-series-with.html
// @see https://github.com/raganwald/homoiconic/blob/master/2008-12-12/fibonacci.md
public class FibonacciModule {
// Standard
public static Integer fibonacci(final Integer n) {
if (n < 2) {
return n;
}
return fibonacci(n - 1) + fibonacci(n - 2);
}
// Iterative
public static Integer ifibonacci(final Integer n) {
if (n < 2) {
return n;
}
Integer fib = 2,
fib1 = fib - 1,
fib2 = fib - 2;
for(int i = n; i > 0; i--) {
fib = fib1 + fib2;
fib1 = fib2;
fib2 = fib;
}
return fib;
}
// Memoized
public static WeakHashMap<Integer, Integer> m = new WeakHashMap<>();
public static Integer mfibonacci(final Integer n) {
if (n < 2) {
return n;
}
if (m.containsKey(n)) {
return m.get(n);
}
m.put(n, mfibonacci(n -1) + mfibonacci(n - 2));
return m.get(n);
}
// Power
public static Integer fibonnaci_power(Integer n) {
if (n < 2) {
return n;
}
Integer[] m = new Integer[]{1, 1, 0};
return power(m, n-1)[0];
}
// Naive Power
public static Integer fibonnaci_naive_power(Integer[] m, final Integer n)
{
Object[] args = new Object[n - 1];
for (Integer i = 0; i < n - 1; i++) {
args[i] = m;
}
Integer[] result = new Integer[]{0, 0, 0};
try {
result = (Integer[])
Fibonnaci.class
.getDeclaredMethod("times", Object[].class)
.invoke(Fibonnaci.class, new Object[] {args});
}
catch (NoSuchMethodException ex) {
}
catch (IllegalAccessException e) {
}
catch (InvocationTargetException e) {
}
return result[0];
}
public final static Integer[] power (Integer[] m, Integer n) {
if (n == 1) {
return m.clone();
}
Integer[] halves = power(m, n / 2);
if ((n % 2) == 0) {
return times(halves, halves);
}
else {
return times(halves, halves, m);
}
}
public final static Integer[] times(Object ...ems) {
Integer[] p = null, // product
m = null; // matrix
Integer a, b, c,
d, e, f;
p = ((Integer[]) ems[0]).clone(); // shallow copy
for (int i = 1, l = ems.length; i < l; i++) {
m = ((Integer[]) ems[i]).clone();
a = p[0]; b = p[1]; c = p[2];
d = m[0]; e = m[1]; f = m[2];
// a, b, c = p[0], p[1], p[2];
// d, e, f = m[0], m[1], m[2];
// [a*d + b*e, a*e + b*f, b*e + c*f]
p[0] = a * d + b * e;
p[1] = a * e + b * f;
p[2] = b * e + c * f;
}
return p;
}
public static void main(String[] args) {
Integer[] m = new Integer[]{1, 1, 0};
Integer n = 43;
long nanoTime = System.nanoTime();
System.out.println("Calculated fib(" + n + ") => " + fibonacci(n) + " in total: " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - nanoTime) + "ms");
nanoTime = System.nanoTime();
System.out.println("Calculated ifib(" + n + ") => " + ifibonacci(n) + " in total: " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - nanoTime) + "ms");
nanoTime = System.nanoTime();
System.out.println("Calculated mfib(" + n + ") => " + mfibonacci(n) + " in total: " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - nanoTime) + "ms");
nanoTime = System.nanoTime();
System.out.println("Calculated fib_power(" + n + ") => " + fibonnaci_power(n) + " in total: " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - nanoTime) + "ms");
nanoTime = System.nanoTime();
System.out.println("Calculated fib_naive_power(" + n + ") => " + fibonnaci_naive_power(m, n) + " in total: " + TimeUnit.NANOSECONDS.toMillis(System.nanoTime() - nanoTime) + "ms");
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment