Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
PerlMonks  

Re: Fibonacci Numbers

by jweed (Chaplain)
on Feb 10, 2005 at 02:28 UTC ( [id://429569]=note: print w/replies, xml ) Need Help??


in reply to Fibonacci Numbers

2 things:
If you stick with the original form of your answer (a recurrance-based one), try Memoizing it, viz.:
# Compute Fibonacci numbers, straight from Memoize docs use Memoize; memoize('fib'); sub fib { my $n = shift; return $n if $n < 2; fib($n-1) + fib($n-2); } my $foo = fib(24);
Such a strategy stores the results of previous iterations for later use, so you only have to calculate each result once. Once you do, it's stored (behind the scenes) in a hash which reconstructs it on demand. This makes things much faster.

But more importantly, I would offer this verson of an answer as a possible contender. It's a one-liner, but of a different style:
sub fib{int(((((1+sqrt(5))/2)**$_[0])/sqrt(5))+.5)}
enjoy!



Code is (almost) always untested.
http://www.justicepoetic.net/

Replies are listed 'Best First'.
Re^2: Fibonacci Numbers
by crashtest (Curate) on Feb 10, 2005 at 07:29 UTC
    Sweet! The Binet Formula! This Mathworld entry shows how the Fibonacci sequence, the Binet Forms and the Golden Ratio fit together.

    For all the times the Fibonacci sequence comes up as an exercise in programming recursion, I've never seen it solved quite like that. Goes to show that TIMTOWTDI, as usual.
Re^2: Fibonacci Numbers
by blazar (Canon) on Feb 10, 2005 at 08:23 UTC
    If you stick with the original form of your answer (a recurrance-based one), try Memoizing it, viz.:
    But the original form of his answer was not recursive:
    sub fib{ ($val0, $val1) =@_; $sum= $val0 + $val1; }
      Honourable friar, Am I wrong to think that recurrsion is utilized by passing the value of $sum as computed by sub fib back into sub fib? Otherwise, the binet formula is extremely cool. Thanks.
        This is a recursive way to do it but it gets slow quickly for larger values unless you memoze it.
        print "$_ : ", fibo($_), "\n" for 0..23; sub fibo{ my $n = shift; if ( $n == 0){ return 0;} elsif( $n == 1){ return 1;} else { return fibo($n-1) + fibo($n-2);} }
        It is iterative. It is not recursive in that fib() does not call itself.

        FWIW I think that Binet's formula is cool too.

Re^2: Fibonacci Numbers
by ihb (Deacon) on Feb 10, 2005 at 23:49 UTC

    Not that it matters much to me, but for the 71st number I get a round-off error using Binet's formula.

    sub fib {int(((((1+sqrt(5))/2)**$_[0])/sqrt(5))+.5)} sub fib2 { my ($n) = @_; my ($x, $y) = (1, 1); ($x, $y) = ($y, $x + $y) for 3 .. $n; return $y; } for (my $n = 1; 1; $n++) { my ($x, $y) = (fib($n), fib2($n)); if ($x != $y) { print "$n: $x $y"; last; } } __END__ 71: 308061521170130 308061521170129

    Regards,
    ihb

    See perltoc if you don't know which perldoc to read!

      Try Math::BigFloat's rounding handling instead of the int(foo+.5) trick, and things should work out.



      Code is (almost) always untested.
      http://www.justicepoetic.net/

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: note [id://429569]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this?Last hourOther CB clients
Other Users?
Others having a coffee break in the Monastery: (4)
As of 2024-03-28 08:10 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found