6
\$\begingroup\$

This is my recursive program for the following function:

  • \$F(x) = G(x) - W(x)\$
  • \$G(x) = [G(x-1)+G(x-2)]^2\$
  • \$W(x) = [W(x-1)]^2 + [W(x-2)]^2\$
  • If x == 0 in either function G or function W, then return 0
  • If x == 1 in either function G or function W, then return 1

import java.math.BigInteger;
import java.io.PrintWriter;
import java.io.IOException;

public class RecursiveProgram
{
    BigInteger test = BigInteger.valueOf(30);
    BigInteger zero = new BigInteger(Integer.toString(0));
    BigInteger one = new BigInteger(Integer.toString(1));
    BigInteger two = new BigInteger(Integer.toString(2));
    public BigInteger G(BigInteger x)
    {
        if(x.equals(zero))
            return zero;
        if(x.equals(one))
            return one;
        return (G(x.subtract(one)).add(G(x.subtract(two)))).multiply((G(x.subtract(one)).add(G(x.subtract(two)))));
    }

    public BigInteger W(BigInteger x)
    {
        if(x.equals(zero))
            return zero;
        if(x.equals(one))
            return one;
        return ((W(x.subtract(one))).multiply(W(x.subtract(one)))).add((W(x.subtract(two))).multiply(W(x.subtract(two))));
    }

    public void solveForF() throws IOException
    {
        PrintWriter writer = new PrintWriter("C:/Users/my computer/Desktop/f(30).txt");
        writer.println(G(test).subtract(W(test)));
        writer.close();
    }
}

It writes the calculated number to the .txt file on my desktop. I want to improve the recursive program to allow it to calculate F(30). However, I did some math calculations as to how long it would take for the program to complete using the amount of time it took to calculateF(20) and F(21), approximating to 12.35 days. Obviously this is inefficient and I haven't learned a better method to make it more efficient. I've heard of dynamic programming but I'm not sure as how I would use it here.

\$\endgroup\$
  • \$\begingroup\$ Dynamic programming would basically involve storing calculations you do a bunch then accessing their values instead of calculating them over and over. You could pretty easily figure out what you can cache by writing your own wrapper around BigInteger that logs every operation made, though be aware that that's gonna skew any profiling you do, since logging is much slower than math. For example, when calculating factorials, you could store 21! so that when you calculate 25! you don't need to iterate through every single number. \$\endgroup\$ – Nic Hartley Dec 4 '15 at 4:00
  • \$\begingroup\$ If logging takes longer, do you have any suggestions as to what I could possibly use? \$\endgroup\$ – immmjimmy Dec 4 '15 at 4:01
  • \$\begingroup\$ I'm suggesting logging to figure out where you can cache, then removing it in the final version. \$\endgroup\$ – Nic Hartley Dec 4 '15 at 4:01
  • \$\begingroup\$ Ah I see. Hmm, that would work. Do you have a potential solution? I've never cached before. \$\endgroup\$ – immmjimmy Dec 4 '15 at 4:04
  • 1
    \$\begingroup\$ If you want to cross-check your solution, this is the answer I got for \$F(30)\$ (zip file, 44MB). \$\endgroup\$ – mjolka Dec 4 '15 at 11:15
4
\$\begingroup\$

Your function is extremely slow because it does a lot of redundant calculations.

$$ \begin{align} G(5) =& (G(4) + G(3))^{2} \\ =& (G(4) + G(3)) \cdot (G(4) + G(3)) \\ =& ((G(3) + G(2))^{2} + (G(2) + G(1))^{2})) \cdot ((G(3) + G(2))^{2} + (G(2) + G(1))^{2})) \\ =& ((G(3) + G(2)) \cdot (G(3) + G(2)) + (G(2) + G(1)) \cdot (G(2) + G(1)))) \cdot ((G(3) + G(2)) \cdot (G(3) + G(2)) + (G(2) + G(1)) \cdot (G(2) + G(1))))) \\ =& \ldots \end{align} $$

The complexity is \$O(4^x)\$: to calculate \$G(x)\$, you're breaking it into four problems of approximately the same size.

To start with, it would be smarter to square a number without having to compute the base again.

$$ \begin{align} G(5) =& (G(4) + G(3))^{2} \\ =& ((G(3) + G(2))^{2} + (G(2) + G(1))^{2}))^{2} \\ =& \ldots \end{align} $$

Then you would be down to "just" \$O(2^x)\$, which is still horrible.

The trick is to notice that you're going to be computing \$G(2)\$, \$G(3)\$, etc. many many times. What you want to do is memoization — caching previously computed results. With memoization, you should be able to compute \$G(x)\$ in \$O(x)\$ time.

Once you solve the efficiency issue above, you will still run into a problem with stack overflow for large \$x\$. To avoid stack overflow, you'll want to reimplement the functions using an iterative loop rather than recursion.

\$\endgroup\$
2
\$\begingroup\$

This seems like a method suitable for the dynamic programming method. As 200_success said in his answer, the use of memoization can greatly improve performance. What I want to add to the answer are two ways to go with solving the problem.

In-time processing

This is the way suggested in 200_success' answer (if I understood it correctly). Let's go at it one step at a time. We have that \$G(0) = 0\$, \$G(1) = 1\$, and \$G(n) = [G(n-1) + G(n-2)]^2\$. By caching the result of \$G(n-2)\$ and \$G(n-1)\$ we can easily calculate \$G(n)\$, so, for \$n >= 2\$ we can use the following algorithm (in pseudo-code):

int calculateG(int n){
    if(n == 0){
        return 0;
    }

    if(n == 1){
        return 1;
    }

    int nMinus2 = 0;
    int nMinus1 = 1;
    int result;

    for(int i = 2; i <= n; i++){
        result = Math.pow(nMinus1 + nMinus2, 2);
        nMinus2 = nMinus1;
        nMinus1 = result;
    }

    return result;
}

This approach calculates each result in \$O(n)\$ time and has a space complexity of \$O(1)\$ and, IMO, is the way to go if the function is calculated not so often.

Cached-result processing

In case the function is calculated often I'd suggest another approach. If you use an appropriate data structure (an arraylist should be ideal) you can implement the function in the following way:

ArrayList values = new ArrayList();
// append G(0)
values.append(0);
// append G(1)
values.append(1);

int calculateG(int n){
    return getValue(n);
}

int getValue(int n){
    // this is calculated in O(n) time in the worst case (where n is greater than the current length of the list)
    for(int i = value.length - 1; i <= n; i++){
        // this is calculated in O(1) time if the get() method accesses the elements in O(1) time
        value.append(Math.pow(value.get(i) + value.get(i-1), 2));
    }

    return value.get(n);
}

This approach has a time complexity of \$O(n)\$ in the worst case (when \$n\$ is much greater than the number of cached elements) and \$O(1)\$ in the best case (when \$n\$ is smaller than, or equal to, the number of cached elements). In the average case the number of calculations is reduced, but still remains \$O(n)\$. The space complexity, on the other hand, is \$O(n)\$ in all cases.

Let me know if anything's unclear.

P.S.: The same logic applies to \$G(n)\$ and \$W(n)\$. Also, all code is pseudo-code, it's there just to better explain the idea.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.