Thread: Memoization

I'm trying to compute fibonacci for extremely large numbers so I'm using memoization and BigInteger.
The trouble is I can't get it to work. I keep getting output -1 for all except the first and second places in HashMap.

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
 
 
public class ProjectEuler{
	static Map<Integer,BigInteger> mapping = new HashMap<Integer,BigInteger>();
 
	public static void main(String[] args){
 
	  mapping.put(0, BigInteger.ZERO);
	  mapping.put(1, BigInteger.ONE);
 
	for(int i=2;i<999;i++){
		mapping.put(i, (new BigInteger("-1")));
	}
 
	//fibonnaci for 0 to 10
	for(int i=0;i<11;i++){
	    System.out.println(fibonnaci(i));
    }
}
 
 
 
	public static BigInteger fibonnaci(int n){
 
		//if n==0
		if(n<1){
			return mapping.get(0);
		}
		//if n==1
		if(n<2){
			return mapping.get(1);
		}
 
		//if in memory
		if(!(mapping.get(n).equals(-1))){
			return mapping.get(n);
	    }
 
		//if not in memory
	   BigInteger bg = fibonnaci(n-1).add(fibonnaci(n-2));
       mapping.put(n, bg);
       return mapping.get(n);
    }
}

--- Update ---

I get a 0, then 1, then the rest of the output is -1.

Under the "if not in memory" comment.

mapping.put(n,bg);

Thank you so much, got it.

I don't know about you, but I'd use a decimal primitive type, and Binet's formula to get large fibonacci numbers. Pass in the "position", have a method that calculates based on Binet's formula, and out pops the fibonacci number at that position!

Sorry about the delay. Its for a project Euler problem, consumes a lot of memory.

import java.math.BigInteger;
import java.util.HashMap;
import java.util.Map;
 
 
public class ProjectEuler{
	static Map<Integer,BigInteger> mapping = new HashMap<Integer,BigInteger>();
 
	public static void main(String[] args){
 
	  mapping.put(0, BigInteger.ZERO);
	  mapping.put(1, BigInteger.ONE);
 
	for(int i=2;i<99999;i++){
		mapping.put(i, (new BigInteger("-1")));
	}
 
	//fibonnaci for 0 to 10
	for(int i=0;i<99999;i++){
		String string = fibonnaci(i).toString();
		if(string.length()>=1000){
	    System.out.println(i);
	    return;
    }
	}
}
 
 
 
	public static BigInteger fibonnaci(int n){
		//if n==0
		if(n<2){
			return (new BigInteger(Integer.toString(n)));
		}
		//if n==1
		//if(n<2){
			//return BigInteger.ONE;
		//}
 
		//if not in memory
		if((mapping.get(n).equals(-1))){;
			return mapping.get(n);
	    }
 
		//if in memory
	   BigInteger bg = fibonnaci(n-1).add(fibonnaci(n-2));
       mapping.put(n, bg);
       return mapping.get(n);
    }
}

You are right, the fibonacci works as I've tested for some numbers though something has going wrong with storage I think which is why it's taking so long for greater numbers.

"-1" was meant to symbolise that certain value fibonacci value has been added. Though I think where I have gone is that when I tried this with array I had a mapping between "i" in the array and fibonnaci("n"), as I added Fibonacci("n") at position "i" in array, and have seemingly tried that with big integer which doesn't work.

Changed it to this still get problems, though I understand its not processing "if in memory" right, I'll get there eventually.

//if in memory, if greater than -1, meaning has a value other than -1
		if(mapping.get(n).compareTo(new BigInteger("-1"))>1){
			return mapping.get(n);
		}
 
		//if not in memory
		BigInteger bg = fibonnaci(n-2).add(fibonnaci(n-1));
		mapping.put(n,bg);
		return mapping.get(n);

Finally got it, got my answer too. Thank you for bearing with me.

public static BigInteger fibonnaci(int n){
		BigInteger bd = new BigInteger("-1");
	//if n==0||n==1
		if(n==0||n==1){
			return (new BigInteger(Integer.toString(n)));
		}
 
		//if in memory, if greater than -1, meaning has a value other than -1
		if(mapping.get(n).compareTo(bd)==1){
			return mapping.get(n);
		}
 
		//if not in memory
		BigInteger bg = fibonnaci(n-2).add(fibonnaci(n-1));
		mapping.put(n,bg);
		return mapping.get(n);
    }

true, would be better for efficiency.