Fibonacci Numbers?

[Dillinger4]

I was looking at a small example program that calculates Fibonacci numbers to use as output.

Fibonacci Numbers: A sequence of numbers where each subsequent number is calculated by obtaining the sum of the previous two numbers. ie... 1,1,2,3,5,8,13,21.....

So i take it that Fibonacci is some old Itialian mathematician. But what is the point of this sequence? What could or has it ever been used for?


Thanks :D

[Yonatan]

These numbers show up everywhere :rolleyes:

Classic example: A person has 3 stages in his/her/and/or/its life:
1) Junior
2) Adult
3) Senior
And then he/she/and/xor/it dies.
When he/she/and/etc. is an Adult, he/etc. has a kid.
With every generation that passes, the Adult has another kid.
Start with one child:

A) One child. (1 child, 0 adults, 1 total)

B) One adult (the child grew up). (0 children, 1 adult, 1 total)

C) One adult and one child. (The adult had a child.) (1 child, 1 adult, 2 total)

D) Two adults and one child. (The adult from 'C' had a child, and the child from 'C' grew up and became an adult.) (1 child, 2 adults, 3 total)

E) Three adults and two children. (The adults from 'D' had children, and the child from 'D' grew up.) (2 children, 3 adults, 5 total)

F) 5 adults, 3 children, 8 total.
G) 8 adults, 5 children, 13 total.
H) 13 adults, 8 children, 21 total.

See... Everywhere :rolleyes:
(Ok, this is a bad example, because nobody's THAT sexually active)

[parksie]

Originally posted by Yonatan
(Ok, this is a bad example, because nobody's THAT sexually active) Except Katie :D
You see them in numbers of petals, buds and things like that on plants.

[Dillinger4]

I think it's a pretty good example. I took me a minute to see your pattern.

C--A
1, 0
0, 1
1, 1
1, 2
2, 3
3, 5
5, 8
8, 13
13,21
21,34

But if we start out with one child and no adult. Where did he come from? And if we start out with one adult wouldnt he have to be a child first? :confused:

Almost like which came first the chicken or the egg. :eek:

[Guv]

In prehistoric times, computers used magnetic tape instead of disks. While a CPU was slow in those days, tape operations ran like molasses in January. Waiting for a tape to rewind was a real bummer.

The following will require some patience and paying careful attention. I hope I can describe it well enough to allow it to be understood.

Somebody came up with a cute sorting tecnique based on Fibonacci numbers. Note that tapes could be read in either direction, but could only be written forwards. Keep the following Fibonacci numbers in mind while reading the rest of this post.

13, 8, 5, 3, 2, 1, 1 (deliberately backwards).

Four tapes would normally be used to sort a large file. The original file would be read from one tape and groups of sorted records would be alternately written to two output tapes. The fourth tape drive would be idle during this initial operation.

Next the three tapes would be rewound. The initial file would be removed and saved. From this point on, two tapes would be read, and groups of sorted records would be merged into larger groups. The larger groups would be assigned alternately to two output tapes. When all the input had been read, all four tapes would be rewound and the output tapes would become input tapes & vice versa for the next merging operation. The process would continue until there were only two large groups of sorted records which got merged into one final sorted group.

The Fibinacci sort started in much the same way using one input tape and two output tapes. The difference was that the sorted output groups were not assigned alternately to the two ouput tapes. Instead they were assigned in such a way that the two tapes had groups of sorted records that corresponded to two consecutive Fibonacci numbers.

For example, after the initial operation, there might be 8 groups on one tape and 13 on the other. Now instead of rewinding all three tapes to start the merging process, only the input tape would be rewound. While that tape was rewinding the merging process would start by reading the two output tapes backwards and merging groups, which would be written to the fourth tape (it had been idle).

Note what would happen during the first merging operation. 8 groups from one tape would be merged with 8 groups from the other, resulting in 8 large groups being written to the output tape, leaving 5 groups on one input tape and none on the other.

Since the input was read backwards, the tape which originally had only 8 groups would be at the begin tape position, and could now be used for output. The tape which originally had 13 groups would only have 5 left, while what had been the output tape would have 8 groups of sorted records ready to be read backwards for the next merging operation.

The next merging operation would merge 5 groups from each input tape, exhausting the tape which only had 5 groups, and leaving 3 groups on the other tape.

After each merging operation, one input tape is exhausted and is ready to be used as an output tape. One input tape still has some groups of sorted records. What had been an output tape is ready to be ready backwards for the next merging operation.

The number of groups of records on the input tapes are always consecutive Fibonacci numbers.

I hope some of you can follow the above.

[Judd]

A related point,

If you divide two consecutive Fibonacci numbers you get closer and closer to the 'Golden Ratio' (Or Golden Section). This is a trancendental number that was commonly used in ancient architectural design as it was thought to be the perfect proportion (or at least that which is most pleasing to the eye). This is probably because it is this ratio which is commonly observed in the natural world which may, in tern, be related to the way cells replicate.

The relevant numbers are approximately:

GR: 1.61803398874989
GS: 0.618033988749895

I'm sure you can see the pattern there.

This can be visualised by drawing a straight line (length a) on a piece of paper. If you then divide that line into a long (length b) and a short (length c) section, such that a is longer than b by the same ratio that b is longer than c, you'll find that the ratio is 'golden'.

[Yonatan]

Actually, if you define "transcendental" by "cannot be the solution of a polynomial equation whose coefficients are rational", then the numbers are not transcendental, only irrational.
The numbers are
1 + sqrt(5)
-----------
2

1 - sqrt(5)
-----------
2Note: The second number is actually negative...
These numbers are two solutions of the equation:
x^2 = x + 1
They can also be defined as "to square it, just add one". :rolleyes:

There is also a non-recursive formula for determining a Fibonacci number:
1 + sqrt(5)
a = -----------
2

1 - sqrt(5)
b = -----------
2

a^n - b^n
F(n) = ---------
sqrt(5)I don't remember the proof of this, but I'll get over it. :rolleyes:

The function F(n) has the following "features":

When n is a natural number, F(n) is the n-th Fibonacci number.
And also some less meaningful features:
When n is a whole number, F(n) is a whole number.
F(0) = 0.
When n is a natural number:
F(-n) = F(n) * (-1)^(2n + 1)
Finally, since (b^n) is evaluated and b is negative, the function is not defined for irrational numbers, and only defined for specific rational numbers, which give pretty much meaningless values as the result of F(n)...

That was fun :rolleyes:

[thinktank]

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html :)

[Dillinger4]

Sweet Thanks!

[HarryW]

And there was I thinking Surrey Maths and Computing department was useless :rolleyes: (I'm a Surrey student)

[thinktank]

Just in case, You missed this :D

Where do you go to get a degree in Apologies?
** at the University of Sorry (Surrey) **

Other pieces...

University courses: to study ...
Ship Shapes at Hull or perhaps Keel (Keele)
British money at Stirling
Word endings at Suffix (Sussex)
Moral Principles at Ethics (Essex)
Books at Reading
Cleanliness at Bath
Peppermint sweets at Imperial
Sea Mammals at Whales (Wales)
Noisy Fireworks (or Sausages or Old Cars) at Banger (Bangor)
Bonfires at Burning 'em (Birmingham)
Rope Joining at Knotting 'em (Nottingham)
Electric Cabling at Leads (Leeds)
Bad shot at Darts (Snooker,etc) at you missed (UMIST)
How cows experience milking at Udders Feeled (Huddersfield)
Binary Multiplication at Doublin' (Dublin)
Sick Men at Guy's Hospital
Male running after Female at Man Chased Her (Manchester)
Looking down a Rabbit Hole at 'ead in Burro' (Edinburgh)
Cows crossing rivers at Ox-ford

:D :D :D :D :D :D :D :D

[Behemoth]

Male running after Female at Man Chased Her (Manchester)

:D

[HarryW]

That's bloody awful.

[ADW]

These are the last 9 possible fibonnacci numbers that can be generated in Visual Basic without an error:

130. 659,034,621,587,633,000,000,000,000
131. 1,066,340,417,491,720,000,000,000,000
132. 1,725,375,039,079,350,000,000,000,000
133. 2,791,715,456,571,060,000,000,000,000
134. 4,517,090,495,650,410,000,000,000,000
135. 7,308,805,952,221,480,000,000,000,000
136. 11,825,896,447,871,900,000,000,000,000
137. 19,134,702,400,093,400,000,000,000,000
138. 30,960,598,847,965,300,000,000,000,000
139. 50,095,301,248,058,600,000,000,000,000

Small numbers...

~ADW~

[Kaverin]

Even though the post is pretty old now, I thought I'd add this anyway. There's another place where a Fibonacci sequence pops up, and that's in a binomial expansion. In this case, the number sequence looks like this:

1 n = 0
1 1 n = 1
1 2 1 n = 2
1 3 3 1 n = 3
1 4 6 4 1 n = 4
1 5 10 10 5 1 n = 5
(this goes on of course)

Each line gives the coefficients of the terms in the binomial expansion (a+b)^n. If n = 4 for example, you get this as the complete expansion:

1(a^4)(b^0) + 4(a^3)(b^1) + 6(a^2)(b^2) + 4(a^1)(b^3) + 1(a^0)(b^4)

Binomials like this can be used in determining the number of times you'll see particular events in a set of n events with one of two outcomes, a or b. The first term in the above one for example (when evaluated), gives the number of times you'll see 'a' 4 times, the second term is 'a' 3 times and 'b' once etc. if you were to repeat the entire process 4 times.


And for something funny (and if you're not a bio person, feel free to ignore it, since I can go on for a while)...

Dilenger4, if you think about it in terms of evolution, the question is easily answered: the egg came first.
In evolutionary time, simpler organisms were producing eggs long before birds even existed. If the egg you're thinking of is like the "normal" bird egg, the amniotic egg, they first appeared as amphibians started to leave the water completely and live solely on land, so the answer to the age old question would still be "the egg was first". For amphibians, protective membranes on eggs aren't required, but limits them since they must lay eggs in water. The amniotic egg has many protective membranes, and also an outer shell, which allows the egg to be laid on land and not dry out. This sort of egg first appeared in early reptiles, and is the form of egg now seen in all reptiles, birds (which are thought to have arisen from reptiles), and mammals. And before that last group makes you think "Huh?", mammals do produce this egg, but it doesn't have the exterior calcium compound shell, and it "hatches" internally for those organisms that bear live young. There are some species of reptiles that do this, and all mammals with the exception of the monotremes, which still lay eggs on land that hatch later.

[Guv]

Kaverin: What is the relationship between the binomial expansion and the Fibonicci series? I do not see it.

Fibonacci series is 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55 . . . .

Each term is the sum of the previous two terms.

[Kaverin]

I assume it is sometimes called a Fibonacci sequence because a number in a given row is the sum of the two numbers to the upper left and right above it. It's also called Pascal's triangle. I just remembered that while I was outside washing the car :).

http://www.intelos.net/~pwcash/junk/Pascal.bmp

[thinktank]

I assume it is sometimes called a Fibonacci sequence .

That's a wrong assumption.

[Kaverin]

I'm not assuming it's called that. I've heard it called that before, although I don't know why, since there is no real relation to a true Fibonacci sequence. I assumed that it was called that because of the way numbers in the set are generated. I only gave that because it was the only name I could remember hearing for the set. I didn't remember until after Guv asked about the relationship.

[Smarturtle]

CAN SOMEONE PLEASE TELL ME HOW TO DO THE FIBONACCI NUMBERS IN FOR NEXT..... PLEASE GIVE ME THE CODE THANKSSS

OH AND I FORGOT... IN VISUAL BASIC PLEASE