Fibonacci Series - Recursive or Iterative? Elegance or Speed?
Emerson Luís dos Santos
number on the Fibonacci Series. Of course that's a classical problem
which was already a lot discussed.
However, I wanted to write my own predicate without taking a look at
answers availables on books or on the Internet. So, please don't take
this message as a kind of challenge to beat my programs or something.
Actually, I'm trying to provide a discussion about approaches someone
could take in order to write a program to find the nth number on the
Fibonacci Series or the whole part of it up to N.
First of all, I wrote the following version to find the nth number of
the Series:
%fib_cons(+N, -F)
fib_cons(N, F) :-
N >= 0,
fib_cons(N, _, F).
fib_cons(0, 0, 1) :-
!.
fib_cons(N, F1, F) :-
N1 is N - 1,
fib_cons(N1, F2, F1),
F is F1 + F2.
This version is too bad as it generates a cons cell a step of
recursion.
Furthermore, I found it hard to figure out a similar version to find
the whole part of the series up to N. This is the best I could get:
%fibi_cons(+N, -Ni, -Fi)
fibi_cons(N, Ni, Fi) :-
N >= 0,
fibi_cons([N:F|NFs]),
member(Ni:Fi, [N:F|NFs]),
Ni \== nil.
fibi_cons([0:1, nil:0]) :-
!.
fibi_cons([N:F, N1:F1, N2:F2|NFs]) :-
N1 is N - 1,
fibi_cons([N1:F1, N2:F2|NFs]),
F is F1 + F2.
Recall I wanted to get the numbers by backtracking. I couldn't help
using lists as I could not figure out a way to get them by
backtracking without lists. Here is the first question: Is there a
way? If so, it's not any obvious for me.
The first improvement I applied to the first version was, of course,
removing the cons cell creation. Those lessons on "The Craft of
Prolog" (Richard O'Keefe) were great. Accumulator pairs were all that
I needed.
%fib_ap(+N, -F)
fib_ap(N, F) :-
N >= 0,
fib_ap(0, N, 0, 1, F).
fib_ap(N, N, _, F, F) :-
!.
fib_ap(N1, N, F2, F1, F) :-
N0 is N1 + 1,
F0 is F2 + F1,
fib_ap(N0, N, F1, F0, F).
This version looked so elegant to me that I easily wrote a similar
version to get all the numbers up to N by backtracking.
%fibi_ap(+N, -Ni, -Fi)
fibi_ap(N, Ni, Fi) :-
N >= 0,
fibi_ap(0, N, 0, 1, Ni, Fi).
fibi_ap(Ni, _, _, Fi, Ni, Fi).
fibi_ap(N1, N, F2, F1, Ni, Fi) :-
N1 < N,
N0 is N1 + 1,
F0 is F2 + F1,
fibi_ap(N0, N, F1, F0, Ni, Fi).
This is another argument in favour of elegance. An elegant solution is
more compatible with modifications and improvements. The accumulator
pairs versions were the most elegant I could get. They are also the
fastest. Local stack is no longer a big deal with these versions.
However, there is a version that used less memory on the global stack
than the previous one: an iterative version.
:-
dynamic fib_it/3.
%fib_it(+N, -Fi1)
fib_it(N, Fi1) :-
N >= 0,
assert(fib_it(0, 0, 1)),
repeat,
( retract(fib_it(Ni1, Fi2, Fi1)),
( Ni1 == N,
!
; Ni0 is Ni1 + 1,
Fi0 is Fi2 + Fi1,
assert(fib_it(Ni0, Fi1, Fi0)),
fail
)
).
This version is also trivially modifiable to get all the numbers up to
N.
:-
dynamic fibi_it/3.
%fibi_it(+N, -Ni, -Fi)
fibi_it(N, Ni, Fi) :-
N >= 0,
assert(fibi_it(0, 0, 1)),
repeat,
( retract(fibi_it(Ni, Fi0, Fi)),
( Ni == N,
!
; Ni1 is Ni + 1,
Fi1 is Fi0 + Fi,
assert(fibi_it(Ni1, Fi, Fi1))
)
).
However, there are some strong main issues not to take this version as
the best, at least for me:
1. This version is a bad example of the logical programming paradigm.
2. If the processing is stopped by a ^C-c, garbage is likely to remain
in memory, jeopardising further calls (catch might solve it).
3. The iterative programs are much slower than the previous versions.
4. Unless memory was extremely critical, I'd never use such a version
instead of an elegant Prolog one. Even if memory was fairly critical,
I'd still tend to use the recursive one.
I'd like to know opinions about each of the versions, as well as
repairs and/or best versions. I don't have any problem concerning the
Fibonacci Series; I just thought that might be a good way to discuss
different approaches when considering different issues. Furthermore,
it's a good way to learn.
I'm using SWI-Prolog 5.0.2.
Sorry if there ares bugs in the programs. I did not bother to test
them a lot.
I'm assuming the order of the clauses will be not changed.
Emerson
Daniel Dudley
news:eb210750.02031...@posting.google.com...
[snipped]
> This version is also trivially modifiable to get all the numbers
> up to N.
>
> :- dynamic fibi_it/3.
>
>
> fibi_it(N, Ni, Fi) :-
> N >= 0,
> assert(fibi_it(0, 0, 1)),
> repeat,
> ( retract(fibi_it(Ni, Fi0, Fi)),
> ( Ni == N,
> !
> ; Ni1 is Ni + 1,
> Fi1 is Fi0 + Fi,
> assert(fibi_it(Ni1, Fi, Fi1))
> )
> ).
>
> However, there are some strong main issues not to take this version as
> the best, at least for me:
>
> 1. This version is a bad example of the logical programming paradigm.
You'll get no argument to that statement here. How much weight you
place on the LP paradigm is your concern, but Prolog is not a pure
LP language, despite its acronym. Paul Singleton once called it an
assembly (as in building blocks) language, so prefix that with
"practical" and you get my definition of the language. Sometimes LP
is best (elegant, fast and/or efficient), sometimes not.
> 2. If the processing is stopped by a ^C-c, garbage is likely to
> remain in memory, jeopardising further calls (catch might solve it).
Hmmm, safety first is probably best.
> 3. The iterative programs are much slower than the previous versions.
That's because you're using the internal database. However, the
efficiency of the assert and retract predicates does vary a lot between
Prolog implementations; it's probably more noticeable on SWI-Prolog.
> 4. Unless memory was extremely critical, I'd never use such a version
> instead of an elegant Prolog one. Even if memory was fairly
> critical, I'd still tend to use the recursive one.
Don't give up so easily! All that's required are a few adjustments and
it'll be looking like this one:
/********************************************************************
File: FIBO.PL
Author: Daniel Dudley
Created: 1999.10.30
Purpose: Non-deterministic (iterative) Fibonacci series
********************************************************************/
% fibo_nd(+N,-Ni,-Fi)
% Eg. ?- fibo_nd(5,Ni,Fi). =>
% Ni = 0 , Fi = 1 ;
% Ni = Fi = 1 ;
% Ni = Fi = 2 ;
% Ni = Fi = 3 ;
% Ni = 4 , Fi = 5 ;
% Ni = 5 , Fi = 8 ;
% no
fibo_nd(N,Ni,Fi):-
fibo_nd(0,N,0,1,Ni,Fi).
% fibo_nd(+Ncurr,+Nmax,+Fprior,+Fcurr,-Ni,-Fi)
fibo_nd(N,_,_,F,N,F).
fibo_nd(N,Nmax,F0,F,Ni,Fi):-
N < Nmax,
N1 is N + 1,
F1 is F0 + F,
fibo_nd(N1,Nmax,F,F1,Ni,Fi).
% end program
I think you'll find this program both fast and efficient.
Daniel
Bart Demoen
> %fib_cons(+N, -F)
> fib_cons(N, F) :-
> N >= 0,
> fib_cons(N, _, F).
> fib_cons(0, 0, 1) :-
> !.
> fib_cons(N, F1, F) :-
> N1 is N - 1,
> fib_cons(N1, F2, F1),
> F is F1 + F2.
>
> This version is too bad as it generates a cons cell a step of
> recursion.
Usually, cons cell is related to the list constructor - but I see no
lists in you fib_cons - what did you mean ?
The problem with your fib_cons is: it is not tail-recursive and your
compiler does not know how to turn it into something tail-recursive.
> Furthermore, I found it hard to figure out a similar version to find
> the whole part of the series up to N. This is the best I could get:
>
...
> However, there is a version that used less memory on the global stack
> than the previous one: an iterative version.
>
Please ... your previous version (fibi_ap) was iterative and did not
use any global stack (unless it was interpreted). Your fib_it is a
failure-driven loop of the worst kind.
> 2. If the processing is stopped by a ^C-c, garbage is likely to remain
> in memory, jeopardising further calls (catch might solve it).
This depends on SWI's robustness - which is usually pretty good (and catch/3
would not solve it if it isn't in this case)
> 3. The iterative programs are much slower than the previous versions.
Once more: what you name iterative is not in the usual sense !
> 4. Unless memory was extremely critical, I'd never use such a version
> instead of an elegant Prolog one. Even if memory was fairly critical,
> I'd still tend to use the recursive one.
I am sure that your fibi_ap uses less memory than your fibi_it in any
decent implementation (*) - unless you declare the predicates involved as
dynamic, or are debugging it ...
(*) if not, you should complain bitterly to the maintainer of the
Prolog system
> fib_ap(N, N, _, F, F) :-
> !.
You are a fan of "The Craft of Prolog" (Richard O'Keefe), but you
missed steadfastness. You better write it as:
fib_ap(N, N, _, Fin, Fout) :-
!,
Fin = Fout.
Cheers
Bart Demoen
Emerson Luís dos Santos
> "Emerson Luís dos Santos" <eme...@ppgia.pucpr.br> wrote in message
> news:eb210750.02031...@posting.google.com...
> [snipped]
> > This version is also trivially modifiable to get all the numbers
> > up to N.
> >
> > :- dynamic fibi_it/3.
> >
> > % fibi_it(+N, -Ni, -Fi)
> >
> > fibi_it(N, Ni, Fi) :-
> > N >= 0,
> > assert(fibi_it(0, 0, 1)),
> > repeat,
> > ( retract(fibi_it(Ni, Fi0, Fi)),
> > ( Ni == N,
> > !
> > ; Ni1 is Ni + 1,
> > Fi1 is Fi0 + Fi,
> > assert(fibi_it(Ni1, Fi, Fi1))
> > )
> > ).
> >
> > However, there are some strong main issues not to take this version as
> > the best, at least for me:
> >
> > 1. This version is a bad example of the logical programming paradigm.
> You'll get no argument to that statement here.
Why not?
LP is based on declarative programming.
Dynamic database is not explicit all the time! It hurts the LP
paradigm in the sense that who reads the code does not see all the
sentences at a given time; furthermore, he cannot even know which
could be the sentences at a given time (not the case of this program).
> How much weight you
> place on the LP paradigm is your concern, but Prolog is not a pure
> LP language, despite its acronym. Paul Singleton once called it an
> assembly (as in building blocks) language, so prefix that with
> "practical" and you get my definition of the language. Sometimes LP
> is best (elegant, fast and/or efficient), sometimes not.
I didn't say you should not use dynamic database. I said it's _unwise_
to use it when u just don't need it. That's what I meant.
Dynamic database is a powerful and necessary mechanism. However, as a
different approach it brings different problems; it is not fault-free
if you don't guarantee it (faults such as a ^C-c or and external
modification of the database in a multithreaded version, for
instance).
> > 3. The iterative programs are much slower than the previous versions.
>
> That's because you're using the internal database. However, the
> efficiency of the assert and retract predicates does vary a lot between
> Prolog implementations; it's probably more noticeable on SWI-Prolog.
Hum??!!
I don't think it would make such a big difference just using another
kind of database modification instead of assert/retract. There's only
one clause caring for the counter at a time: so, querying the database
is fast. Furthermore, other kinds of database would still have to at
least copy terms. The problem is with dynamic manipulation.
Parameters passing is surely faster.
Are you sure u had paid enough attention to my message before posting
your answer?
This is almost exactly the same version i had provided with fibi_ap!!!
I had missed steadfastness, which was corrected by Bart Deomon, but
you missed the N >= 0 test besides that.
Emerson
Emerson Luís dos Santos
> Emerson Luís dos Santos wrote:
>
> > %fib_cons(+N, -F)
> > fib_cons(N, F) :-
> > N >= 0,
> > fib_cons(N, _, F).
> > fib_cons(0, 0, 1) :-
> > !.
> > fib_cons(N, F1, F) :-
> > N1 is N - 1,
> > fib_cons(N1, F2, F1),
> > F is F1 + F2.
> >
> > This version is too bad as it generates a cons cell a step of
> > recursion.
>
> Usually, cons cell is related to the list constructor - but I see no
> lists in you fib_cons - what did you mean ?
> The problem with your fib_cons is: it is not tail-recursive and your
> compiler does not know how to turn it into something tail-recursive.
Actually, it's stack frame, not cons cell. Sorry, that was a confusion
of terms.
But tail recursion is something you can do with your code. I have not
heard of a compiler that could do that; it would have to be quite
intelligent as it would have to _know_ how to program.
What compilers usually provide is last call optimisation.
Succintly, it changes the last form in a procedure body, if that form
is a recursive call, into a jump.
SWI-Prolog does provide it.
>
>
>
> > Furthermore, I found it hard to figure out a similar version to find
> > the whole part of the series up to N. This is the best I could get:
> >
>
> ...
>
> > However, there is a version that used less memory on the global stack
> > than the previous one: an iterative version.
> >
>
> Please ... your previous version (fibi_ap) was iterative and did not
> use any global stack (unless it was interpreted). Your fib_it is a
> failure-driven loop of the worst kind.
It was interpreted. I was testing issues, not trying to get a program.
As I said, Fibonacci Series is not interesting for me. However, I
thought it would behaves the same way when it was compiled. fibi_ap
was indeed iterative, but when you think about the steps. I was
thinking about modification of values.
I'll not use it that way anymore, though.
> > 2. If the processing is stopped by a ^C-c, garbage is likely to remain
> > in memory, jeopardising further calls (catch might solve it).
>
> This depends on SWI's robustness - which is usually pretty good (and catch/3
> would not solve it if it isn't in this case)
> > 4. Unless memory was extremely critical, I'd never use such a version
> > instead of an elegant Prolog one. Even if memory was fairly critical,
> > I'd still tend to use the recursive one.
>
> I am sure that your fibi_ap uses less memory than your fibi_it in any
> decent implementation (*) - unless you declare the predicates involved as
> dynamic, or are debugging it ...
they _were_ dynamic. The ":- dynamic" declaration was part of the code
I had posted. I was not debugging it, I was just using predicates to
measure time and memory; that must not be the right way to get what I
wanted, though. I'll check it. (SWI-Prolog is a great compiler. That
cannot remaing in doubt here.).
But using garbage collection, there's no reason to believe fibi_it
would waste memory.
I now agree fibi_ap does not waste memory too, and I must had got a
bad interpretation.
>
>
> > fib_ap(N, N, _, F, F) :-
> > !.
>
> You are a fan of "The Craft of Prolog" (Richard O'Keefe), but you
> missed steadfastness. You better write it as:
>
>
> fib_ap(N, N, _, Fin, Fout) :-
> !,
> Fin = Fout.
Great! I had not noticed that.
Emerson
Daniel Dudley
> "Daniel Dudley" <dud...@online.no> wrote in message
> news:<yD6m8.13660$eJ6.2...@news2.ulv.nextra.no>...
> > "Emerson Luís dos Santos" <eme...@ppgia.pucpr.br> wrote in message
> > news:eb210750.02031...@posting.google.com...
> > [snipped]
> > >
> > > 1. This version is a bad example of the logical programming
> > > paradigm.
>
> > You'll get no argument to that statement here.
>
> Why not?
> LP is based on declarative programming.
> Dynamic database is not explicit all the time! It hurts the LP
> paradigm in the sense that who reads the code does not see all the
> sentences at a given time; furthermore, he cannot even know which
> could be the sentences at a given time (not the case of this program).
As I said, you'll get no argument to that statement here -- meaning
that I am in agreement with you.
> > How much weight you
> > place on the LP paradigm is your concern, but Prolog is not a pure
> > LP language, despite its acronym. Paul Singleton once called it
> > an assembly (as in building blocks) language, so prefix that with
> > "practical" and you get my definition of the language. Sometimes
> > LP is best (elegant, fast and/or efficient), sometimes not.
>
> I didn't say you should not use dynamic database. I said it's
> _unwise_ to use it when u just don't need it. That's what I meant.
> Dynamic database is a powerful and necessary mechanism. However, as a
> different approach it brings different problems; it is not fault-free
> if you don't guarantee it (faults such as a ^C-c or and external
> modification of the database in a multithreaded version, for
> instance).
I didn't say you shouldn't use the dynamic database, either. You're
reading without digesting what has been said. Try again.
> > > 3. The iterative programs are much slower than the previous versions.
> >
> > That's because you're using the internal database. However, the
> > efficiency of the assert and retract predicates does vary a lot between
> > Prolog implementations; it's probably more noticeable on SWI-Prolog.
>
> Hum??!!
> I don't think it would make such a big difference just using another
> kind of database modification instead of . There's only
> one clause caring for the counter at a time: so, querying the database
> is fast. Furthermore, other kinds of database would still have to at
> least copy terms. The problem is with dynamic manipulation.
> Parameters passing is surely faster.
Sure it is. If you can do the job without using assert/retract, then
I suggest you do it.
> > > 4. Unless memory was extremely critical, I'd never use such a
> > > version instead of an elegant Prolog one. Even if memory was
> > > fairly critical, I'd still tend to use the recursive one.
> >
> > Don't give up so easily! All that's required are a few adjustments
> > and it'll be looking like this one:
[snipped]
> > I think you'll find this program both fast and efficient.
>
> Are you sure u had paid enough attention to my message before posting
> your answer?
Except for a little miss (see below), yes.
> This is almost exactly the same version i had provided with fibi_ap!!!
> I had missed steadfastness, which was corrected by Bart Deomon, but
> you missed the N >= 0 test besides that.
Well, yes, your fibi_ap is similar to fibo_nd. I missed that --
probably because fibi_ap/3 and fibi_ap/6 are all-in-one, and I
concentrated on answering your 4 issues concerning fibi_it. That's
frustrating for me because I spent time changing the variable names
in my original program to allow you to relate to the fact that few
adjustments are necessary to arrive at that solution. :-(
Having found that (best) solution yourself, I can only say: well done!
BTW, Bart's correction regarding steadfastness applies to fib_ap, not
fibi_ap, which relies on non-determinism to function correctly. A lot
of people have a hard time understanding exactly how predicates like
fibi_ap work, so it makes a good exercise to try to write the flow
logic down. Do let us know what you come up with. ;-)
Daniel
Bart Demoen
> I have not
> heard of a compiler that could do that; it would have to be quite
> intelligent as it would have to _know_ how to program.
Saumya Debray did some work on turning non-tail recursive predicates into tail-recursive ones.
Probably the reference is
Optimizing Almost-Tail-Recursive Prolog Programs.
Proceedings of the IFIP International Conference on Functional Programming
Languages and Computer Architecture, Nancy, France, Sept. 1985.
Springer-Verlag LNCS v. 201.
but it might have been a section in his PhD too.
Cheers
Bart Demoen
Fergus Henderson
>Emerson Luis dos Santos wrote:
>
>> I have not
>> heard of a compiler that could do that; it would have to be quite
>> intelligent as it would have to _know_ how to program.
>
>Saumya Debray did some work on turning non-tail recursive predicates into
>tail-recursive ones. Probably the reference is
>
>Optimizing Almost-Tail-Recursive Prolog Programs. [...]
See also the following:
"Making Mercury programs tail recursive",
Peter Ross, David Overton and Zoltan Somogyi.
Proceedings of the Ninth International Workshop on Logic-based
Program Synthesis and Transformation, Venice, Italy, September
1999. Lecture Notes in Computer Science, Springer Verlag.
Available via <http://www.cs.mu.oz.au/mercury/information/papers.html>.
This work has been incorporated into the Mercury compiler;
the optimization is enabled with the `--introduce-accumulators' option.
--
Fergus Henderson <f...@cs.mu.oz.au> | "I have always known that the pursuit
The University of Melbourne | of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
Emerson Luís dos Santos
> "Emerson Luís dos Santos" <eme...@ppgia.pucpr.br> wrote in message
> news:eb210750.02032...@posting.google.com...
> > "Daniel Dudley" <dud...@online.no> wrote in message
> > news:<yD6m8.13660$eJ6.2...@news2.ulv.nextra.no>...
> > > "Emerson Luís dos Santos" <eme...@ppgia.pucpr.br> wrote in message
> > > news:eb210750.02031...@posting.google.com...
> > > [snipped]
> > > > [snipped]
> > > >
> > > > 1. This version is a bad example of the logical programming
> > > > paradigm.
>
> > > You'll get no argument to that statement here.
> >
> > Why not?
> > LP is based on declarative programming.
> > Dynamic database is not explicit all the time! It hurts the LP
> > paradigm in the sense that who reads the code does not see all the
> > sentences at a given time; furthermore, he cannot even know which
> > could be the sentences at a given time (not the case of this program).
>
> As I said, you'll get no argument to that statement here -- meaning
> that I am in agreement with you.
I'm sorry. That's frustrating for me because I realized I'm still too
bad
at English. :(
I took "no argument to that" as "nothing to justify that".
:(
I'm also frustrated my restricted knowledge is in doubt because I
wrote the
program by myself. However, I agree
with you; I deserve that because I did not pay enough attention on
what I
wrote in the last message, burning my tongue.
It's clear fibi_ap does not need the correction. It just does a thing
fib_ap
cannot. Once it finds a solution, it looks for
others by walking deeper in the recursion to find them. As there is a
constraint
in the general case, it will never execute more steps than it must. If
the return argument is previously instantiated to a bad solution,
there will be no infinite loop because of the constraint in the
general case.
Fib_ap was not steadfastness because if the return argument was
previously
instantiated to a bad solution, the arguments in the base case would
not
match and the cut would not be reached. Thus, the choice point due to
the
general case would not be pruned away and the processing would go on
for
good as there is no constraint in the general case.
Emerson
Daniel Dudley
> "Daniel Dudley" <dud...@online.no> wrote in message
> news:<XJTm8.14974$eJ6.2...@news2.ulv.nextra.no>...
> > "Emerson Luís dos Santos" <eme...@ppgia.pucpr.br> wrote in message
> > news:eb210750.02032...@posting.google.com...
> > > "Daniel Dudley" <dud...@online.no> wrote in message
> > > news:<yD6m8.13660$eJ6.2...@news2.ulv.nextra.no>...
> > > > "Emerson Luís dos Santos" <eme...@ppgia.pucpr.br> wrote in message
> > > > news:eb210750.02031...@posting.google.com...
> > > > [snipped]
> > > > > [snipped]
> > BTW, Bart's correction regarding steadfastness applies to fib_ap, not
> > fibi_ap, which relies on non-determinism to function correctly.
>
Good, that got that point out of the way. :-)
> > A lot of people have a hard time understanding exactly how predicates
> > like fibi_ap work, so it makes a good exercise to try to write the
> > flow logic down. Do let us know what you come up with. ;-)
[snipped]
>
> It just does a thing fib_ap cannot. Once it finds a solution, it
> looks for others by walking deeper in the recursion to find them.
:-(
Yes, it looks for other solutions, but no, at any one time there is
only one level of recursion.
> As there is a constraint in the general case, it will never
> execute more steps than it must.
Correct.
> If the return argument is previously instantiated to
> a bad solution,
Think about it, can this really happen?
> there will be no infinite loop because of the constraint in the
> general case.
Yes, the predicate fails when the limit is reached, ie. the
constraint cannot be satisfied.
Well, unfortunately this wasn't quite the answer one expected. Here's
a repost (from Sept. 2000) of my description of the flow logic for
the non-deterministic for/3 predicate. You should have no difficulty
relating this to fibi_ap/6. Note that fibi_ap/3 may be considered as
a wrapper to hide the details of fibi_ap/6, which will function
perfectly without the wrapper.
% for(+Start,+Stop,-NumOut)
% Eg. ?- findall(N,for(4,7,N),Ns). =>
% N = _ , Ns = [4,5,6,7]
for(N,_,N).
for(Start,Stop,NumOut):-
Start < Stop,
Start1 is Start + 1,
for(Start1,Stop,NumOut).
The first call to the predicate succeeds with the first clause,
but it also leaves a choice point to the second clause.
Subsequent failure in the calling predicate causes backtracking
into the second clause, and the looping process (success on the
first clause and a new choice point on the second clause) is
re-invoked by the recursive last call. Repetition continues until
the 'stop' value has been reached. It's the first clause that
returns the current value (in the first call to the calling
predicate, in subsequent calls to the calling second clause). The
second clause (with each 'new' choice point) holds the current
value until it is backtracked into, upon which it is incremented
by the step value.
It therefore follows that one choice point will remain on predicate
completion if for/3 (or the like) is not allowed to fail on
completion. Since you'll probably not be running this loop just for
fun, you might consider cutting (!) this choice point away in
the calling predicate, eg. after testing that NumOut unifies with
Stop -- or another relevant test related to the iteration value(s),
or by wrapping the for/3 (or the like) call in an if-then construct
or collection predicate (findall, bagof, setof) before proceeding
with other calls (goals).
You should now compare this continuous "interaction" between the
calling predicate and the non-deterministic, iterative predicate
with the "closed" nature of a comparable recursive predicate. In
particular, the latter gives no room to break in on or break out
of the loop without hard coding it in that predicate. Hey, did I
just hear a cry of "Great" from the staunch LP'ers? I think I'll
abstain from commenting on that! ;-)
Daniel
Emerson Luís dos Santos
> "Emerson Luís dos Santos" <eme...@ppgia.pucpr.br> wrote in message
> news:eb210750.0203...@posting.google.com...
> > "Daniel Dudley" <dud...@online.no> wrote in message
> > news:<XJTm8.14974$eJ6.2...@news2.ulv.nextra.no>...
> > > "Emerson Luís dos Santos" <eme...@ppgia.pucpr.br> wrote in message
> > > news:eb210750.02032...@posting.google.com...
> > > > "Daniel Dudley" <dud...@online.no> wrote in message
> > > > news:<yD6m8.13660$eJ6.2...@news2.ulv.nextra.no>...
> > > > > "Emerson Luís dos Santos" <eme...@ppgia.pucpr.br> wrote in message
> > > > > news:eb210750.02031...@posting.google.com...
> > > > > [snipped]
> > > > > > [snipped]
> [snipped]
> > > A lot of people have a hard time understanding exactly how predicates
> > > like fibi_ap work, so it makes a good exercise to try to write the
> > > flow logic down. Do let us know what you come up with. ;-)
> [snipped]
> >
> > It just does a thing fib_ap cannot. Once it finds a solution, it
> > looks for others by walking deeper in the recursion to find them.
>
> :-(
> Yes, it looks for other solutions, but no, at any one time there is
> only one level of recursion.
By walking deeper in the recursion I meant the new procedure call at
each step in the general case; maybe I didn't use the usual term.
> > If the return argument is previously instantiated to
> > a bad solution,
>
> Think about it, can this really happen?
This is a regular call, for me:
?- fibi_ap(4, Ni, Fi).
Ni = 0
Fi = 1 ;
Ni = 1
Fi = 1 ;
Ni = 2
Fi = 2 ;
Ni = 3
Fi = 3 ;
Ni = 4
Fi = 5 ;
No
And these are bad calls (with return arguments previously instantiated
to
bad solutions):
?- fibi_ap(4, 5, Fi).
No
?- fibi_ap(4, Ni, 4).
No
?- fibi_ap(4, 5, 4).
No
I really don't understand. I don't understand what made you think
I needed to give such a detailed description for a predicate I had
written by
myself. The new things for me were the remark about a cut (which I
hadn't
noticed) and the good use of English.
I need to improve my knowledge of English. :)
As a matter of information, there's an alternative way of finding the
first
N Fibonacci numbers described in The Craft of Prolog, in the section
about
recurrences. I've just taken a look at the book to check for any
comments about the Fibonaccci Series and I found it interesting.
Emerson
Daniel Dudley
news:eb210750.02032...@posting.google.com...
> I really don't understand. I don't understand what made you think
> I needed to give such a detailed description for a predicate I had
> written by myself. The new things for me were the remark about a
The fact that you'd written the predicate yourself doesn't
necessarily mean that you have understood its workings. Perhaps
you'd have caught the necessity for a cut (or wrapper) if you'd
done a detailed analysis of the workings of fibi_ap? That's why
I said it makes a good exercise to do so.
But really, I'm sorry to have wasted both your and my time. :-(
Daniel
Jamie Andrews
in Prolog programs in order to understand the logical basis of a
program. This is a point that Richard O'Keefe used to make here
a lot. I think the only problem with the previous versions we
saw here was that the predicates were named obscurely and not
really commented, and were therefore difficult to interpret as
anything but "tricks". Here is another version.
% fib(N, F): F is the Nth Fibonacci number.
fib(1, 1).
fib(N, F) :-
N > 1,
N2 is N-2,
fib_given_prev(N2, 1, 1, F).
% fib_given_prev(N, F1, F2, F): Given that F1 and F2 are two
% Fibonacci numbers which are one after the other in the
% sequence, F is the Nth Fibonacci number after them.
fib_given_prev(0, F1, F2, F2).
fib_given_prev(N, F1, F2, F) :-
N > 0,
NextF is F1+F2,
N1 is N-1,
fib_given_prev(N1, F2, NextF, F).
This is tail-recursive and makes perfect sense if we interpret
the predicates logically, as described. We can make it slightly
more efficient by introducing (steadfast) cuts into the first
clause of each predicate and omitting the ">" tests. However,
this makes it a bit more difficult to understand logically, and
doesn't properly handle N being 0 or negative.
--Jamie. (nel mezzo del cammin di nostra vita)
andrews .uwo } Merge these two lines to obtain my e-mail address.
@csd .ca } (Unsolicited "bulk" e-mail costs everyone.)
Daniel Dudley
news:a7vdj4$510$1...@panther.uwo.ca...
> In my opinion, predicate naming and commenting is crucial
> in Prolog programs in order to understand the logical basis of a
> program. This is a point that Richard O'Keefe used to make here
> a lot. I think the only problem with the previous versions we
> saw here was that the predicates were named obscurely and not
> really commented, and were therefore difficult to interpret as
> anything but "tricks".
Hmm, "tricks", eh? That's probably stretching it, Jamie. I do
agree with (a generalization of) your comments, though. Of course,
you did notice after you posted your message that you are at fault
for not denoting variable flow patterns (often called modes). ;-)
> Here is another version.
>
> % fib(N, F): F is the Nth Fibonacci number.
> fib(1, 1).
> fib(N, F) :-
> N > 1,
> N2 is N-2,
> fib_given_prev(N2, 1, 1, F).
>
> % fib_given_prev(N, F1, F2, F): Given that F1 and F2 are two
> % Fibonacci numbers which are one after the other in the
> % sequence, F is the Nth Fibonacci number after them.
> fib_given_prev(0, F1, F2, F2).
> fib_given_prev(N, F1, F2, F) :-
> N > 0,
> NextF is F1+F2,
> N1 is N-1,
> fib_given_prev(N1, F2, NextF, F).
>
> This is tail-recursive and makes perfect sense if we interpret
> the predicates logically, as described. We can make it slightly
> more efficient by introducing (steadfast) cuts into the first
> clause of each predicate and omitting the ">" tests. However,
> this makes it a bit more difficult to understand logically, and
> doesn't properly handle N being 0 or negative.
Yes, this one's ok too -- as an exercise in Prolog programming.
However, all the programs given in this thread are only of practical
interest for small values of N, or for returning the Fibonacci
sequence up to and including N; they are inefficient when the Nth
Fibonacci number alone is of interest. Here's an alternative the
mathematicians among the readers might find useful (and practical):
/********************************************************************
File: BINET.PL
Author: Daniel Dudley
Created: 1999.11.12 (Win-Prolog version)
Purpose: Compute the nth Fibonacci number using the Binet formula
Modified: 2001.5.02 (DLD) - to ECLiPSe (uses big number library)
********************************************************************/
% binet(+N,-F) is true if F is the Nth Fibonacci number
% Eg. ?- binet(100, F). =>
% F = 354224848179263111168
% Yes (0.00s cpu)
% ?- binet(1000, F).
% F = 4346655768693891486263750038675501401095838890172
% 5051132915256476112292920052539720295234060457458
% 0578007320250861309759987169770518391682424838140
% 6280528331182105132727351805088207566265953452337
% 0463746326528
% Yes (0.00s cpu)
binet(N,F):-
SqRtOf5 is sqrt(5),
F is fix((1 / SqRtOf5) *
((((1 + SqRtOf5) / 2)^N) -
(((1 - SqRtOf5) / 2)^N) +
0.5
)
).
% end of binet/2
If anyone is interested in the Win-Prolog version of this program,
I'll post it here.
Daniel
Martin Jansche
On Fri, 29 Mar 2002, Daniel Dudley wrote:
> binet(N,F):-
> SqRtOf5 is sqrt(5),
> F is fix((1 / SqRtOf5) *
> ((((1 + SqRtOf5) / 2)^N) -
> (((1 - SqRtOf5) / 2)^N) +
> 0.5
> )
> ).
Why not simply
fib(X, Fib_X) :-
Sqrt_5 is sqrt(5),
Fib_X is round((((1+Sqrt_5)/2)**X) / Sqrt_5).
?
- martin
Fergus Henderson
>"Jamie Andrews" wrote in message
>> Here is another version.
...
>Yes, this one's ok too -- as an exercise in Prolog programming.
>However, all the programs given in this thread are only of practical
>interest for small values of N, or for returning the Fibonacci
>sequence up to and including N; they are inefficient when the Nth
>Fibonacci number alone is of interest. Here's an alternative the
>mathematicians among the readers might find useful (and practical):
>
>/********************************************************************
>
>File: BINET.PL
>Author: Daniel Dudley
>Created: 1999.11.12 (Win-Prolog version)
>Purpose: Compute the nth Fibonacci number using the Binet formula
>Modified: 2001.5.02 (DLD) - to ECLiPSe (uses big number library)
>
>********************************************************************/
>
>% binet(+N,-F) is true if F is the Nth Fibonacci number
>% Eg. ?- binet(100, F). =>
>% F = 354224848179263111168
>% Yes (0.00s cpu)
>% ?- binet(1000, F).
>% F = 4346655768693891486263750038675501401095838890172
>% 5051132915256476112292920052539720295234060457458
>% 0578007320250861309759987169770518391682424838140
>% 6280528331182105132727351805088207566265953452337
>% 0463746326528
>% Yes (0.00s cpu)
This answer may be fast, but it is unfortunately not correct.
Only the first 13 digits of that answer are right. The correct
value of the 1000th fibonacci number is
434665576869374564356885276750406258025646605173717804024817
290895365554179490518904038798400792551692959225930803226347
752096896232398733224711616429964409065331879382989696499285
16003704476137795166849228875
Using floating point to calculate Fibonacci numbers only produces
correct answers for small values of N (e.g. N =< 78, with IEEE
double-precision floating point). If you want an accurate compuation
of the Nth Fibonacci number for large values of N, you need to use
arbitrary-precision arithmetic.
Andrew Bromage
"Daniel Dudley" <dud...@online.no> writes:
>Yes, this one's ok too -- as an exercise in Prolog programming.
>However, all the programs given in this thread are only of practical
>interest for small values of N, or for returning the Fibonacci
>sequence up to and including N; they are inefficient when the Nth
>Fibonacci number alone is of interest. Here's an alternative the
>mathematicians among the readers might find useful (and practical):
As Fergus has pointed out, the "binet" algorithm is not practical for
anything but small values of N when using IEEE floating point arithmetic.
A better approach, which takes O(log N) time and uses only (arbitrary
precision) integer arithmetic is the matrix algorithm:
%
% WARNING! Untested code follows...
%
fib(N, FibN) :-
( N =< 0 ->
FibN = 0
;
m4pow(m(1, 1, 1, 0), N, m(FibN, _, _, _))
).
% 2x2 matrix multiply
m4mult(m(A1,B1,C1,D1), m(A2, B2, C2, D2), m(A, B, C, D)) :-
A is A1*A2 + B1*C2,
B is A1*B2 + B1*D2,
C is C1*A2 + D1*C2,
D is C1*B2 + D1*D2.
% Raise the matrix M to the power of N
m4pow(M, N, MpowN) :-
( N = 0 ->
MpowN = m(1, 0, 0, 1)
;
N2 is N div 2,
m4pow(M, N2, M2),
m4mult(M2, M2, M22),
( 0 is N mod 2 ->
MpowN = M22
;
m4mult(M, M22, MpowN)
)
).
Basically, you raise this matrix to the power of N:
[ 1 1 ]
[ 1 0 ]
When you've done that, the top left-hand entry in the matrix will be
the Nth Fibonacci number.
This should be practical for any purpose except for producing a lot
of large Fibonacci numbers. If you need to do that, compute two
sequential numbers using the matrix algorithm and then use that to seed
the iterative algorithm.
Cheers,
Andrew Bromage
hawkaccess
fib(N, Fib):-
set_prolog_flag(epsilon, -24),
Sqrt5 is sqrt(5),
Fib is round((((1+Sqrt5)/2)**N)/Sqrt5).
Amzi! Prolog Listener
Prolog Version: 6.1.70 debugging Windows
Apr 1 2002 13:47:49
Copyright (c) 1992-2002 Amzi! inc. All Rights Reserved.
Type 'quit.' to exit
?- [fib].
yes
?- fugit(fib(1000,X)).
0.02 seconds
X =
4346655768693745643568852767504062580256466051737178040248172908953655541794
9051890403879840079255169295922593080322634775209689623239873322471161642996
4409
06533187938298969649928516003704476137795166849228875.0
yes
?-
Ray Reeves
Joachim Schimpf
>
> fib(N, Fib):-
> set_prolog_flag(epsilon, -24),
> Sqrt5 is sqrt(5),
> Fib is round((((1+Sqrt5)/2)**N)/Sqrt5).
Cute :-)
In ECLiPSe, you can use rational arithmetic,
plus a good enough approximation of sqrt(5):
fib(N, Fib):-
approx_sqrt(5, 9, Sqrt5),
Fib is fix((((1+Sqrt5)/2)^N)/Sqrt5).
% compute a rational approximation of the square root
approx_sqrt(X, Iter, R) :-
approx_sqrt(X, 1_1, Iter, R).
approx_sqrt(X, G, Iter, R) :-
NG is G - (G^2-X) / (2*G),
( Iter < 1 ->
R = NG
;
Iter1 is Iter-1,
approx_sqrt(X, NG, Iter1, R)
).
?- fib(1000,F).
F =
43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
Yes (6.70s cpu)
--
Joachim Schimpf / phone: +44 20 7594 8187
IC-Parc, Imperial College / mailto:J.Sc...@ic.ac.uk
London SW7 2AZ, UK / http://www.icparc.ic.ac.uk/eclipse
Daniel Dudley
news:3CAAE8D1...@icparc.ic.ac.uk...
> hawkaccess wrote:
> >
> > fib(N, Fib):-
> > set_prolog_flag(epsilon, -24),
> > Sqrt5 is sqrt(5),
> > Fib is round((((1+Sqrt5)/2)**N)/Sqrt5).
>
> Cute :-)
I suppose your smiley means that you caught Ray's April
Fool's joke, Joachim. (For those that didn't: Amzi!
doesn't have a documented round/1 function, and you can
rack your brains out trying to guess what fugit/1 does.)
> In ECLiPSe, you can use rational arithmetic,
> plus a good enough approximation of sqrt(5):
>
> fib(N, Fib):-
> approx_sqrt(5, 9, Sqrt5),
> Fib is fix((((1+Sqrt5)/2)^N)/Sqrt5).
>
>
> % compute a rational approximation of the square root
> approx_sqrt(X, Iter, R) :-
> approx_sqrt(X, 1_1, Iter, R).
>
> approx_sqrt(X, G, Iter, R) :-
> NG is G - (G^2-X) / (2*G),
> ( Iter < 1 ->
> R = NG
> ;
> Iter1 is Iter-1,
> approx_sqrt(X, NG, Iter1, R)
> ).
>
>
> ?- fib(1000,F).
>
> F =
> 43466557686937456[snipped]849228875
> Yes (6.70s cpu)
On a Win2K platform (PII 400 MHz, 256 Kb RAM) it takes an
amazing 58 seconds, Joachim! Since fibo_nd(1000,F) returns
the same result in 0.00s, this solution is useful only with
much, much, much higher values of N than 1000. It can be
bettered. Andrew Bromage's Fibonacci Q-matrix solution is
also interesting -- when you get it to work correctly.
Daniel
Andrew Bromage
"Daniel Dudley" <dud...@online.no> writes:
> Andrew Bromage's Fibonacci Q-matrix solution is
>also interesting -- when you get it to work correctly.
On that:
If anyone wants my original (tested) Haskell version, rather than
the hand-translated-and-untested Prolog version, email and I can
send it to you. (I hesitate posting Haskell code on c.l.p.)
Cheers,
Andrew Bromage
Joachim Schimpf
>
> > ?- fib(1000,F).
> >
> > F =
> > 43466557686937456[snipped]849228875
> > Yes (6.70s cpu)
>
> On a Win2K platform (PII 400 MHz, 256 Kb RAM) it takes an
> amazing 58 seconds, Joachim!
Yes, I know... It's probably because rational exponentiation is
implemented rather naively by repeated squaring and multiplying.
That can take a while when your rationals have a few thousand
digits...
Daniel Dudley
news:a8geap$17...@goaway.cc.monash.edu.au...
Isn't Haskell a LP language? If so, post it, Andrew.
Daniel
hawkaccess
> "Joachim Schimpf" <j.sc...@icparc.ic.ac.uk> wrote in message
> news:3CAAE8D1...@icparc.ic.ac.uk...
> > hawkaccess wrote:
> > >
> > > fib(N, Fib):-
> > > set_prolog_flag(epsilon, -24),
> > > Sqrt5 is sqrt(5),
> > > Fib is round((((1+Sqrt5)/2)**N)/Sqrt5).
> >
> > Cute :-)
>
> I suppose your smiley means that you caught Ray's April
> Fool's joke, Joachim. (For those that didn't: Amzi!
> doesn't have a documented round/1 function, and you can
> rack your brains out trying to guess what fugit/1 does.)
It worked correctly, though, didn't it? And in a respectable 20mS
interpreted.
Some minds are more easily racked!
Ray Reeves
Daniel Dudley
news:a8hpnr$3ta$1...@news.chatlink.com...
I've no idea whether it worked or not. Why (apparently) waste
time on poorly documented code, which cannot be authenticated
in the Amzi! documentation.
> Some minds are more easily racked!
Hmm, not when it appears to be a joke. If you want it to be
taken seriously, Ray, I'd humbly suggest that you get your
documentation in order!
Daniel
Andrew Bromage
"Daniel Dudley" <dud...@online.no> writes:
>Isn't Haskell a LP language?
No.
>If so, post it, Andrew.
http://andrew.bromage.org/Fib.hs
Cheers,
Andrew Bromage