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 3 of 3

Thread: Recursive Fibonacci sequence optimization

  1. #1
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Recursive Fibonacci sequence optimization

    I've written an algorithm for finding terms in a Fibonacci Sequence using a recursive method. It's fairly quick until around the 45th term which takes roughly 5 seconds to calculate using a primitive type; it goes until the 42nd term using the BigInteger class in about 10 seconds. I need to find the first term that contains 1000 digits. Which also means I have to use the BigInteger class which slows it down. Is there anyway I can speed up my algorithm short of hard-coding all the terms in the sequence up to a specific point?

    public static BigInteger fibSeq(int x)
    	{
    		if( x <= 2)
    		{
    			return BigInteger.ONE;
    		}
    		else
    		{
    			return fibSeq(x-1).add(fibSeq(x-2));
    		}
    	}
    	public static long fibSeqL(long x)
    	{
    		if( x <= 2)
    		{
    			return 1;
    		}
    		else
    		{
    			return fibSeqL(x-1)+(fibSeqL(x-2));
    		}
    	}
     
     
    	public static void main(String[] args)
    	{
    		long start = System.currentTimeMillis();
     
    			System.out.println(fibSeq(42));
     
    		long end = System.currentTimeMillis();
    		System.out.println("Elapsed time: " + (end - start) + "ms");
    	}	
    }


  2. #2
    Member
    Join Date
    Jun 2012
    Location
    Left Coast, USA
    Posts
    451
    My Mood
    Mellow
    Thanks
    1
    Thanked 97 Times in 88 Posts

    Default Re: Recursive Fibonacci sequence optimization

    Quote Originally Posted by aesguitar View Post
    I've written an algorithm for finding terms in a Fibonacci Sequence using a recursive method.
    Here's the thing: Lots of things are "easy" to define and explain, and, maybe even easy to understand as recursive processes.

    However...

    There is a lot of overhead (time and memory) in deep recursive calls. In the case of the Fibonacci sequence, each term requires two recursive calls.

    So...

    Implement iteratively instead of recursively. Make a loop, not a recursive call.

        public static BigInteger fibSeq(int x)
        {
            // Declare BigInteger variables for sum, nminus1 and nminus2
            // Initialize sum to zero and the others to 1
     
            if( x <= 2)
            {
                return BigInteger.ONE;
            } // x <= 2
            else
            {
                for (int i = 3; i <= x; i++)
                {
                    // Set sum equal to nminus1 + nminus2
                    // Set nminus2 equal to nminus1
                    // Set nminus1 equal to sum
                } // for
            } // else
            return sum;
        }


    Now, this can get an answer much quicker.

    But, here's the thing:

    Your problem is not to calculate, say the 3000th term of the sequence. It is to keep calculating until there are 1000 digits in the result and then stop. I mean, the whole problem is to determine how many terms it takes to get up to the 1000 digit thing, right?

    So...

    Here's what I suggest:

    Declare a Fibonacci class. It has private BigInteger variables for sum, nminus1 and nminus2. Because of the quirkiness of the startup routine, I might make a variable named "called" that takes care of the first two terms.

    Then, instead of trying to tell it how many terms to give just make a "next()" method that gives the next term.

    After creating the object, the first call to next() gives F1, the second call gives F2. Just keep calling next() until you get a term with the number of digits you need. (I would probably just keep count of the terms in main(), although you could use the "called" variable in the object if you wanted to create a "getter" method for it.)

    class Fibonacci
    {
        private int called;
        private BigInteger nm2;
        private BigInteger nm1;
     
        // Constructor
        public Fibonacci()
        {
            nm2 = new BigInteger("1");
            nm1 = new BigInteger("1");
            called = 0;
        }
     
        public BigInteger next()
        {
            // Special condition to get the first two terms
            if (called < 2)
            {
                ++called;
                return BigInteger.ONE;
            } // if (called < 2)
            else
            {// A loop to get higher terms.  Note that nm1 and nm2 have been "primed" with values of 1, so it's ready to go
                // Set sum equal to nmi1+nm2
                // Set nm2 equal to nm1
                // Set nm1 equal to sum
            }//else
            return sum;
        }// next
    } // Fibonacci

    Now in main(), create a Fibonacci instance and call its next() method in a loop where the loop control function is the length of the string that the BigInteger.toString() function gives you for the terms as they flow out from the object.
    Of course, instead of making a separate class, the whole Fibonacci loop could be put into main(), and it would save the time-consuming function calls.

    My methodology: Implement first. Optimize later, if appropriate. (It's not a speed contest, right? I mean if a clean, modular object-oriented approach does the deed in a second or so, is there any practical reason to try to get it down to ten milliseconds? maybe so; maybe not.)


    Cheers!

    Z
    Last edited by Zaphod_b; June 24th, 2012 at 01:25 AM.

  3. #3
    Member
    Join Date
    Feb 2012
    Posts
    173
    Thanks
    6
    Thanked 10 Times in 10 Posts

    Default Re: Recursive Fibonacci sequence optimization

    I thought about doing it in a loop, but I needed the practice in recursion. Thanks a lot.

Similar Threads

  1. The Fibonacci sequence
    By Ryuk_93 in forum Android Development
    Replies: 1
    Last Post: March 26th, 2012, 12:56 PM
  2. Java Quick Sort Optimization
    By javaNewb37 in forum What's Wrong With My Code?
    Replies: 1
    Last Post: December 4th, 2011, 07:32 AM
  3. A Star Pathfinding algorithm optimization
    By randomcracker in forum Algorithms & Recursion
    Replies: 4
    Last Post: May 19th, 2011, 12:11 AM
  4. Fibonacci with matrixes and recursive powers
    By Enrico123 in forum What's Wrong With My Code?
    Replies: 4
    Last Post: December 28th, 2010, 08:51 AM
  5. Swing app gui optimization
    By nik_meback in forum AWT / Java Swing
    Replies: 1
    Last Post: December 6th, 2010, 12:55 PM