Perl: the Markov chain saw PerlMonks

### Fibonacci numbers

 on Oct 02, 2001 at 00:50 UTC 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
Yes.

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.

Yves
--

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 ... ) );

xoxo,
Andy
--
<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 see....at 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:
```s;.;+1;g;eval;
now, back to figuring out exactly what the rest of that sub is doing....

-Blake

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.

----------
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
```(\$a,\$b)=(\$a,\$a+\$b);
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

```(\$a,\$b)=(\$b,\$a+\$b);

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;
}
Thanks.

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

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

Create A New User
Domain Nodelet?
Node Status?
node history
Node Type: perlquestion [id://115972]
Approved by root
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others browsing the Monastery: (6)
As of 2022-07-04 11:42 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?

No recent polls found

Notices?