Rightnow I have the first 3 voulmes of this book. I tried to read these books, to completion, but never was able to. :-(
I did Randomized Algorithms course in IIT, so I read Volume II to some extent.
Randomized Algorithms course was interesting as each time our prof gave a new algorithm, he used to say "Now that we know this algo, so its no more random, as we can predict the next number using this algorithm :-)"
Finally He concluded the course saying theres no truly Random Algorithm existing in this world. So whats the point in doing this course :-O
I was just skimming through Volume I of this book (Knuth) and saw the section about the famous series, Fibonacci Series.
This reminded me of a the program I did long back, when I was in college, which prints all the fibonacci numbers. Fibonacci numbers are mentioned in Dan Brown's novel DaVinci Code. Many of you might know about Fibonacci numbers through this book, but a computer science grad will definitely kow about Fibonacci series...even the mathematics grad should be knowing about these sequesnce. But many of then don't know the importance of this series.
The algorithm is simple:
If F(n) is the nth fibonacci number then
F(n) is 1 for n = 1, 2
F(n) = F(n-1) + F(n-2) where n>2
At that time, I was curious why we are doing this program. All I could know is this is one example for writing a recursive program.
I wrote GCD:
GCD(m,n) = GCD(n,m), if n>m;
= m if n=0;
= GCD(n, m%n), otherwise.
I wrote Ackermann's function:
A(0,n) = n+1;
A(m+1,0) = A(m,1);
A(m+1,n+1) = A(m, A(m+1,n))
But I felt both these functions are of importance. GCD...we know about it, Ackermanns function is one of the fastest growing primitive recursive function I know till date. (consider f(x) = A(x,x) then for x = 0,1,2,3,4, g(x) values are 1,3,7,61, 2^2^2^65,536 -3 :-O ( where ^ is to-the-power-of)
Well, I tend to divert from the actual topic:-D, let me get back. I know GCD or ackermann's functions has some importance, but why Fibonacci numbers? :-O
No idea then, but this curiosity made me investigate what this fibonacci numbers are....
Fibonacci numbers were invented by Leonardo Pisano in 1100AD. Before Fibonacci (Leonardo's another name) wrote his work, the sequence Fn had already been discussed by Indian scholars, who had long been interested in rhythmic patterns that are formed from one-beat and two-beat notes. The number of such rhythms having n beats altogether is Fn+1; therefore both Gospala (before 1135) and Hemachandra (c. 1150) mentioned the numbers 1, 2, 3, 5, 8, 13, 21, ... explicitly. (Snip taken from a website. forgot the link :-( )
Fibonacci mentioned a problem in his books...
How Many Pairs of Rabbits Are Created by One Pair in One Year?
A certain man had one pair of rabbits together in a certain enclosed place, and one wishes to know how many are created from the pair in one year when it is the nature of them in a single month to bear another pair, and in the second month those born to bear also.
He then goes on to solve and explain the solution:
Because the abovewritten pair in the first month bore, you will double it; there will be two pairs in one month. One of these, namely the first, bears in the second month, and thus there are in the second month 3 pairs; of these in one month two are pregnant and in the third month 2 pairs of rabbits are born, and thus there are 5 pairs in the month;
...
there will be 144 pairs in this [the tenth] month; to these are added again the 89 pairs that are born in the eleventh month; there will be 233 pairs in this month. To these are still added the 144 pairs that are born in the last month; there will be 377 pairs, and this many pairs are produced from the abovewritten pair in the mentioned place at the end of the one year.
You can indeed see in the margin how we operated, namely that we added the first number to the second, namely the 1 to the 2, and the second to the third, and the third to the fourth and the fourth to the fifth, and thus one after another until we added the tenth to the eleventh, namely the 144 to the 233, and we had the abovewritten sum of rabbits, namely 377, and thus you can in order find it for an unending number of months.
The ratios of successive Fibonacci numbers F(n)/F(n-1) approaches the golden ratio phi as n approaches infinity.
What is Golden Ratio..hey wait, this would be fun to know, but wait for next post. :-)
Some interesting properties of Fibonacci numbers.
We see Fibonacci numbers in biology:
Phyllotaxis: (The following snip was taken from mathworld.wolfram.com)
The beautiful arrangement of leaves in some plants, called phyllotaxis, obeys a number of subtle mathematical relationships. For instance, the florets in the head of a sunflower form two oppositely directed spirals: 55 of them clockwise and 34 counterclockwise. Surprisingly, these numbers are consecutive Fibonacci numbers. The ratios of alternate Fibonacci numbers are given by the convergents to phi^(-2), where phi is the golden ratio, and are said to measure the fraction of a turn between successive leaves on the stalk of a plant: 1/2 for elm and linden, 1/3 for beech and hazel, 2/5 for oak and apple, 3/8 for poplar and rose, 5/13 for willow and almond, etc. (Coxeter 1969, Ball and Coxeter 1987). A similar phenomenon occurs for daisies, pineapples, pinecones, cauliflowers, and so on.
Lilies, irises, and the trillium have three petals; columbines, buttercups, larkspur, and wild rose have five petals; delphiniums, bloodroot, and cosmos have eight petals; corn marigolds have 13 petals; asters have 21 petals; and daisies have 34, 55, or 89 petals--all Fibonacci numbers.
This figure shows the buds 13 in clockwise and 21 in anti-clockwise...both Fibonacci numbers.Some mathematical properties:
1) F(n+1)*F(n-1) - 2*F(n) = (-1) TTPO n
2) GCD(F(m),F(n)) = F(GCD(m,n))
3) F(n) <= phi to-the-power-of (n-1)
4) phi to-the-power-of 2 = phi + 1;
5) phi = (1+sqrt5)/2
6) Fib(n) = round( Phi TTPO n/√5 )
7) Fibonacci numbers are complete, which means you can generate any positive number with the sum of any set of Fibonacci numbers.
8) Neighbouring Fibonacci Numbers have no common factors
9) Any prime Fibonacci number must have a subscript which is prime with one exception. (Go and find it out yourself. ;-) )
10) Can you find out Fibonacci numbers from Pascal's traingle?
There are lot more of such properties in The Art of Computer Programming by D. Knuth.
One of the interesting problem I found in the excercises of this book is
Problem) 2 players complete is a game: There a pile of n chips; 1st player takes as many chips as he like, except he can't take the whole pile.
From then on, players alternate moves, each person can take atmost twice as many chips as the preceeding player has taken. The player who takes the last chip wins.
Now solve this problem ;-)....do you see the usage of Fibonacci numbers here?
Some more properties. Basically you see such questions in interviews ;-)
1) The number of ways of picking a set (including the empty set) from the numbers 1, 2, ..., n without picking two consecutive numbers is F_(n+2). The number of ways of picking a set (including the empty set) from the numbers 1, 2, ..., n without picking two consecutive numbers (where 1 and n are now consecutive) is L_n==F_(n+1)+F_(n-1), where L_n is a Lucas number.
2) The probability of not getting two heads in a row in n tosses of a coin is F_(n+2)/2^n (Honsberger 1985, pp. 120-122). Fibonacci numbers are also related to the number of ways in which n coin tosses can be made such that there are not three consecutive heads or tails. The number of ideals of an n-element fence poset is the Fibonacci number F_n.
3) Given a resistor network of n 1-Omega resistors, each incrementally connected in series or parallel to the preceding resistors, then the net resistance is a rational number having maximum possible denominator of F_(n+1).
Do you know about Fibonacci number system? No I won't mention it here. Go find it yourself :-P
(Hint: search for Fibonaccimal)
Do you realize. KM to Mile conversion we can use Fibonacci numbers?
Yes. 8 Kms is 5 miles, 5 kms is 3 miles....So F(n) Kms is F(n-1) miles!!
What if you have to find 20 Kms in miles. Yep there a solution. convert to Fibonacci number system.
20 can be expressed as 13+5+2. So the miles conversion is 8+3+1=12Miles!!
Note: These are just approximations in Miles, not close values.
Now don't ask me what the value of 1Km in Miles ;-) ...larger values get closer but not accurate approximation.
visit this link for more info
Fibonacci numbers:
http://mathworld.wolfram.com/FibonacciNumber.html
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibrep.html
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/Fibonomials.html
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibInArt.html
Phyllotaxis:
http://mathworld.wolfram.com/Phyllotaxis.html
http://maven.smith.edu/~phyllo/index.html
Fibonacci numbers in nature:
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibnat.html
Fibonaccimal Base:
http://acm.up.pt/local/prova2/c.html
Books:
The Art of computer programming, Volume I, by D. Knuth.
