Guide to Prolog Programming	© Roman Barták, 1998
Home	Previous | Contents | Next
Top Down vs. Bottom Up Computation

In the previous chapter, we study the recursion, a powerfull method of solving problems using decomposition to smaller problems of the same type. Recursion in Prolog uses the top down method of computation typically.

---

Top Down Computation

Top down computation, typically used in Prolog, starts with the original problem and it decomposes this problem to simpler and simpler problems till the trivial problem, i.e., the fact in Prolog database, is reached. Then, the solution of larger problems is composed of the solutions of simpler problems etc. till the solution of the original problem is obtained. Following two examples present programs that use the top down computation.

Factorial

To compute the factorial of N we first compute the factorial of N-1 using the same procedure (recursion) and then, usign the result of subproblem, we compute the factorial of N. The recursion stops when a trivial problem is reached, i.e., when a factorial of 0 is computed.

fact_td(0,1).
fact_td(N,F):-N>0, N1 is N-1, fact_td(N1,F1), F is N*F1.

Note, that the complexity of the above procedure is linear, i.e., we need N+1 calls of the procedure fact_td.

Fibonacci

The following program computes Fibonacci numbers using the top down method, i.e., if we are looking for Fibonacci number of N>1, we first compute Fibonacci numbers of N-1 and N-2 (usign the same procedure) and, then, we compose the Fibonacci number of N from the subresults. In this case, the recursion stops as soon as the Fibonacci number of 0 or 1 is computed.

fibo_td(0,0).
fibo_td(1,1)
fibo_td(N,F):-
  N>1, N1 is N-1, N2 is N-2,
  fibo_td(N1,F1), fibo_td(N2,F2),
  F is F1+F2.

Note, that the above procedure is very inefficient if standard Prolog execution rule is used because we compute the same thing many times. For example, to compute F(N-1) we need to compute F(N-2) which is also required to compute F(N) that was decomposed to F(N-1) and F(N-2). In fact, the complexity of the above procedure is exponential thas is "not very efficient".

---

Bottom Up Computation

Even if the top down computation is typical for Prolog, we can still simulate the bottom up computation as well without changes of the Prolog interpreter. The bottom up computation starts with know facts and extends the set of know trues using rules. i.e., it derives new facts from old facts and rules. This extension continues till the solved problem is present in the computed set of facts.

In general, pure bottom up method is less efficient than top down method because many facts are derived that has nothing in common with the original problem. Therefore, Prolog uses top down evaluation as a standard method of computation. However, in same cases, it is possible to guide the bottom up evaluation towards the solution of the original problem.

The following two examples present bottom up versions of the above two procedures for computing factorial and Fibonacci numbers. The advantage of bottom up evaluation is visible mainly in the procedure fibo_bu that is a lot of faster than fibo_td.

Factorial

Now, we compute the factorial usign bottom up method so we start with the trivial problem of computing the factorial of 0 and continue with the factorial of 1, 2 and so on till the factorial of N is known. Because we do not want to change the standard behaviour of Prolog, that is top down in nature, we need to simulate the bottom up compution, i.e., we have to store the computed facts using additional parameters. In this case, we remember only the last computed "fact" namely the factorial of M in the M-th step.

fact_bu(N,F):-fact_bu1(0,1,N,F).
   
fact_bu1(N,F,N,F).
fact_bu1(N1,F1,N,F):-
  N1<N, N2 is N1+1, F2 is N2*F1, fact_bu1(N2,F2,N,F).

Note, that the complexity of the above procedure is linear again, i.e., we need N+1 calls of the procedure fact_bu1. However, the procedure fact_bu1 is more efficient than fact_td because it can be translated using iteration, i.e., without a stack required by the recursion in fact_td.

Fibonacci

We can use the same principle as in "bottom-up factorial" to compute the Fibonacci numbers using bottom up method. Now, we need to remember last two Fibonacci numbers to be able to compute the next Fibonacci number.

fibo_bu(N,F):-fibo_bu1(0,0,1,N,F).
   
fibo_bu1(N,F,_,N,F)
fibo_bu1(N1,F1,F2,N,F):-
  N1<N, N2 is N1+1, F3 is F1+F2,
  fibo_bu1(N2,F2,F3,N,F).

Note, that the complexity of fibo_bu is linear and therefore the procedure fibo_bu is far away efficient than fibo_td that is exponential.

Designed and maintained by Roman Barták	Previous | Contents | Next