A short guide to precomputation

Post date: Sep 25, 2012 12:27:17 AM

This is a short guide to precomputation -- no (real) programming language was abused during the making of this guide.

Introduction

Precomputation of functions comes up often in practice. Suppose you want to compute the cosine of an angle. A call to a pre-defined cosine function may look like this:

r = cos(40)

But what if this were to be called millions of times? As fast as the function may be computed, it adds up to a significant amount. Instead suppose that you precomputed the cosines of common angles. Your code might look something like this:

COS = []

for i in 0 to 359

    COS[i] = cos(i)

r = COS[40]

You would first create an array with enough space to contain your precomputed values, then populate the array by computing the function and adding this value to the right position in the array. When that is done, accessing the array at the proper index will give you the same value as calling the function.

Assuming that an array access is faster than computing the value, you save time every time you access the array. Therefore, if you do this millions of times you can save a significant amount. (The amount may not be very significant for fast operations such as finding the reciprocal of an integer, but you can measure the performance if you want to see for yourself. This is left as an exercise.)

Recursion

What if you wanted to precompute the values of a recursively defined function? Let's take the function which computes the Fibonacci sequence. One well-known approach is as follows:

fib(n)

    if n < 2

        return n

    return fib(n - 1) + fib(n - 2)

v = fib(30)

You are probably aware that the number of calls grows very quickly as the input grows. How to speed it up? Notice that if you have already computed the last two Fibonacci numbers, you can compute the current one simply by adding them. Let's apply the precomputation technique -- create an array and populate it by computing the function:

FIB = []

for i in 0 to 30

    FIB[i] = FIB[i - 1] + FIB[i - 2]

v = FIB[30]

We are still missing the base case(s) here. Without them we could never start computing the function! Therefore we initialize the base case(s) before computing, as follows:

FIB = []

FIB[0] = 0

FIB[1] = 1

for i in 2 to 30

    FIB[i] = FIB[i - 1] + FIB[i - 2]

v = FIB[30]

Problem solved.

Sometimes -- or often -- functions are expressed more clearly and written more easily when they are written recursively. But how can you benefit from recursion while precomputing your values? Lazy evaluation.

Lazy Evaluation

In summary, lazy evaluation means to store a precomputed value only when you compute it. A function written in a lazy way should work just like a non-lazy one. To see how this works, here is the aforementioned cosine function written in a lazy way:

COS = []

lazycos(x)

    if COS[x] == null

        COS[x] = cos(x)

    return COS[x]

r = lazycos(40)

But what motivates the use of lazy evaluation?

• You may not know ahead of time which values you need.
• You may not know the order in which to precompute the values.
• Simply figuring out the order takes additional effort.
• You want to avoid precomputing all possible values of a function because the computation is too slow or the problem domain is too large.

Now let's see how it can be applied to a recursive function. The Fibonacci function written using lazy evaluation may look like this:

FIB = []

lazyfib(n)

    if FIB[n] != null

        return FIB[n]

    ans = 0

    if n < 2

        ans = n

    else

        ans = lazyfib(n - 1) + lazyfib(n - 2)

    FIB[n] = ans

    return ans

v = lazyfib(30)

Notice that there is extra logic to check whether or not the function has been computed.

The benefit to you is that when writing the recursive case, you can assume that whatever values on which you depend have already been taken care of, since calling the function should be a guaranteed success just like the non-lazy way. In the above, the base cases are handled inside the function, but you can handle them outside of the function. This is left as an exercise.

Lazy evaluation addresses the problem of knowing in which order to compute the values. For this example, we do not need to know that we have to precompute the values in increasing order. But it does not seem useful for this example; there are problems where the order in which you have to evaluate a function is not clear. Such as:

Exercise:

Here is another way of expressing the Fibonacci function F(n).

  F0 = 0

  F1 = 1

  F2n = 2Fn-1Fn + Fn2

  F2n-1 = Fn-12 + Fn2

Find the last 10 digits of Fx where x = 1018.

Precomputation in Multiple Dimensions

Similar reasoning can be applied to functions that take multiple arguments, such as computing the values in Pascal's triangle. (I will make the assumption that the reader is familiar with Pascal's triangle. If not, it would be fun to look it up.)

If we index Pascal's triangle by row, and then column, starting from 0, we can have a function that looks like P(r, c). Therefore the only number in row 0 would be P(0, 0), the numbers in row 1 would be P(1, 0) and P(1, 1), etc. The base cases of this function would be the borders of the triangle, where the value always equals 1. This happens when c = 0 or c = r. Writing this recursively, it would look like this:

pascal(r, c)

    if c == 0 || c == r

        return 1

    return pascal(r - 1, c - 1) + pascal(r - 1, c)

If you wanted to precompute this function using an array, you would probably use a two-dimensional one. The logic is more involving than that of a simpler function such as the Fibonacci function, so be sure to look it over:

PAS = [][]

for i in 0 to 20

    PAS[i][0] = PAS[i][i] = 1

for r in 0 to 20

    for c in 1 to r - 1

        PAS[r][c] = PAS[r - 1][c - 1] + PAS[r - 1][c]

Writing this function in a lazy way is left as an exercise.

Exercise:

A robot wants to travel from one corner of a warehouse to another. Unfortunately its path blocked by large boxes. For some reason the robot is only capable of moving toward its destination, and for some other reason the robot wants to figure out how many ways it can get there.

The room is specified by a grid, where a dot is an empty space and an X is a box:

  ...XX

  .....

  .XX..

  ..X..

  .....

The robot starts from the top-left corner and can move right or down one space on the grid. Find the number of ways it can reach the bottom-right corner.

And that concludes this guide. What are you doing? Go out and code some fun stuff!