Did you know ... | Search Documentation: |

Example 1: using tabling for memoizing |

- Home
- DOWNLOAD
- DOCUMENTATION
- TUTORIALS
- Beginner▶
- Advanced▶
- Web applications▶
- Semantic web▶
- Graphics▶
- Machine learning▶
- External collections▶
- For packagers▶

- COMMUNITY
- USERS
- WIKI

As a first classical example we use tabling for *memoizing*
intermediate results. We use Fibonacci numbers to illustrate the
approach. The Fibonacci number `I` is defined as the sum of the
Fibonacci numbers for `I-1` and `I-2`, while the
Fibonacci number of 0 and 1 are both defined to be 1. This can be
translated naturally into Prolog:

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

The complexity of executing this using SLD resolution however is `2^N`
and thus becomes prohibitively slow rather quickly, e.g., the execution
time for `N=30` is already 0.4 seconds. Using tabling, `fib(N,F)`

for each value of `N` is computed only once and the algorithm
becomes linear. Tabling effectively inverts the execution order for this
case: it suspends the final addition (F is F1+F2) until the two
preceeding Fibonacci numbers have been added to the answer tables. Thus,
we can reduce the complexity from the show-stopping `2^N` to
linear by adding a tabling directive and otherwise not changing the
algorithm. The code becomes:

:- use_module(library(tabling)). :- table fib/2. fib(0, 1) :- !. fib(1, 1) :- !. fib(N, F) :- N > 1, N1 is N-1, N2 is N-2, fib(N1, F1), fib(N2, F2), F is F1+F2.

The price that we pay is that a table `fib(I,F)`

is
created for each `I` in `0..N`. The execution time for `N=30`
is now 1 millisecond and computing the Fibonacci number for `N=1000`
is doable (output edited for readability).

1 ?- time(fib(1000, X)). % 52,991 inferences, 0.013 CPU in 0.013 seconds X = 70330367711422815821835254877183549770181269836358 73274260490508715453711819693357974224949456261173 34877504492417659910881863632654502236471060120533 74121273867339111198139373125598767690091902245245 323403501.

In the case of Fibonacci numbers we can still rather easily achieve
linear complexity using program transformation, where we use bottom-up
instead of top-down evaluation, i.e., we compute `fib(N,F)`

for growing `N`, where we pass the last two Fibonacci numbers
to the next iteration. Not having to create the tables and not having to
suspend and resume goals makes this implementation about 25 times faster
than the tabled one. However, even in this simple case the
transformation is not obvious and it is far more difficult to recognise
the algorithm as an implementation of Fibonacci numbers.

fib(0, 1) :- !. fib(1, 1) :- !. fib(N, F) :- fib(1,1,1,N,F). fib(_F, F1, N, N, F1) :- !. fib(F0, F1, I, N, F) :- F2 is F0+F1, I2 is I + 1, fib(F1, F2, I2, N, F).

Tag confusing pages with **doc-needs-help**|Tags are associated to your profile if you are logged in

Tags: