Why are Fibonacci numbers significant in computer science?

Question

Fibonacci numbers have become a popular introduction to recursion for students of computer science, and there is a strong argument that they are preserved in nature. For these reasons, many of us are familiar with them.

They also exist in computer science elsewhere; in surprisingly efficient data structures and sequence-based algorithms.

Two basic examples come to mind:

• Fibonacci heaps that have better cushioned runtimes than binomial dumps.
• Fibonacci search , which shares O (log N) with a binary search on an ordered array.

Is there any special property of these numbers that gives them an advantage over other numerical sequences? Is it spatial quality? What other possible applications could have?

It seems strange to me, as there are many natural numerical sequences in other recursive problems, but I have never seen a Catalan heap.

Answer 1

Fibonacci numbers have all kinds of really good mathematical properties that make them excellent in computer science. Here are a few:

• They grow exponentially fast. One interesting data structure in which the Fibonacci series occurs is the AVL tree, a form of self-balancing binary tree. The intuition behind this tree is that each node maintains a balance factor, so that the heights of the left and right subtrees differ by no more than one. Because of this, you can think about the minimum number of nodes needed to get the AVL tree of height h, determined by the repetition, which looks like N (h + 2) ~ = N (h) + N (h + 1), which is very similar to Fibonacci series. If you work out the math, you can show that the number of nodes needed to get the AVL tree with height h is F (h + 2) - 1. Since the Fibonacci series grows exponentially fast, this means that the height of the AVL tree is no more than the logarithmic the number of nodes, which gives us the search time O (log n), which we know and love about balanced binary trees. In fact, if you can relate the size of some structure to the Fibonacci number, you are likely to get some working environment O (log n) with some operation. This is the real reason that Fibonacci heaps are called Fibonacci heaps - proof that the number of heaps after minus min includes limiting the number of nodes that you can have at a certain depth with the Fibonacci number.
• Any number can be written as the sum of the unique Fibonacci numbers. This property of Fibonacci numbers is crucial in order to generally look for Fibonacci work; if you could not add unique Fibonacci numbers to any possible number, this search will not work. Compare this to many other series, such as 3 ⁿ or Catalan numbers. This also partially explains why many algorithms, such as the powers of the two, I think.
• Fibonacci numbers are effectively calculated. The fact that a series can be generated extremely efficiently (you can get the first n terms in O (n) or any arbitrary term in O (log n)), then many algorithms that use them will not be practical. Catalan number generation is quite difficult to calculate, IIRC. In addition, the Fibonacci numbers have a good property, where, given any two consecutive Fibonacci numbers, say F (k) and F (k + 1), we can easily calculate the next or previous Fibonacci number by adding two values ​​(F (k) + F (k + 1) = F (k + 2)) or subtract them (F (k + 1) - F (k) = F (k - 1)). This property is used in several algorithms in combination with property (2) to divide numbers by the sum of Fibonacci numbers. For example, a Fibonacci search uses this to determine values ​​in memory, while a similar algorithm can be used to quickly and efficiently calculate logarithms.
• They are pedagogically useful. Teaching recursion is difficult, and the Fibonacci series is a great way to introduce it. You can talk about direct recursion, about memories, or about dynamic programming when introducing a series. In addition, the amazing is often taught as an exercise in induction or in the analysis of infinite series, and the related matrix equation for Fibonacci numbers is usually introduced into linear algebra as a motivation for eigenvectors and eigenvalues. I think this is one of the reasons that they are so loud in introductory classes.

I am sure that there are more reasons than just this, but I am sure that some of these reasons are the main factors. Hope this helps!

Answer 2

The greatest common divisor is yet another magic; see this for too many magicians. But Fibonacci numbers are easy to calculate; also has a specific name. For example, natural numbers 1,2,3,4,5 have too much logic; all primes inside them; the sum 1..n is computable, each of which can be obtained with the others, ... but no one cares about them :)

One of the important things that I forgot about is the Golden Ratio , which has a very important influence in real life (for example, you like wide monitors :)

Answer 3

If you have an algorithm that can be successfully explained by a simple and concise mannor with clear examples in CS and nature, what better training tool could you come up with?

Answer 4

Fibonacci sequences are indeed found everywhere in nature / life. They are useful in modeling the growth of animal populations, the growth of plant cells, the shape of snowflakes, the shape of plants, cryptography and, of course, computer science. I heard that it is referred to as a DNA sample of nature.

The Fibonacci pile has already been mentioned; the number of children of each node in the heap is not more than log (n). Also, the subtree starting with node with m children is at least (m + 2) the Fibonacci number.

Torrent, as protocols that use a system of nodes and supernodes, use fibonacci to decide when a new super node is needed and how many subnodes it will manage. They perform node control based on a Fibonacci loop (gold ratio). See the photo below for how nodes are divided / merged (divided from one large square into smaller ones and vice versa). See photo: http://smartpei.typepad.com/.a/6a00d83451db7969e20115704556bd970b-pi

Some occurrences in nature

http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/sneezewort.GIF

http://img.blogster.com/view/anacoana/post-uploads/finger.gif

http://jwilson.coe.uga.edu/EMAT6680/Simmons/6690Pictures/pinecone3yellow.gif

http://2.bp.blogspot.com/-X5II-IhjXuU/TVbHrpmRnLI/AAAAAAAAABU/nv73Y9Ylkkw/s320/amazing_fun_featured_2561778790105101600S600x600Q85_200907231856306879jpg

Answer 5

I don’t think there is a final answer, but one possibility is that the operation of dividing the set S into two sections S1 and S2, one of which is then divided into subsections S11 and S12, one of which is the same size as S2 , is a likely approach to many algorithms and which can sometimes be numerically described as a Fibonacci sequence.

Answer 6

Let me add another data structure to yours: Fibonacci trees. They are interesting in that the calculation of the next position in the tree can be performed by simply adding the previous nodes:

http://xw2k.nist.gov/dads/html/fibonacciTree.html

It is well connected with the discussion of templatetypedef on AVL trees (the AVL tree may in the worst case have a fibonacci structure). I also saw that in some cases, buffers are expanded in fibonacci actions, and not in two cases.

Answer 7

Just to add the little things about it, the Fibonacci numbers describe the breading of rabbits. You start with (1, 1), two rabbits, and then their population grows exponentially.

Answer 8

Their calculation as the degree of the matrix [[0,1], [1,1]] can be considered as the most primitive problem of operational research (like the Prisoners Dilemma - the most primitive game theory problem).