Out of local stack error in my program

[hecke]

Hey Guys, i have written the following program, that describes a lagged fibbonacci sequence, with
fib = 1, for 0<=n<2000 and
fib = fib(n-2000)+fib(n-1999), for n>=2000.

The problem:
When i call the programm (below) for a large "n", for example, for
n= 100000000000000 (in the code its X), prolog always returns "out of local stack". With a view in my code, is there a way to prevent that error? The modolu op is used, cause i want my solution modolued. Please do not make bad comments about the runtime of my program =D .
code:

:- dynamic fib/2.
fib(X,1) :- X>=0, X<2000,!.
fib(X,Y) :- X>=2000,!,
X1 is (X-2000),
fib(X1,Y1),
Y1 is Y1 mod 200000,
X2 is (X-1999),
fib(X2,Y2),
Y2 is Y2 mod 200000,
Y is ((Y1+Y2) mod 200000),
asserta( fib(X,Y) :- ! ).
user:
?- fib(10000000000000,Y).

Thank you helping !

 

[kahleen]

When X = 100000, X1 = 100000 - 2000 = 998000 and your code does the recursive call. So the first parameter of fib gets decreased by 2000 at each step, eventually getting in the [0, 2000) interval where the problem is solved. But to do that, you need to make the recursive call 50 times (100000 / 2000).

Now if X = 10^14, the recursive call is made 10^14 / (2*10^3) = 5 * 10^10. That is enough to bring you out of local stack. And don't forget that you have a second recursive call which is made for each of the 5 * 10^10 of the previous recursive calls.

The natural thing to do to prevent the out of local stack conclusion is to build your algorithm bottom-up instead of top-down.

I'll give you an example for the factorial algorithm:

Here is the top-down approach (factorial(N) is computed using factorial(N-1)):

top_down(1, 1) :- !.
top_down(N, F) :-
	N1 is N - 1,
	top_down(N1, F1),
	F is N * F1.

Here is the bottom-up approach (you start from 1 and multiply consecutive values to end up with the value of factorial(N)):

bottom_up(N, N, CurrentF, F) :-
	F is N * CurrentF.
bottom_up(N, X, CurrentF, F) :-
	X < N,
	X1 is X + 1,
	CurrentF1 is X * CurrentF,
	bottom_up(N, X1, CurrentF1, F).

You launch the second one: bottom_up(100, 1, 1, F) and get the value of F as the factorial of 100.

Now both of the above algorithms perform 100 recursive calls if N is 100. But for your fibonacci algorithm, things are different since the top-down algorithm makes 2 recursive calls at each step. The bottom-up approach will have pairs of consecutive values computed at each step and a single recursive call will be needed to advance to the next pair of consecutive numbers. You still have to do a lot of recursive calls for N = 10^14 and I, for one, don't think you will get a result for such a big N, but the bottom-up approach will certainly go for much higher values of N than the top-down approach