Dynamic programming with Fibonacci

Question

I have written the following code using a dynamic programming technique. Can I use ArrayList here? Please let me know if I can improve this code.

package com.java.fib; import java.math.BigInteger; import java.util.HashMap; public class Fibonaci { public static void main(String[] args) { System.out.println(" number "); long startTime = System.currentTimeMillis(); HashMap<Integer, BigInteger> memoized = new HashMap<Integer, BigInteger>(); fibonanci(220, memoized); System.out.println(" Total Time " + (System.currentTimeMillis() - startTime)); } private static BigInteger fibonanci(int n, HashMap<Integer, BigInteger> memoized) { if (memoized.containsKey(n)) { return memoized.get(n); } if (n <= 0) { return BigInteger.ZERO; } if (n <= 2) { return BigInteger.ONE; } else { BigInteger febonani = fibonanci(n - 1, memoized).add (fibonanci(n - 2, memoized)); System.out.println(" febonani " + febonani); memoized.put(n, febonani); return febonani; } } } 

Answer 1

A few things:

Naming:

It's neither Fibonaci, nor febonani, nor fibonanci it's fibonacci. Please get your names to reflect what you're actually talking about and not some disfigured mutation of it :(

memoized OTOH is a relatively nice name, I'd probably prefer memoizedFibonacciNumbers, but that's a thing of preference

Calculating:

quoting wikipedia:

By definition, the first two numbers in the Fibonacci sequence are \$1\$ and \$1\$, or \$0\$ and \$1\$, depending on the chosen starting point of the sequence, and each subsequent number is the sum of the previous two.

You on the other hand say:

The value of Fibonacci for \$n <= 0\$ is \$0\$, and for \$n <= 2\$ is \$1\$, and each subsequent number is the sum of the previous two.

Wikipedia also mentions "negative Fibonacci numbers". Your definition does not match the actual Fibonacci sequence definition :(

instead your fibonacci method should look like this, if you exactly follow the rules for only positive fibonacci numbers:

private static BigInteger fibonacci(Integer n, HashMap<Integer, BigInteger> memoized) { if (n < 0) { throw new IllegalArgumentException("We assume the positive Fibonacci sequence only"); } if (memoized.containsKey(n)) { return memoized.get(n); } if (n == 0) { memoized.put(n, BigInteger.ZERO); return memoized.get(n); } if (n == 1) { memoized.put(n, BigInteger.ONE); return memoized.get(n); } BigInteger fibonacci = fibonacci(n-1, memoized).add(fibonacci(n-2, memoized)); memoized.put(n, finbonacci); return fibonacci; } 

Printing is slow:

I see you benchmarking your code. Please keep in mind, that writing something to the Console is quite slow. Your measured execution time is not matching the calculation time.

You should remove the System.out.println() in your fibonacci method.

Conditionals

Also you maybe have already realized, I removed the else in the fibonacci method.

This is because if your code reaches that area, all other branches have returned early, and the else is quite useless.

Answer 2

@Vogel612 has already mentioned all major defects and areas of improvement in your code. I want to talk about one more thing:

Your package naming is horrible. You are using com.java.fib, please do not ever do that again, because:

1. Although Java classes are prefixed with java.*, it still creates confusion as people might think this is a library class. In extreme cases when you use professional names, it might even lead to a name clash.
2. You are pretending to be or have anything to do with java.com, which you really aren't and haven't.
3. Change it to something imaginary or existing. Use your own name, or your own website, I usually use com.skiwi.*.
4. Even com.skiwi.fib would be horrible because it offers barely any extra information, com.java.fib.Fibonacci is not helpful, consider something along the lines of com.skiwi.algorithms, in which the class Fibonacci can be found.

Answer 3

Don't use ArrayList. A lookup in the list with get(220) will throw an IndexOutOfBoundsException. Your list is not initialized by default. What you can do is to use an array for your values. It allows you to check, if an index is already filled (via != null). On the other hand, you'll have to predefine the size of your array. Also you'll have to check for indexbounds as well.

public static void main(String[] args) { final BigInteger[] fibonacciCache = new BigInteger[221]; fibonacciCache[0] = BigInteger.ZERO; fibonacciCache[1] = BigInteger.ONE; fibonacci(220, fibonacciCache); } private static BigInteger fibonacci(int n, final BigInteger[] fibonacciCache) { if (n<0) n=0; if (fibonacciCache[n]!=null) { return fibonacciCache[n]; } fibonacciCache[n] = fibonacci(n - 1, fibonacciCache).add(fibonacci(n - 2, fibonacciCache)); return fibonacciCache[n]; } 

Answer 4

Aside from the things other people have mentioned (notably throwing an error on negative numbers and correcting the spelling), I would reorder some of the functionality and add more elses like so:

 private static BigInteger fibonacci(int n, HashMap<Integer, BigInteger> memoized) { if (n <= 0) { return BigInteger.ZERO; } else if (n <= 2) { return BigInteger.ONE; } else if (memoized.containsKey(n)) { return memoized.get(n); } else { BigInteger result = fibonacci(n - 1, memoized).add (fibonacci(n - 2, memoized)); memoized.put(n, result); return result; } } 

I'd also suggest that instead of making the user provide the memoized hash, you instead make a private static hash. Aside from making less work for the user, this would also allow you to preload the hash with the values of 0, 1 and 2, meaning you could strim out some of the function's logic and make it simpler.

 private static HashMap<Integer, BigInteger> memoizedHash; static { memoizedHash = new HashMap<Integer, BigInteger>(); memoizedHash.put(0, BigInteger.ZERO); memoizedHash.put(1, BigInteger.ONE); memoizedHash.put(2, BigInteger.ONE); } private static BigInteger fibonacci(int n) { assert (n >= 0) : "This function does not accept negative numbers"; if (memoizedHash.containsKey(n)) { return memoizedHash.get(n); } else { BigInteger result = fibonacci(n - 1).add (fibonacci(n - 2)); memoizedHash.put(n, result); return result; } } 

Answer 5

You can use ArrayList instead of HashMap here.

Update:

After some comments, I reimplement using non-recursive way, it took a bit longer than your source code (15 ms in comparison with 11 ms running on my computer), but most of time is spent to print output by System.out.println function. There is a small difference, I added 3 first numbers of Fibonaci sequence (0, 1, 1) to the result array.

public class Fibonaci { public static int count = 0; public static void main(String[] args) { ArrayList<BigInteger> memoized = new ArrayList<BigInteger>(); long startTime = System.currentTimeMillis(); fibonanci(220, memoized); for(int i = 0; i < memoized.size(); i++) { System.out.println(" febonani " + memoized.get(i)); } System.out.println(" Total Time " + (System.currentTimeMillis() - startTime)); } private static BigInteger fibonanci(int n, ArrayList<BigInteger> memoized) { BigInteger febonani = BigInteger.ZERO; int size = memoized.size(); if (n < 0) { return BigInteger.ZERO; } if (size > n) { febonani = memoized.get(n); } else { for(int i = size; i <= n; i++) { if(i == 0) { febonani = BigInteger.ZERO; } else if(i == 1 || i == 2) { febonani = BigInteger.ONE; } else { febonani = memoized.get(i - 1).add(memoized.get(i - 2)); } memoized.add(febonani); } } return febonani; } }