Beefy Boxes and Bandwidth Generously Provided by pair Networks
Problems? Is your data what you think it is?
 
PerlMonks  

fibonacci numbers using subroutine?

by derpp (Acolyte)
on Aug 19, 2010 at 22:44 UTC ( [id://856143]=perlquestion: print w/replies, xml ) Need Help??

derpp has asked for the wisdom of the Perl Monks concerning the following question:

Hi, monks.

Still a beginner at this stuff, so I need to borrow your wisdom. I to find the nth number of the fibonacci sequence using a subroutine. Problem is, I can already get it fine without a subroutine, and I can't figure out a way to get it with a subroutine without messing up my code. By the way, I don't know if I did this right.

use warnings; use strict; my $x = 0; my $y = 1; my $third = 0; my $count; print "Enter the number you would like to see in the sequence: "; my $number = <STDIN>; for ($count = 1; $count<=$number; $count++) { $third = $x + $y; $x = $y; $y = $third; } print $y;
Excuse my incorrect spacing. Thanks for the help! -- Update: Solved it (: Thanks for the suggestion, dasgar!

Replies are listed 'Best First'.
Re: fibonacci numbers using subroutine?
by dasgar (Priest) on Aug 19, 2010 at 22:56 UTC

    The way you described things, this sounds like a programming class assignment. As such, I don't want to do your homework for you. I apologize if I misread the intent behind your question.

    Anyways, you're about 90% there with your code anyways. Just put your for loop in a subroutine. Then all you need to do is pass values into and out of it. To learn more about using subroutines, I'd recommend checking out perldoc or the PerlMonks' tutorial on subroutines.

    I'm giving you generic information because you'll learn more this way as opposed to just giving you the code to do it. Try checking out those links and experiment with what you learn from them. If you're still struggling, just post your code along with your questions.

      Ah, yes. I guess it does sound like a class assignment. But this is just something I do for fun. Not much to do during summer vacation. Oh, and thanks for the suggestion. I'll try it out.
Re: fibonacci numbers using subroutine?
by FunkyMonk (Chancellor) on Aug 20, 2010 at 00:13 UTC
    For extra points, check out what Wikipedia has to say about Fibonacci numbers, and then implement a recursive1 solution.

    Recursion can lead to some wonderfully beautiful solutions to programming problems, but not always efficiently. Memoize can often increase their efficiency greatly, so take a look at that too.

    Post your solutions here for further comment, and enjoy your journey.

    Good luck

    ---
    [1] 30 years ago, when I was a student, one of the researchers told me about quicksort. He told me that to sort a list, I should split it in to two lists, sort each list, and repeat. That was when I recognised the beauty of recursion.

      30 years ago, when I was a student, one of the researchers told me about quicksort. He told me that to sort a list, I should split it in to two lists, sort each list, and repeat. That was when I recognised the beauty of recursion.
      While quicksort splits the list into two, as you describe it, it sound more like merge sort. The essence of quicksort is that you partition the list using a pivot element.
      Recursion can lead to some wonderfully beautiful solutions to programming problems, but not always efficiently. Memoize can often increase their efficiency greatly, so take a look at that too.
      I'd say that if memoizing your recursive function speeds it up significantly, it's likely there's a more efficient iterative solution.
Re: fibonacci numbers using subroutine?
by ikegami (Patriarch) on Aug 20, 2010 at 00:02 UTC
    Your program is aligned along the lines of
    1. Get input
    2. Calculate result
    3. Output result

    A sub is identical. It takes in inputs in the form of arguments, does something, and returns some outputs.

    You could move your entire code into a sub, but 1) you wouldn't learn anything, and 2) you want subs to do specific tasks, so you want to separate the keyboard input from the processing from displaying the result:

    use warnings; use strict; print "Enter the number you would like to see in the sequence: "; my $number = <STDIN>; print(fibonacci($number), "\n");

    Just move the rest into the sub, get the number from the argument list and return the result.

Re: fibonacci numbers using subroutine?
by Marshall (Canon) on Aug 20, 2010 at 05:28 UTC
    Ok, I'll bite... The fibonacci sequence is often used in CS classes as "the poster child against recursion" because the recursive algorithm is just so horrific in performance.

    Below I have coded both a non-recursive and a recursive algorithm in pretty much "run of the mill" implementations. They both produce the same results although the recursive algorithm is ridiculously slow.

    Sorry I didn't crank up the iterations far enough to get a meaningful result for the non-iterative version because if I did that, I'd have to go take a long nap waiting for the recursive version to finish! However, the benchmark below shows just how silly the comparison between the two is. "Un-comment" the print statements and crank down the iterations to verify output is the same.

    #!/usr/bin/perl -w use strict; use Benchmark; timethese (10, { Normal=> q{ foreach (20..25) { #print "number $_ : fibonacci ",fibonacci($_),"\n"; my $f = fibonacci($_); } }, Slow => q{ foreach (20..25) { #print "number $_ : fibonacci ",fibonacci_slow($_),"\n"; my $f = fibonacci_slow($_); } }, } ); =prints: Benchmark: timing 10 iterations of Normal, Slow... Normal: 0 wallclock secs ( 0.00 usr + 0.00 sys = 0.00 CPU) (warning: too few iterations for a reliable count) Slow: 7 wallclock secs ( 6.24 usr + 0.00 sys = 6.24 CPU) @ 1 +.60/s (n=10) =cut sub fibonacci { my $number = shift; my $curnum = 1; my $prevnum = 1; my $sum; if ($number ==1 || $number ==2){ return 1;} $number -= 2; while ($number--) { $sum = $curnum + $prevnum; $prevnum = $curnum; $curnum = $sum; } return $sum; } sub fibonacci_slow { my $number = shift; if ($number ==1 || $number ==2){ return 1;} return fibonacci_slow($number-1) + fibonacci_slow($number-2); }

      A simply memoised recursive fib will outstrip most iterative methods:

      sub fib_memo { state $memo = { 1 => 1, 2 => 1 }; return $memo->{ $_[0] } //= fib_memo( $_[0] - 1 ) + fib_memo( $_[0 +] - 2 ); }
        Interesting. I ran same benchmark as I'd run previously. Of course I cranked up the number of iterations and took the slow recursive version out of the mix otherwise I'd have time to go have a vacation in Mexico or something!

        For run #1, as more of an apples to apples deal, I flushed the cache after each subroutine call. The memoized version wound up about 1/2 the speed (1495/3478) of the iterative version which is a pretty impressive result considering how incredibly slow the non-memoized version is!

        Then for run #2, I commented out the line with the "flush" and let fib_memo do its best. Not surprisingly the iterative version stayed the same while the memoized version sped up (4130/3516).

        My curiosity is satisfied, but code is below if anybody wants to fiddle with it.

        #!/usr/bin/perl -w use strict; use Benchmark; use Memoize qw(flush_cache memoize); use feature "state"; memoize ('fib_memo'); timethese (10000, { Normal=> q{ foreach (20..25) { #print "number $_ : fibonacci ",fibonacci($_),"\n"; my $f = fibonacci($_); } }, # Slow => # q{ # foreach (20..25) # { # #print "number $_ : fibonacci ",fibonacci_slow($_),"\n"; # my $f = fibonacci_slow($_); # } # }, Memo => q{ foreach (20..25) { #print "number $_ : fibonacci ",fib_memo($_),"\n"; my $f = fib_memo($_); flush_cache('fib_memo'); } }, } ); =prints Benchmark: timing 10000 iterations of Memo, Normal... Memo: 7 wallclock secs ( 6.69 usr + 0.00 sys = 6.69 CPU) @ 14 +95.44/s (n=10000) Normal: 3 wallclock secs ( 2.88 usr + 0.00 sys = 2.88 CPU) @ 34 +78.26/s (n=10000) Just for fun...without flush_cache('fib_memo'); Benchmark: timing 10000 iterations of Memo, Normal... Memo: 2 wallclock secs ( 2.42 usr + 0.00 sys = 2.42 CPU) @ 41 +30.52/s (n=10000) Normal: 3 wallclock secs ( 2.84 usr + 0.00 sys = 2.84 CPU) @ 35 +16.17/s (n=10000) =cut sub fibonacci { my $number = shift; my $curnum = 1; my $prevnum = 1; my $sum; if ($number ==1 || $number ==2){ return 1;} $number -= 2; while ($number--) { $sum = $curnum + $prevnum; $prevnum = $curnum; $curnum = $sum; } return $sum; } sub fibonacci_slow { my $number = shift; if ($number ==1 || $number ==2){ return 1;} return fibonacci_slow($number-1) + fibonacci_slow($number-2); } sub fib_memo { state $memo = { 1 => 1, 2 => 1 }; return $memo->{ $_[0] } //= fib_memo( $_[0] - 1 ) + fib_memo( $_[0 +] - 2 ); }
      Memoize can help on the speed front :)
        I agree. Memoize can help a lot. Here's a little script that I use to get the 1000th, 2000th, 3000th number etc.
        #!/usr/bin/perl use strict; use warnings; use Math::Big qw/fibonacci/; use Memoize; memoize('fib', INSTALL => 'fastfib'); my $n = '1000'; print fib(), "\n"; sub fib { foreach ($n) { my @fibonacci = fibonacci($n); print "$fibonacci[$n-1]", "\n"; } }
Re: fibonacci numbers using subroutine?
by Anonymous Monk on Aug 19, 2010 at 23:05 UTC
    Problem is, I can already get it fine without a subroutine, and I can't figure out a way to get it with a subroutine without messing up my code.

    You are creating a recursive function so throw away your code, get a piece of paper, and write

    sub Fibonacci { my $n = shift; ... }
    then replace ... with an if/else structure that either returns a number, or adds the return value of a call to Fibonacci( $n ... ) ...it should follow closely the mathematical definition for Fibonacci number.

      I agree, recursive function follows better the mathematical definition and is easier to implement (no useless loop).

      Here is an example (if anyone is interested as derpp solved):

      sub fibonacci { my $n = shift; return undef if $n < 0; my $f; if ($n == 0) { $f = 0; } elsif ($n == 1) { $f = 1; } else { $f = fibonacci($n-1) + fibonacci($n-2); } return $f; } print fibonacci(25);
      Alessandro Ghedini <http://ghedini.co.cc>
        recursive function follows better the mathematical definition and is easier to implement (no useless loop).
        Fibonacci is a prime example why recursion can be very, very bad. For instance, your fibonacci(25) call results in 242785 calls to fibonacci. This doesn't scale.

        Even the most naïve loop implementation only execute its body 25 times. And it only takes two lines:

        my ($f, $fn) = (0, 1); ($f, $fn) = ($fn, $f + $fn) for 1 .. 25; print $f;
        And there's a formula that does the calculation in constant time.:
        my $PHI = (1 + sqrt(5)) / 2; Fibonnaci(N) = ($PHI ** $N - (1 - $PHI) ** $N) / sqrt(5);
        And since 1 < $PHI < 2, that can be written as:
        Fibonnaci(N) = int(0.5 + $PHI ** $N / sqrt(5))
        The only disadvantage the closed form has that for (on a 64 bit platform), for values > 84, the closed form suffers from rounding errors. But then, for values > 93, the result no longer fits in 64 bits integers, so precision is lost either way.

        † That assuming all arithmetic operations take constant time. This isn't quite true - it shuffles the size of the numbers under the carpet. There's a log(N) factor assumed (log(N) is the number of bits needed to store N).

Re: fibonacci numbers using subroutine?
by dHarry (Abbot) on Aug 20, 2010 at 08:24 UTC

    As you have nothing to do you might also want to take a look at Binet's formula to calculate Fibonacci numbers. See for example here or on wiki. It would be interesting to implement it and compare it to your solution. Fibonacci has been studied a lot and has many (surprising) applications like in trading (finance)!

      Fibonacci has been studied a lot and has many (surprising) applications like in trading (finance)!

      I don't suppose you have any references to those uses?

      Aside from those exploring the purely theoretical properties of Fib, does anyone use anything much beyond say fib(1000)?:

      4346655768693745643568852767504062580256466051737178040248172908953655 +541794905189040387984007925516929592259308032263477520968962323987332 +247116164299644090653318793829896964992851600370447613779516684922887 +5

      Examine what is said, not who speaks -- Silence betokens consent -- Love the truth but pardon error.
      "Science is about questioning the status quo. Questioning authority".
      In the absence of evidence, opinion is indistinguishable from prejudice.

        Not really, but the following list gives an idea: petals on a flower, leaves, branching plants, Fibonacci spiral (e.g. Cauliflour), Music, Phi (golden ratio), the human body, finance (mainly for traders, like for example retracement), etc. There several books on the application of Fibonacci. I think for most practical purposes the number is big enough!

Re: fibonacci numbers using subroutine?
by JavaFan (Canon) on Aug 20, 2010 at 08:25 UTC
    Easy. Just add two lines.
    use warnings; use strict; sub { my $x = 0; my $y = 1; my $third = 0; my $count; print "Enter the number you would like to see in the sequence: "; my $number = <STDIN>; for ($count = 1; $count<=$number; $count++) { $third = $x + $y; $x = $y; $y = $third; } print $y; }->();

      Just to show off, here's a Perl 6 solution:

      sub MAIN($limit as Int) { say (0, 1, *+* ... *)[$limit]; }

      Which you call as

      perl6 fib.pl 8

      To obtain the 8th fibonacci number.

      As an explanation, MAIN takes its arguments from the command line, and is run automatically at startup. as Int converts the command line argument (which is a string) to an integer (this is not sctrictly necessary). 0, 1, *+* ... * is a lazy, infinite list starting with 0 and 1, and then is built by summing the two previous elements. [$limit] takes the $limit's element of that list, with a zero-based index. (Which is why the fibonacci sequence starts with 0, 1 instead of 1, 1 in that program).

      Perl 6 - links to (nearly) everything that is Perl 6.
        In practice, though, if you're going to reuse a series in your Perl 6 program, you'll want to memoize the series by binding the series to an array, like this:
        my @fib := (0,1, *+* ... *); say @fib[8]; say @fib[9]; # doesn't recalculate fib(8)
        Both lists and arrays can be lazily infinite in Perl 6; the only real difference is whether the values are kept in an indexable form as they are generated. Note also that the memoization naturally uses an array rather than a hash in this case, which saves memory over those memoization techniques that must assume a hash for generality.
        Wait. Perl6 doesn't have OEIS() as a primitive? I can't just do OEIS(45)[8].say?
Re: fibonacci numbers using subroutine?
by nvivek (Vicar) on Aug 20, 2010 at 03:54 UTC

    You can easily do it in subroutine.If you don't understand the following code, you read about it.Subroutine is very useful for coding.It simplifies your program as well as it avoids the repetition of statements.

    print "Enter the number you would like to see in the sequence: "; my $number = <STDIN>; &fibonacci($number); #calling the subrounting fibonacci with passing g +iven number as argument sub fibonacci { my $a = 0; my $b = 1; # So now we see the parameter being used here. For clarity, I have w +ritten the for # loop using $n like the other examples. To set $n using the first p +arameter passed # to the subroutine, I access the scalar variable $_[0], which is th +e first element # of the parameter array @_ my $n = $_[0]; for (my $i=0;$i<$n;$i++){ #for loop to traverse and find the sum of +the value printf "%d\n", $a; my $sum = $a + $b; $a = $b; $b = $sum; } }

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others perusing the Monastery: (6)
As of 2024-03-29 14:26 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found