Welcome to the Java Programming Forums


The professional, friendly Java community. 21,500 members and growing!


The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.


>> REGISTER NOW TO START POSTING


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 18 of 18

Thread: Memoization

  1. #1
    Member
    Join Date
    May 2013
    Posts
    165
    Thanks
    58
    Thanked 1 Time in 1 Post

    Default 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.


  2. #2
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,376
    Thanks
    49
    Thanked 2,208 Times in 2,181 Posts

    Default Re: Memoization

    Where does the code add the other places (besides 0 and 1)?
    Does it always add -1 in the other places?
    If you don't understand my answer, don't ignore it, ask a question.

  3. The Following User Says Thank You to Norm For This Useful Post:

    keepStriving (October 23rd, 2013)

  4. #3
    Member
    Join Date
    May 2013
    Posts
    165
    Thanks
    58
    Thanked 1 Time in 1 Post

    Default Re: Memoization

    Under the "if not in memory" comment.
    mapping.put(n,bg);

  5. #4
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,376
    Thanks
    49
    Thanked 2,208 Times in 2,181 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  6. #5
    Member
    Join Date
    May 2013
    Posts
    165
    Thanks
    58
    Thanked 1 Time in 1 Post

    Default Re: Memoization

    Thank you so much, got it.

  7. #6
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,376
    Thanks
    49
    Thanked 2,208 Times in 2,181 Posts

    Default Re: Memoization

    Can you post your solution so everyone can see what the problem was and how you solved it?
    If you don't understand my answer, don't ignore it, ask a question.

  8. #7
    Member mjr's Avatar
    Join Date
    Jan 2012
    Location
    127.0.0.1
    Posts
    36
    My Mood
    Fine
    Thanks
    8
    Thanked 2 Times in 1 Post

    Default 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!

  9. #8
    Member
    Join Date
    May 2013
    Posts
    165
    Thanks
    58
    Thanked 1 Time in 1 Post

    Default Re: Memoization

    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);
        }
    }

  10. #9
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,376
    Thanks
    49
    Thanked 2,208 Times in 2,181 Posts

    Default Re: Memoization

    I'm not sure the posted code works. Add some debugging code like this:
    		//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
    If you don't understand my answer, don't ignore it, ask a question.

  11. The Following User Says Thank You to Norm For This Useful Post:

    keepStriving (October 25th, 2013)

  12. #10
    Member
    Join Date
    May 2013
    Posts
    165
    Thanks
    58
    Thanked 1 Time in 1 Post

    Default 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.

  13. #11
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,376
    Thanks
    49
    Thanked 2,208 Times in 2,181 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  14. #12
    Member
    Join Date
    May 2013
    Posts
    165
    Thanks
    58
    Thanked 1 Time in 1 Post

    Default 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.

  15. #13
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,376
    Thanks
    49
    Thanked 2,208 Times in 2,181 Posts

    Default Re: Memoization

    The snippet of code I posted says that this expression doesn't work as you expect:
    mapping.get(n).equals(-1)
    If you don't understand my answer, don't ignore it, ask a question.

  16. #14
    Member
    Join Date
    May 2013
    Posts
    165
    Thanks
    58
    Thanked 1 Time in 1 Post

    Default Re: Memoization

    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);

  17. #15
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,376
    Thanks
    49
    Thanked 2,208 Times in 2,181 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  18. The Following User Says Thank You to Norm For This Useful Post:

    keepStriving (October 26th, 2013)

  19. #16
    Member
    Join Date
    May 2013
    Posts
    165
    Thanks
    58
    Thanked 1 Time in 1 Post

    Default Re: Memoization

    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);
        }

  20. #17
    Super Moderator Norm's Avatar
    Join Date
    May 2010
    Location
    SW Missouri
    Posts
    20,376
    Thanks
    49
    Thanked 2,208 Times in 2,181 Posts

    Default 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.
    If you don't understand my answer, don't ignore it, ask a question.

  21. The Following User Says Thank You to Norm For This Useful Post:

    keepStriving (October 26th, 2013)

  22. #18
    Member
    Join Date
    May 2013
    Posts
    165
    Thanks
    58
    Thanked 1 Time in 1 Post

    Default Re: Memoization

    true, would be better for efficiency.

Similar Threads

  1. Memoization (dyanamic programming) for edit distance recursion
    By rph12 in forum Algorithms & Recursion
    Replies: 4
    Last Post: January 28th, 2011, 09:37 AM