Re: calculating fibonacci[was: encryption]

On Sun, 14 Dec 2008 22:14:41 +0000, Ben Bacarisse
<ben.usenet@xxxxxxxxx> wrote:

cri@xxxxxxxx (Richard Harter) writes:

On Sun, 14 Dec 2008 14:03:35 +0000, Ben Bacarisse
<ben.usenet@xxxxxxxxx> wrote:


"Elegant" is a bit of an over statement - it is elegant given the
constraints of using the simple addition formula, using
recursion, using a functional language, and the criterion of
having compact code. Under the hood it creates a list of 1000
values that is not needed in the obvious iterative solution.

I submit that an elegant recursive solution is a simple, compact
implementation that does not require O(n) additional storage;
i.e., a solution that requires O(1) additional storage given tail
recursion. Take it as a challenge.

I don't see any need for this algorithm to use more than O(1) space
unless, of course, some other part of the program causes the list to
be stored for other purposes. In other words, it seems quite likely
that

fib n = fibs !! n
where fibs = 1 : 1 : map (uncurry (+)) (zip fibs (tail fibs))

may be enough. (Even the top-level definition need not cause the list
to stored if the compiler can prove that there are no other
references to it.)

I dare say you are right about O(1) storage; that's the sort of
thing that clever compilers optimize. Still, it's a very
roundabout sort of approach. In effect a simulated array is
being created with the proviso that the compiler can be counted
upon to generate code that will discard the unneeded low order
part of the array during the course of execution. It's rather
like scratching your nose with both hands tied behind your back.

Or so it seems to me. If one is going to do the iterative
version in disguise, one might as well do the tuple hack, e.g.,

fib n = hack n 1 1
where hack n a b = n==1:a | hack (n-1) b a+b

with suitable syntax mods for the language of choice.


At least one functional language implementation I know well (not
Haskell but SASL) would have made a circular structure from that where
definition and iterating to find fibs !! n would have caused the cons
cells to become unreferenced immediately. It would have been possible
to run this code with a tiny heap -- the collector would then run for
every new fib but the overall space would be bounded.

I may be misremembering, and ghc[1] may not have this property, though
I would never bet against the ingenuity of its implementers. I now
have an excuse to go see how to profile Haskell code...

[1] The Glasgow Haskell Compiler.

--
Ben.

Richard Harter, cri@xxxxxxxx
http://home.tiac.net/~cri, http://www.varinoma.com
Save the Earth now!!
It's the only planet with chocolate.
.

Relevant Pages

  • Re: newbie question : summing elements in a list
    ... > I am beginner at lisp and I can do it in the classical way with do... ... I mention this because it's a subjective judgment that 'do' is not elegant. ... but please understand that 'recursion' and 'elegance' are not synonymous, ... Recursive solutions can use stack and you can run out of stack. ...
    (comp.lang.lisp)
  • Re: calculating fibonacci[was: encryption]
    ... version in disguise, one might as well do the tuple hack, e.g., ... simply as an example of a recursive fib definition that did not ... If we want to compute yusing recursion the code needs to be ...
    (comp.programming)
  • Re: Fibonacci series...please help!!!
    ... you must be aware that the recursion can very quickly cause ... means that when function Fib is used, it calls it self twice. ... second place the number of invocations grows more like phi**n, ...
    (comp.lang.fortran)
  • Re: Towers of Hanoi
    ... the way won't help you with the recursion. ... changing the base case to 0 might make it more concise or ... elegant. ... Prev by Date: ...
    (comp.lang.scheme)
  • Re: File::Glob - can it recurse?
    ... > I'd like to use the perl chowncommand so I tried this: ... One of the nice things about the glob() function is that it can ... and now you have recursion that's five levels deep. ... Like I said, this isn't really all that elegant of a solution, ...
    (comp.lang.perl.misc)