Beefy Boxes and Bandwidth Generously Provided by pair Networks
go ahead... be a heretic

Fibonacci numbers

by Anonymous Monk
on Oct 02, 2001 at 00:50 UTC ( [id://115972] : perlquestion . print w/replies, xml ) Need Help??

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

This node falls below the community's threshold of quality. You may see it by logging in.

Replies are listed 'Best First'.
Re: Fibonacci numbers
by suaveant (Parson) on Oct 02, 2001 at 00:59 UTC
    $i = 1; print "$i,"; print($i++,',') for(;;);
    This will generate the fibonacci numbers... (and a few others), the professor can sort them out :)

                    - Ant
                    - Some of my best work - Fish Dinner

Re: Fibonacci numbers
by jeroenes (Priest) on Oct 02, 2001 at 00:54 UTC

      I agree with jeroenes. This is very possible to do.

        Yes, it is. To reduce the problem size, the following program is likely to eventually print out any Fibonacci numbers between 0 and N-1, where N is the command line argument. In order, even. However, you must find them buried in all the other numbers, and it will take an indeterminate amount of time. It will not stop upon hitting a sequence of fibonacci numbers. (Hint: The output is random.)
        #!/usr/bin/perl -w use strict;my$N=$_[0];$\=' ';for (;;){print int rand$N}
Re: Fibonacci numbers
by runrig (Abbot) on Oct 02, 2001 at 01:18 UTC
    Can anybody make a program to generate Fibonacci numbers

    Well, no I don't think anybody can do it. I had trouble getting my daughter to write just a 'hello world' program. But you might be able to do it by just writing a program that generates a sequence that follows these rules:

    i0=0, i1=1, in, n>=2=in-1+in-2

(jeffa) Re: Fibonacci numbers
by jeffa (Bishop) on Oct 02, 2001 at 00:58 UTC
Re: Fibonacci numbers
by demerphq (Chancellor) on Oct 02, 2001 at 01:07 UTC
    If you watch rabbits breed long enough the solution will come to you.

    You are not ready to use symrefs unless you already know why they are bad. -- tadmc (CLPM)

Re: Fibonacci numbers
by petdance (Parson) on Oct 02, 2001 at 05:25 UTC
    Based on your description of the problem, I think this should work just fine:
    print "1,1,2,3,5,8,13,21,...\n";
    If you want something that "does more", try this:
    print join( ",", qw( 1 1 2 3 5 8 13 21 ... ) );

    <megaphone> Throw down the gun and tiara and come out of the float! </megaphone>

Re (tilly) 1: Fibonacci numbers
by tilly (Archbishop) on Oct 02, 2001 at 01:48 UTC
    The answers in the thread RE (tilly) 1: Fibonnaci all are programs that do what you want.

    I would advise against using them if you can't explain on demand how they work.

Re: Fibonacci numbers
by chromatic (Archbishop) on Oct 02, 2001 at 03:16 UTC
    Do you know LISP? It's pretty easy to translate into Perl:
    #!/usr/bin/perl -w use strict; *prev = sub { my $a = $_[0] || 0; sub { $a }; }; *fib = sub { ($a, $b) = ($_[0] + $_[1]->(), $_[0]); printf "%d$/", $a; $_ = sub { fib( $a, prev($b) ) }; }; print "$_$/" for ++$|; fib(1, prev(0)); for my $var (1 .. shift || 10) { $_->(); }
    Alright, that's not necessary *good* LISP, but you should have no trouble deciphering the algorithm without extraneous parenthesis. ©
Re: Fibonacci numbers
by miyagawa (Chaplain) on Oct 02, 2001 at 05:46 UTC
Re: Fibonacci numbers
by saiful (Novice) on Oct 02, 2001 at 14:22 UTC
    Well i've tried this but is not giving the desired result...
    $a=1; $b=1; $c=$a+$b; while($a <=100){ print("$a\n"); print("$b\n"); print("$c\n"); $a=$b+$c; $b=$a+$c; }

      OK, if you're going to make an attempt at it, then we can help

      Lets the start you set $a and $b to 1, and $c to $a+$b = 2

      Then, on each iteration round the loop, you print out all three variables, then add 2 ($c from your initialisation) to $a and $b, then repeat.

      The assignment of $c=$a+$b simply sets $c according to the values of $a and $b at the time of assignment, and does not 'recalculate' on each trip around the loop.

      You will also have to rethink the calculation, as it doesn't quite work.

      p.s. try using strict and warnings.

Re: Fibonacci numbers
by Sweeper (Pilgrim) on Oct 05, 2001 at 00:09 UTC
    May be you could try :
    foreach (1..10) { print fibo($_), "\n" } sub fibo { $_ = '1'.'2'x($_[0]).'1'; while (/[1568]$/) {s=([2-589]?[01358])=int(abs((67*$1-1467)*$1+1423)/140)=eg} y/02678//d; return length }
      Whoa, thats wild... I'm still picking it apart, but I've got a slight obfu change, if that's what you're going for. Replace the 'return length' line with:
      now, back to figuring out exactly what the rest of that sub is doing....


        This is one of my two submissions to OPC-5. And now, here is the solution file:
        Solution -------- This program computes the Fibonacci numbers, using regexps. First, I'll prove that $_ contains only 0's, 1's and 2's, and that all other digits are there for obfuscation purpose only. Then, I'll prove that the numbers of 0's and 1's are Fibonacci numbers. Lastly, I'll explain the result. 1 Which digits? --------------- We start with a string which looks like "12222221" (with six 2's, because we want to compute fib(6)). This string contains substrings belonging to the following set: "0", "1", "2", "00", "01", "10", "11", "02", "12", "22" and "21". Of these substrings, only "0", "1", and "21" can match the regexp. For these three substrings, the formula gives: 0 -> 10 1 -> 0 21 -> 1 The resulting string will therefore contain substrings belonging to the same set. And the de-obfuscated lines would read: while (/1$/){s=(2?[01])=int(abs((67*$1-1467)*$1+1423)/140)=eg} y/02//d; 2 How Fibonacci is computed --------------------------- Theorem: at the end of the i-th iteration, the string contains fib(i-1) "1"s mixed with fib(i) "0"s then (n-i) "2"s then either a "1" or a "0" Demonstration: at the start of the program, the string contains a single "1", n "2"s and another "1". After the first iteration, the string contains a single "0", (n-1) "2"s and a "1". That is, the first part of the string contains 0 "1"s (and fib(1-1) = 0) and only one "0" (fib(1) = 1). Suppose this is true for i, we show it remains true for j=i+1. - In the first part of the resulting string, all "1"s come from the substitution 0 -> 10. There were fib(i) "0"s in the original string, therefore there are fib(i) = fib(j-1) "1"s in the resulting string. - In the first part of the resulting string, all "0"s come either from the substitution 1 -> 0 (fib(i-1) such substitutions), or from 0 ->10 (fib(i) such substitutions). Therefore, in the resulting string, there are fib(i-1) + fib(i) "0"s, that is fib(i+1) or fib(j). - In the second part of the original string, only the last "2" match the regexp. Actually, this "2" and the last "1" match "21". Both digits are replaced with a single "1", in effect deleting this "2". The number n-i becomes n-i-1, that is, n-j. 3 How many iterations? ---------------------- We start with n "2"s. Each iteration removes one "2". So, after n iterations, we have a string consisting of: fib(n-1) "1"s mixed with fib(n) "0"s and then a single "1", no longer prefixed by any "2"s. After this iteration, the loop condition (end with "1") is still true. So there is a (n+1)-th iteration, which produces: fib(n) "1"s mixed with fib(n+1) "0"s and then a single "0", because of the 1 -> 0 substitution (used for a different purpose). Then, we remove the (fib(n+1)+1) "0"s, with y/02//d, and the last string now contains only fib(n) "1"s. By the way, y/02//d could even be replaced by y/0//d, because there are no "2"s anymore. 4 Comments ---------- Where did the formula come from? I needed a formula producing: 0 -> 10 1 -> 0 21 -> 1 I tried a polynom y = a x**2 + b x + c, and I found y = (67 x**2 - 1467 x + 1400)/140 or, with the Horner formula y = ((67 x - 1467) x + 1400)/140 The problem is, only the three values give an positive integer result, which would be an indication that these three values are the important ones, and the other values can be discarded. So I introduced the functions "abs" and "int". Since I had done that, I could alter a bit the polynom, and therefore I changed it to y = ((67 x - 1467) x + 1423)/140 Duration of the program. This program is very inefficient. During the i-th iteration, you have: fib(i-1) substitutions "1 -> 0" fib(i) substitutions "0 -> 10" (which extends the string) and 1 substitution "21 -> 1". Therefore, the i-th iteration has fib(i+1)+1 substitutions, that is 0.723 x 1.618 ** i + small quantity. The total cost is 0.723 x sum(1.618 ** i + small quantities), that is O(1.618**n). Not very good, but much fun.
Re: Fibonacci numbers
by davorg (Chancellor) on Oct 02, 2001 at 14:53 UTC
Re: Fibonacci numbers(Again)
by saiful (Novice) on Oct 02, 2001 at 16:40 UTC
    Here's the most simple program to do it. You can test it.
    $a=0; $b=1; while($a <=200) {print("$a\n"); ($a,$b)=($b,$a+$b); }
      How does this statement
      does the trick? I couldn't understand...can somebody explain?

        Perhaps you can't see it because you've got the statement wrong. It should be


        It's a simple list assignment. $a gets the value of $b and $b gets $a+$b.

        Incidently, it can be a bad idea to use $a and $b in Perl scripts as they are "special" variables because of their use in sorting.

        Blessed Be
        The Pixel

        Dear Anonymous, It's very simple. In every iteration the $a receives the earlier value of $b...that's the trick. Bye the way, u can see my ealier attempt, which had one serious mistake... that can be rewritten to give the desired result. See:
        $a=1; $b=1; while($a <=200) {$c=$a+$b; print("$a\n$b\n$c\n"); $a=$b+$c; $b=$c+$a; }

        Oh, for goodness sake. This is homework, right?

        For the answer to this latest question, see the first answer in the thread...

        (Alternatively, read what you're quoting: it might make more sense then.)