Using an array to improve the execution time of a recursive binomial distribution algorithm?

Question

As a beginning programmer, I recently bought the book 'Algorithms - Forth Edition' by Robert Sedgewick/Kevin Wayne and I really appreciate the exerices at the end of each chapter. However, there is one exercise (who looks quite simple) that is driving me crazy since I can't find a solution for it.

You have to take this recursive algorithm that finds the probability of getting exactly k successes in n trials where p is the probabily of success for one event. The algorithm given is based on the recursive binomial distribution forumula.

public static double binomial(int n, int k, double p) {
    if (n == 0 && k == 0)
        return 1.0;
    else if (n < 0 || k < 0)
        return 0.0;
    return (1 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);
}

The goal of this exercise is to make this algorithm faster by saving computed values in an array. I already made this algorithm considerably faster by using another way of getting the binomial distribution [p(x) = nCr * p^k * (1 - p)^(n - k)] that uses an iterative method to find factorials. However, I don't understand how an array could be used to improve execution time in this context.

Any help would be greatly appreciated!

... and before someone asks, this is not homeworks!

does your recursion require to recalculate any number that you already have? If that's the case by saving those numbers you can just refer back to them rather than calculate them again. — twain249, Apr 27 '12 at 19:50
If this is not homework, you should be using the closed form version of the binomial distribution: http://en.wikipedia.org/wiki/Binomial_distribution — ControlAltDel, Apr 27 '12 at 19:55

score 5 · Accepted Answer · answered Apr 27 '12 at 19:55

5

The book is trying to teach you a particular programming technique called memoization, a kind of broader technique known as dynamic programming. Of course in real life knowing a closed-form solution is much better, but not in the context of solving this exercise.

Anyway, the idea is to pass a 2D array as your fourth parameter, fill it with NaNs initially, and check if there's a solution for the given combination of n and k in the array before computing anything. If there is, return it; if there isn't, compute it recursively, store in the array, and only then return it.

answered Apr 27 '12 at 19:55

Sergey Kalinichenko

714,442
84
1,110
1,523

so instead of doing the calculation every time, check first if we already know it. Is that right? – Ismael Abreu Apr 27 '12 at 19:57
It's worth noting that you don't actually need a *2D* array to store the values. It's easier to avoid that if you compute the values systematically upwards from n=0, using iteration, instead of downwards from the n you need using recursion. (For historical reasons the term "dynamic programming" is more often used when referring to this sort of iterative structure, and "memoization" when referring to a recursive approach. The two are frequently equivalent.) – Gareth McCaughan Apr 27 '12 at 19:57
@ismaelga Yes, that's the idea behind the memoization technique. Essentially, you pay with memory for speedup of your computations. – Sergey Kalinichenko Apr 27 '12 at 19:59
@GarethMcCaughan You are absolutely right. I would not be surprised if optimizing for memory through employing DP would come as an exercise later in the book. – Sergey Kalinichenko Apr 27 '12 at 20:01

score 2 · Answer 2 · answered Apr 27 '12 at 20:01

The recursive algorithm here ends up calling particular conditions over and over. For example:

It could be made more efficient by remembering, for example, what value (1, 2) came out to, and returning that immediately when called with those parameters again. Using Guava's Table, this would look like:

public static double binomial(int n, int k, double p, Table<Integer, Integer, Double> memo) {
    if(memo.contains(n, k))
        return memo.get(n, k);

    double result;
    if (n == 0 && k == 0)
        result = 1.0;
    else if (n < 0 || k < 0)
        result = 0.0;
    else 
        result = (1 - p) * binomial(n - 1, k, p) + p * binomial(n - 1, k - 1, p);

    memo.put(n, k, result);
    return result;
}

score 1 · Answer 3 · edited May 23 '17 at 12:03

A bit late but for the ones who are looking for a complete solution here is mine below. First I suggest to others to read the answer given here: https://stackoverflow.com/a/6165124/4636721 to understand what dynamic programming, memoization and tabulation mean

Anyway about my solution so basically we have the given method:

// Not efficient at all
private static double binomial(int N, int k, double p)
{
    if (N == 0 && k == 0)
    {
        return 1.0;
    }
    else if ((N < 0) || (k < 0))
    {
        return 0.0;
    }
    else
    {
        return (1.0 - p) * binomial(N - 1, k, p) + p * binomial(N - 1, k - 1, p);
    }
}

Yes this is really slow... the number of recursive calls is kinda big (about ~N^2)

Yes you can use the memoization approach which is basically as others have already stated basically caching values that have been previously computed. For some people memoization imply to keep the recursive strategy and checking the value we need has been calculated or not, if not the program has to compute it and cache it, it's really easy to implement:

private static double binomialTopDown(int N, int k, double p)
{
    double[][] cache = new double[N + 1][k + 1];

    for (int i = 0; i < (N + 1); i++)
    {
         Arrays.fill(cache[i], Double.NaN);
    }

    return binomialTopDown(N, k, p, cache);
}

// More efficient
private static double binomialTopDown(int N, int k, double p, double[][] cache)
{
    if ((N == 0) && (k == 0))
    {
        return 1.0;
    }
    else if ((N < 0) || (k < 0))
    {
        return 0.0;
    }
    else if (Double.isNaN(cache[N][k]))
    {
        cache[N][k] = (1.0 - p) * binomialTopDown(N - 1, k, p, cache) + p * binomialTopDown(N - 1, k - 1, p, cache);
    }

    return cache[N][k];
}

The trick is actually to use the bottom-up approach (also called tabulation) to order the computations in an much more efficient way. This is usually achieved by using an iterative version of the algorithm above.

// Much more efficient
private static double binomialBottomUp(int N, int k, double p)
{
    /*
    double[][] cache = new double[N + 1][k + 1];

    cache[0][0] = 1.0;

    for (int i = 1; i <= N; i++)
    {
        cache[i][0] = Math.pow(1.0 - p, i);

        for (int j = 1; j <= k; j++)
        {
            cache[i][j] =  p * cache[i - 1][j - 1] + (1.0 - p) * cache[i - 1][j];
        }
    }

    return cache[N][k];
    */

    // Optimization using less memory, swapping two arrays
    double[][] cache = new double[2][k + 1];
    double[] previous = cache[0];
    double[] current = cache[1];
    double[] temp;

    previous[0] = 1.0;

    for (int i = 1; i <= N; i++)
    {
        current[0] = Math.pow(1.0 - p, i);

        for (int j = 1; j <= k; j++)
        {
            current[j] =  p * previous[j - 1] + (1.0 - p) * previous[j];
        }

        temp = current;
        current = previous;
        previous = temp;
    }

    return previous[k];
}

Which is the most efficient way to do it using dynamic programming with the Bottom Up approach.

Hope this helps.

Using an array to improve the execution time of a recursive binomial distribution algorithm?

3 Answers3