Fibonacci

Java

The Fibonacci sequence is a series of numbers where a number is a result of adding up the two numbers before it.
Starting with 0 and 1, the sequence goes 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 etc.

a smart way

final int GOAL = 50000; long startTime = System.currentTimeMillis(); BigInteger prevPrev = BigInteger.ZERO; BigInteger prev = BigInteger.ONE; BigInteger current = null; for (long i = 2; i <= GOAL; i++) { current = prev.add(prevPrev); prevPrev = prev; prev = current; } System.out.println(current); System.out.println("Shortcut: " + (System.currentTimeMillis() - startTime));

The following examples (iterative and recursive) cache all numbers, so while they take longer, you'll have quicker access to any individual number

iterative

int GOAL = 50000; HashMap<Long, BigInteger> cache; cache = new HashMap<>(GOAL); long startTime = System.currentTimeMillis(); cache.put(0l, BigInteger.ZERO); cache.put(1l, BigInteger.ONE); for (long i = 2; i <= GOAL; i++) { cache.put(i, cache.get(i - 1).add(cache.get(i - 2))); } System.out.println(cache.get(GOAL * 1l)); System.out.println("Iterative: " + (System.currentTimeMillis() - startTime));

recursive

private static final int GOAL = 50000; private static HashMap<Long, BigInteger> cache; void getFib() { cache = new HashMap<>(GOAL); startTime = System.currentTimeMillis(); // this will prevent a stackoverflow for (int point = 4000; point <= GOAL; point += 2000) getFibonacci(point); System.out.println(getFibonacci(GOAL * 1l)); System.out.println("Recurive: " + (System.currentTimeMillis() - startTime)); } BigInteger getFibonacci(long n) { if (n == 0) return BigInteger.ZERO; else if (n == 1) return BigInteger.ONE; else { if (!cache.containsKey(n)) { BigInteger number = getFibonacci(n - 1).add(getFibonacci(n - 2)); cache.put(n, number); return number; } return cache.get(n); } }

Reference

No known

History Mar 20, 2019