Memoization

• October 23rd, 2013, 06:39 PM
keepStriving
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.

Code :

```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.
• October 23rd, 2013, 06:46 PM
Norm
Re: Memoization
Where does the code add the other places (besides 0 and 1)?
Does it always add -1 in the other places?
• October 23rd, 2013, 06:57 PM
keepStriving
Re: Memoization
Under the "if not in memory" comment.
Code :

`mapping.put(n,bg);`
• October 23rd, 2013, 07:00 PM
Norm
Re: Memoization
Is that statement executed? What is the value of bg when it is executed?
Try debugging the code by adding some println statements to see what statements are executing and to see the values of the expressions and variables as the code executes.
• October 23rd, 2013, 07:20 PM
keepStriving
Re: Memoization
Thank you so much, got it.
• October 23rd, 2013, 07:24 PM
Norm
Re: Memoization
Can you post your solution so everyone can see what the problem was and how you solved it?
• October 23rd, 2013, 09:12 PM
mjr
Re: Memoization
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!
• October 25th, 2013, 02:17 PM
keepStriving
Re: Memoization
Sorry about the delay. Its for a project Euler problem, consumes a lot of memory.
Code :

```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); } }```
• October 25th, 2013, 02:37 PM
Norm
Re: Memoization
I'm not sure the posted code works. Add some debugging code like this:
Code :

``` //if not in memory System.out.println("test for -1 "+ mapping.get(n)); //<<<<<<<<< if((mapping.get(n).equals(-1))){ ///???; System.out.println("get(n) = -1 for n="+n); //<<<<<<<<<<NEVER printed return mapping.get(n); }```
The second line never prints even though the first line shows a -1:
fib n=0
fib n=1
fib n=2
test for -1 -1
fib n=1
fib n=0
• October 25th, 2013, 02:45 PM
keepStriving
Re: Memoization
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.
• October 25th, 2013, 02:49 PM
Norm
Re: Memoization
Why is it coded to return a -1? If the code I posted worked, then the method would return a -1 instead of a good number.
• October 25th, 2013, 03:04 PM
keepStriving
Re: Memoization
"-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.
• October 25th, 2013, 03:18 PM
Norm
Re: Memoization
The snippet of code I posted says that this expression doesn't work as you expect:
Code :

`mapping.get(n).equals(-1)`
• October 25th, 2013, 03:52 PM
keepStriving
Re: Memoization
Changed it to this still get problems, though I understand its not processing "if in memory" right, I'll get there eventually.
Code :

```//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);```
• October 25th, 2013, 05:11 PM
Norm
Re: Memoization
If you are only using the -1 as a flag, you could create one instance of BigInteger with that value and use it in all the places where the code is creating new instances with the value of -1.

See BigInteger.ZERO for example.
• October 26th, 2013, 04:01 AM
keepStriving
Re: Memoization
Finally got it, got my answer too. Thank you for bearing with me.
Code :

```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); }```
• October 26th, 2013, 05:22 AM
Norm
Re: Memoization
bd should be defined outside of the fibonnaci() method so it is only created one time, not every time the method is called.
• October 26th, 2013, 06:04 AM
keepStriving
Re: Memoization
true, would be better for efficiency.