serious stuff
www.cubbi.com
personal
programming
fibonacci numbers
forth examples
postscript examples
muf examples
joy examples
j examples
scheme examples
hope examples
ocaml examples
haskell examples
prolog examples
c++ examples
java examples
assembly language examples
fortran examples
c examples
sh examples
awk examples
perl examples
tcl examples
asmix
hacker test
resume
science
martial arts
fun stuff
www.cubbi.org
|
Java
Date: 1995
Type: Object-oriented language
Usage: Mostly web applications, though targeted and marketed for much more
ALGORITHM 1A: NAIVE BINARY RECURSION |
class f1a {
private static long fib(long n) {
return n<2 ? n : fib(n-2)+fib(n-1);
}
private static long f(long n) {
if(n<0)
return (n%2==0) ? -fib(-n) : fib(-n);
else
return fib(n);
}
private static void fib_print(int n) {
System.out.println(n + "th Fibonacci number is " + f(n));
}
public static void main(String argv[]) {
try {
if(argv.length == 1) {
fib_print(Integer.parseInt(argv[0]));
System.exit(0);
}
} catch (NumberFormatException e) { }
System.out.println("Usage: java f1a ");
System.exit(1);
}
}
|
ALGORITHM 1B: CACHED BINARY RECURSION / MEMOIZATION |
import java.math.BigInteger;
import java.util.HashMap;
class f1b {
private static BigInteger fib(int n, HashMap<Integer, BigInteger> m) {
if(m.containsKey(n)) return m.get(n);
BigInteger result = n<=0 ? BigInteger.ZERO
: n==1 ? BigInteger.ONE
: fib(n-2, m).add(fib(n-1, m));
m.put(n, result);
return result;
}
private static BigInteger fib(int n) {
HashMap<Integer, BigInteger> memo = new HashMap<Integer, BigInteger>(n);
return fib(n, memo);
}
private static BigInteger f(int n) {
if(n<0)
return (n%2==0) ? fib(-n).negate() : fib(-n);
else
return fib(n);
}
private static void fib_print(int n) {
System.out.println(n + "th Fibonacci number is " + f(n));
}
public static void main(String argv[]) {
try {
if(argv.length == 1) {
fib_print(Integer.parseInt(argv[0]));
System.exit(0);
}
} catch (NumberFormatException e) { }
System.out.println("Usage: java f1b <n>");
System.exit(1);
}
}
|
ALGORITHM 2A: CACHED LINEAR RECURSION / RANDOM-ACCESS CONTAINER |
import java.math.BigInteger;
import java.util.LinkedList;
class f2a {
private static BigInteger fib(LinkedList<BigInteger> l, int n) {
l.addFirst(l.peek().add(l.get(1)));
return n<1 ? l.peek() : fib(l, n-1);
}
private static BigInteger fib(int n) {
LinkedList<BigInteger> list = new LinkedList<BigInteger>();
list.addFirst(BigInteger.ZERO);
list.addFirst(BigInteger.ONE);
return n<2 ? list.get(1-n) : fib(list, n-2);
}
private static BigInteger f(int n) {
if(n<0)
return (n%2==0) ? fib(-n).negate() : fib(-n);
else
return fib(n);
}
private static void fib_print(int n) {
System.out.println(n + "th Fibonacci number is " + f(n));
}
public static void main(String argv[]) {
try {
if(argv.length == 1) {
fib_print(Integer.parseInt(argv[0]));
System.exit(0);
}
} catch (NumberFormatException e) { }
System.out.println("Usage: java f2a <n>");
System.exit(1);
}
}
|
ALGORITHM 2B: LINEAR RECURSION WITH ACCUMULATOR |
import java.math.BigInteger;
class f2b {
private static BigInteger fib(BigInteger x1, BigInteger x2, long n) {
return n<1 ? x1 : fib(x1.add(x2), x1, n-1);
}
private static BigInteger fib(long n) {
return fib(BigInteger.ZERO, BigInteger.ONE, n);
}
private static BigInteger f(long n) {
if(n<0)
return (n%2==0) ? fib(-n).negate() : fib(-n);
else
return fib(n);
}
private static void fib_print(int n) {
System.out.println(n + "th Fibonacci number is " + f(n));
}
public static void main(String argv[]) {
try {
if(argv.length == 1) {
fib_print(Integer.parseInt(argv[0]));
System.exit(0);
}
} catch (NumberFormatException e) { }
System.out.println("Usage: java f2b <n>");
System.exit(1);
}
}
|
ALGORITHM 2C: IMPERATIVE LOOP WITH MUTABLE VARIABLES |
import java.math.BigInteger;
class f2c {
private static BigInteger fib(long n) {
BigInteger x1 = BigInteger.ZERO;
BigInteger x2 = BigInteger.ONE;
BigInteger tmp;
for(long i=1;i<=n;i++) {
x1=x1.add(x2);
tmp=x2; x2=x1; x1=tmp;
}
return x1;
}
private static BigInteger f(long n) {
if(n<0)
return (n%2==0) ? fib(-n).negate() : fib(-n);
else
return fib(n);
}
private static void fib_print(int n) {
System.out.println(n + "th Fibonacci number is " + f(n));
}
public static void main(String argv[]) {
try {
if(argv.length == 1) {
fib_print(Integer.parseInt(argv[0]));
System.exit(0);
}
} catch (NumberFormatException e) { }
System.out.println("Usage: java f2c <n>");
System.exit(1);
}
}
|
ALGORITHM 3A: MATRIX MULTIPLICATION |
import java.math.BigInteger;
class f3a {
private static BigInteger[][] mm(BigInteger[][] m1, BigInteger[][] m2) {
int m1rows = m1.length;
int m1cols = m1[0].length;
int m2cols = m2[0].length;
BigInteger[][] result = new BigInteger[m1rows][m2cols];
for (int i=0; i<m1rows; i++)
for (int j=0; j<m2cols; j++) {
result[i][j] = BigInteger.ZERO;
for (int k=0; k<m1cols; k++)
result[i][j] = result[i][j].add(m1[i][k].multiply(m2[k][j]));
}
return result;
}
private static BigInteger[][] mpow(BigInteger[][] m, int n) {
if(n<=0) {
BigInteger[][] unity = {{BigInteger.ONE ,BigInteger.ZERO},
{BigInteger.ZERO,BigInteger.ONE}};
return unity;
}
BigInteger[][] b = mpow(mm(m,m), n>>1);
return n%2==1 ? mm(m, b) : b;
}
private static BigInteger fib(int n) {
if(n==0) return BigInteger.ZERO;
BigInteger[][] fm = {{BigInteger.ONE,BigInteger.ONE},
{BigInteger.ONE,BigInteger.ZERO}};
fm = mpow(fm, n-1);
return fm[0][0];
}
private static BigInteger f(int n) {
if(n<0)
return (n%2==0) ? fib(-n).negate() : fib(-n);
else
return fib(n);
}
private static void fib_print(int n) {
System.out.println(n + "th Fibonacci number is " + f(n));
}
public static void main(String argv[]) {
try {
if(argv.length == 1) {
fib_print(Integer.parseInt(argv[0]));
System.exit(0);
}
} catch (NumberFormatException e) { }
System.out.println("Usage: java f3a <n>");
System.exit(1);
}
}
|
ALGORITHM 3B: FAST RECURSION |
import java.math.BigInteger;
class f3b {
private static BigInteger[] fib_rec(int n) {
BigInteger[] r = new BigInteger[2];
if(n<=0) {r[0]=BigInteger.ZERO; r[1]=BigInteger.ZERO; return r;}
if(n==1) {r[0]=BigInteger.ZERO; r[1]=BigInteger.ONE; return r;}
BigInteger[] k = fib_rec(n/2);
BigInteger f1 = k[0];
BigInteger f2 = k[1];
BigInteger f3 = f1.add(f2);
if (n%2==1) {
r[0]=f1.add(f3).multiply(f2);
r[1]=f3.multiply(f3).add(f2.multiply(f2));
} else {
r[0]=f1.multiply(f1).add(f2.multiply(f2));
r[1]=f1.add(f3).multiply(f2);
}
return r;
}
private static BigInteger fib(int n) {
return fib_rec(n)[1];
}
private static BigInteger f(int n) {
if(n<0)
return (n%2==0) ? fib(-n).negate() : fib(-n);
else
return fib(n);
}
private static void fib_print(int n) {
System.out.println(n + "th Fibonacci number is " + f(n));
}
public static void main(String argv[]) {
try {
if(argv.length == 1) {
fib_print(Integer.parseInt(argv[0]));
System.exit(0);
}
} catch (NumberFormatException e) { }
System.out.println("Usage: java f3b <n>");
System.exit(1);
}
}
|
ALGORITHM 3C: BINET'S FORMULA WITH ROUNDING |
import java.lang.Math;
import java.math.BigInteger;
import java.math.BigDecimal;
import java.math.MathContext;
import java.math.RoundingMode;
class f3c {
private static BigDecimal isqrt(BigDecimal x, MathContext mc) {
BigDecimal guess = new BigDecimal(1/Math.sqrt(x.doubleValue()));
BigDecimal three = new BigDecimal(3);
BigDecimal half = new BigDecimal(0.5);
BigDecimal oldguess;
do{ oldguess = guess;
guess = half.multiply(guess.multiply(
three.subtract(x.multiply(guess.pow(2)))), mc);
} while (oldguess.compareTo(guess) != 0);
return guess;
}
private static BigInteger fib(int n) {
MathContext mc = new MathContext(n/2, RoundingMode.HALF_DOWN);
BigDecimal is5 = isqrt(new BigDecimal("5"), mc);
BigDecimal one = BigDecimal.ONE;
BigDecimal half = new BigDecimal(0.5);
BigDecimal phi = half.multiply(one.add(one.divide(is5, mc)));
return phi.pow(n, mc).multiply(is5).toBigInteger();
}
private static BigInteger f(int n) {
if(n<0)
return (n%2==0) ? fib(-n).negate() : fib(-n);
else
return fib(n);
}
private static void fib_print(int n) {
System.out.println(n + "th Fibonacci number is " + f(n));
}
public static void main(String argv[]) {
try {
if(argv.length == 1) {
fib_print(Integer.parseInt(argv[0]));
System.exit(0);
}
} catch (NumberFormatException e) { }
System.out.println("Usage: java f3c <n>");
System.exit(1);
}
}
|
|