Fibonacci Programming - Computerphile
HTML-код
- Опубликовано: 2 авг 2024
- Audible Free Book: www.audible.com/computerphile
Following on from our film on recursion, Professor Brailsford uses the Fibonacci Sequence as a further demonstration of recursive programming.
Original Recursion film: • What on Earth is Recur...
Fibononacci on Numberphile
Sunflowers and Fibonacci: • Sunflowers and Fibonac...
Tartan and Bagpipes: • Fibonacci Tartan and B...
Fibonacci Mystery: • Fibonacci Mystery - Nu...
Professor Brailsford's programs and a hint of what is to come: bit.ly/1nhKtW4
/ computerphile
/ computer_phile
This video was filmed and edited by Sean Riley.
Computer Science at the University of Nottingham: bit.ly/nottscomputer
Computerphile is a sister project to Brady Haran's Numberphile. See the full list of Brady's video projects at: bit.ly/bradychannels
No joke, this channel, and, in particular, this man, Professor Brailsford, are very significant factors in my decision to go back to college at age 30 and get my bachelor's degree in Computer Science. I am now halfway done with my degree, and I have a perfect 4.0. I never wrote a line of code until I was 29, but the programming bug bit me hard. Thank you for inspiring my love of computer science, Professor!
I am in a similar situation like you although slightly younger. How is it going man?
Dear Professor Brailsford,
Thank you so much for this series, I"m a nurse whose gone back to school for web development and you just made a part of my program a success instead of a failure.
Many thanks!
We're going to cover 'recursion' again? I see what you did there....
Thank you computerphile, watching these videos I finally remembered what it was that made me choose programming as a profession. I feel like a 10 year old right now :)
This man is such a great teller, i found gold in this video's. Golden knowledge and am learning all of this. And I feel that you are making the world a better place with sharing this. Thank you.
Marco Meerman exactly how I feel.
I guess we can say u found the golden rule
The most beautiful definition of the Fibonacci sequence I have seen is still this Haskell one liner:
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Computerphile has been literally posting the exact same material that I have been learning in my data structures class. It has been great for furthering my understanding!
I absolutely love and admire this guy. Well, I don't think I haven't liked any of Numberphile or Computerphile's guests ever, they are all so smart and charismatic!
By the way, the dynamic approch in python:
memo = {}
def fib(n):
if n in memo:
return memo[n]
else:
memo[n] = n if n < 2 else fib(n-2) + fib(n-1)
return memo[n]
Really enjoyed the talk you did on the open day for the university. It's where i'd like to come to study Computer Science. It was awesome to see you in the flesh haha Keep up the great work! :D
sometimes you need to trust your teacher or instructor to understand something, I looked up recursion online because I have difficulties to understand it, and then finally Professor Brailsford helped me and I got it, but I think the only reason is because he is the only one I trusted and for the first time I listened to the end, maybe because he is very much experienced and look very wise person to me
I love writing recursive programs. They're so elegant! (If occasionally inefficient)
Tail recursive Fibonacci in Erlang:
fib(N) -> fib(N, 1, 0).
fib(0, Acc, _) -> Acc;
fib(N, Acc, Tmp) -> fib(N-1, Acc+Tmp, Acc).
There is also a formula to find out the nth position in the Fibonacci sequence.
f(n) = ((1+√5)^n - (1-√5)^n) / (2^n(√5))
***** How is that inaccurate? It gives you the exact value for every n.
***** I was wondering the same exact thing. Plug in any value of n and you will get the correct value.
***** Theres are quite a few proofs of this formula, I can think of 3 off the top of my head. It works perfectly fine and can cumpute any nth fib number (the golden ratio isnt anything special to do with the fib numbers by the way, check out the brady numbers numberphile video)
That is not only incorrect, its a classic example of a wrong algorithm in many algorithms first lessons in Universities. You simply can not store Square root of 5 in a machine with finite amount of memory.
Even tho the formula is correct It is not a correct algorithm.
6:05 very convenient how the lighting turned dark as he was saying this
I remember reading that any recursive function can be converted into an iterative procedure (though it may require the use of a stack.) This makes sense because assembly language (and I don't care what processor we are talking about; I've seen several and it holds for all of them) does not actually allow for recursion.
I've been reading through the wizard book (The Structure and Interpretation of Computer Programs) recently, and another interesting thing about the tree recursion definition of Fibonacci(n) is it's order of growth. Because each time you want to compute a fibonacci number you have to compute the last two fibonacci numbers, the time it takes to compute a given fibonacci number is itself a fibonacci number.
Fibonacci numbers are intricately linked to the golden ratio, and in fact a given fibonacci number is the closest integer that is a result of taking the golden ratio to the nth power, divided by the square root of five. So with respect to time, the order of growth is given by (phi^n / sqrt(5)), which we can put as Theta(phi^n) for simplicity's sake. This is an exponential order of growth, and so very bad if you want to compute large fibonacci numbers!
Would love to see more videos on recursion!
Fibonacci spiral in python 3
from time import sleep
import turtle
turtle.color("light blue")
turtle.pencolor("dark blue")
a, b = 0, 1
for i in range (2000):
c=(a+b)
a= (b)
b = c
print (c)
turtle.circle(c, 90)
sleep (.05)
input()
It feels like Winnie the Pooh is teaching me maths!
I can't unhear this now...
Gather round the pot of honey guys it time to learn advanced computer science
Haskell:
fib 0 = 0
fib 1 = 1
fib n = fib ( n - 1 ) + fib ( n - 2 )
or
fib = 0 : 1 : (zipWith + fib (tail fib))
About a year ago, I had a great Fibonacci sequence idea, which I call Fibinary notation. It turns out (not too unexpectedly) that not only was I not the first to think of the idea, I also wasn't the first to think of the name.
If D is a sequence of binary digits (i.e. D_i = 0 or 1 for all i) then we can interpret it as an integer by
value = Sum_i D_i F_{i+1}.
(Smallest index is 1.) Compare to binary notation, where
value = Sum_i D_i 2^{i-1}.
(When we write D as a string of digits, we write it from highest index on left to lowest index on right.)
One interesting outcome is that Fibinary notation is not always unique, e.g. 100 = 3, but 011=3 also. In fact, anywhere in the sequence you see '011', you can substitute '100' without changing the value (and vice versa.) I call it canonical form when there are no adjacent 1s.
It isn't too hard to come up with an addition algorithm, although it would be hard to efficiently implement in logic gates because you don't know how many times you need to do 011 -> 100 substitutions. I looked at multiplication, threw up my hands in horror, and tried no further.
Web search for 'fibinary' to find out more. There is also an academic paper on a generalization of fibinary notation, the citation to which I don't have on hand (as I recall, it did not use the name 'fibinary').
Actually the first fibonacci number is 0, although I think it's F(0).
0 1 1 2 3 5 8 includes the case where no rabbits are there.
***** Prove it. Because its impossible for me to prove that I draw invisible object.
no...it 1,1,2,3,5,8,13,...
No. 0 rabbits is no case. 2 rabbits is the beginning. 1, 1.
and then the rabbits, you know, do their thing.
Thank you very much for this, I'll use it whenever I need to help explain recursion.
PROFESSOR BRAILSFORD
CAN YOU PLS BE MY COMP SCI PROFESSOR
YOU ARE LEGEND IN SOUTH KOREA
+Steve Lee Im pretty sure just about any computer science class wants him as a professor.
Why mess with the dict stuff? Postscript already has an "easy" to use stack
/fib {
dup dup 1 eq exch 2 eq or
{ pop 1 }
{ 1 sub dup 1 sub fib exch fib add }
ifelse
} def
My assignment in class was to write a program that could handle calculating the Fibonacci sequence to the 1000th number. But we could not use any of the large number libraries. We had to build a linked list class that could add and store the numbers.
Just love the Prof!
It's much less computationally intensive if you define f(n) = 2 * f(n-2) + f(n-3).
You do need to define one more special case though: f(1)=1 f(2)=1 and f(3)=2.
f(10) would then take 17 function calls instead of 55, and f(20) would take 301 instead of 6,765.
This desn't improve the overall computational complexity however. The number of calls is still proportional to r raised to the power of n, where r is the Golden Ratio. There is a way to calculate Fibonacci in linear time. See www.geeksforgeeks.org/dynamic-programming-set-1/
Could you do a video on prolog?
what is the formula of logarithmic spiral approximated by Fibonacci spiral?
Someone could say me if there's a reproduction list about recursion or the videos that talk about it? I'm doing an important work about it to enter for the university and it would be useful
With memoizing in Python:
computed_fib = {1:1,2:1}
def fib(n):
if n in computed_fib:
return computed_fib[n]
else:
computed_fib[n] = fib(n-1) + fib(n-2)
return computed_fib[n]
And the 2015 Fibonacci number would be:
In [17]: print fib(2015)
5762488896030140993970127447076792874336403418687476758848483166124324633496452225745760531625355769343572448331578223521805650643845496976578903145216445829111893577603290923340147837405958982446562955804144013677696770990394272037162587085666026561601045718910518761496231846434488662629501872606840106837782272291703369191403678479329790837646825844843416090881795139086749031394076973360344297117287140768030461857985
Is it possible to generate the set of arrangements of a n-element set without recursion ?
For people who enjoy fun bits of trivia, the desks behind which the panellists sit on QI each have Fibonacci spirals on them. If you take adjacent pairs of Fibonacci numbers and divide them (1/1, 2/1, 3/2, 5/3, 8/5,...), you'll find yourself steadily getting closer to the quantity which is written behind Stephen Fry's right ear.
... and you can make it into an actual logarithmic spiral by using actual golden rectangles (GRs) from the start, each added square making the next larger GR out of the previous one; and continuously increasing the radius of curvature of the spiral, not just at each rectangle boundary crossing.
Might be interesting to see those two sets of rectangles and spirals co-overlaid, maybe in contrasting colors.
Fred
For Professor Brailsford, everythink will end up in stacks
As long as they are implemented in PostScript of course !
I bet he puts stacks in stacks, too.
Stackception programmed in PostScript
On a hardware level stacks are everywhere, so he is not wrong
well this should not matter since computer science isn't about computers...
Possible to do this at O(log n), by squaring matrix transforms.
5:43 *windows closes behind him* Woo for smart buildings!
wow... great observation :)
You can also use Z Transform to get a formula for every nth number in the fibonacci sequence. You get F(z) = z/(z^2-z-1). Inverse Z transform gives, F(n)=(-(1/2 (1 - Sqrt[5]))^n + (1/2 (1 + Sqrt[5]))^n)/Sqrt[5]. If you put in negative numbers, and plot a curve in the complex plane. Imaginary number as the y axis and real numbers as the x axis. you get a fine spiral too :)
If you plot from 0 to 2, I really love the little loop the curve does to pass number 1 twice :D
Really liked that =)
A non-recursive equation can be made for fibb(n). What I have been trying to determine is if a non-recursive equation can be made if we scale the recursion to a third degree.
If a1=1, a2=1, and a3=1, and a(n+1)=a(n)+a(n-1)+a(n-2)....
can a non-recursive function be made?
#GPC - 2017
x, y = 1, 1
while True:
print(y)
x, y = y, x+y
Maybe you could use the Fibonacci sequence to introduce the concepts of Memoization and Dynamic Programming.
"en plus oneth" or "en plus first"?
Do a Computerphile or Numberphile or both on the Mandelbrot set!
So, did he actually explain what kind of operations can´t be de-recursed?
+Kabitu1 I think it's in here /watch?v=i7sm9dzFtEI
I wrote a recursive program in c++ to find the Fibonacci sequence at varying steps and included the number of iterations of the function it take to get from one member of the set to the next.... The first, like, ten members took a couple hundred iterations each. It ground to a near halt around the 50th member of the sequence... That's because it took 25 billion iterations of fib() to get from the 49th to the 50th member... 😳...
If anyone wants the code, I'll gladly paste it.
Doesn't a recursive approach lead to an exponential nightmare with larger values of n though? Unless you do something clever with a globally available array of already determined values set from previous function calls, you'll find an ever increasing number of cases where the function is called with the same arguments as one or more others, which is entirely pointless for a deterministic function.
Some clever languages like Haskell let you define an operator that automatically memoizes (i.e. stores prior results in a list) for any function, which is a top down approach.
Rumor has it professor Brailford dreams about recursion
I'm trying to get into computer science and programming. Any help? I'm fairly young so I have lots of time to learn.
.
Please make a video about polymorphism
Here's a little fact:
Did you know the human hand follows the Fibonacci sequence? Start at the tip of any finger and measure the distance between the joints all the way to your wrist. Its actually what I go by when I'm 3D modeling a human hand to proportion.
loving the scrap paper ;)
You sent me here from the university of Nottingham open day.
"The fact that this region of the universe has a limited observable range as the waves come from a distance radius. . ..And the fact that the electron is a perfectly round sphere.. . .Are two sides of the same + and - coin!!
There exists only two combinations of these two spherical + and - electromagnetic sine waves, or wavefronts multiplying and dividing at right angles.. . .They have opposite vectors and quantum spin forming the positron and electron wave centre.. . .4pi R2=/N pi Re2.. . .
Or "the two energy states of Qubits" in quantum computing which can be such things as photons, trapped ions, atoms, electrons, and nuclear spins made of vibrating wavefronts called shells in particle physics, or spherical standing wave structures over a period of time.. . .E2=mc2/c4+p2/c2.. . .Only difference is time dilating Volume!!
Their output was the negation of their input: 0 goes to 1/1 to 0.. . .the start of a Fibonacci spiral.. . .
Therefore generation of any information exceeds radiation during the first half of the cycle. . ..Radiation now exceeds generation during the second half of the cycle as the constant outward momentum of EMR (de-compression) repels like charged particles absorbing energy and emitting the density from the two previous vectors spiralling out the Fibonacci sequence seen everywhere in nature.. . .
Since centre is everywhere forming the total amplitude of sinusoidal waves at each and every point of space then mc2 represents the expansion of mass which is an opposite de-compression from the energy compression c4+ acting upon time dilating inertial ref-frames p2 at the expense of gravitational potential c2.. . .
Space is a division of solidity into entropy C2 the second law of thermodynamics.. . .But also E2= a multiplication of volume at the expense of gravitational potential."
Y sigo teniendo demostraciones de que mi tatto es un EXCELENTE Y MUY BIEN ELEGIDO TATTO algo de lo que nunca me arrepentiré
I see a few recursive functions in the comments, some call it a 'better' version, but they have probably never called those functions with high integer values... stack overflow imminent.
if you follow the fibonacci sequence in reverse, you get alternating positive and negative numbers of the same as forwards. just thought it was interesting.
give me 10 dicts? oh my professor...
4:33 this sounds like a name for some kind of a world replacement meme video...
why can't you declare an array and pass it to your c function and get the results in it??
Isn't that the same thing??
Yes you can. In fact, it is posible to optimize the function by storing previously computed results in the array.
Python:
oldNumber, newNumber, answer, n = 0,1,0,10
for i in range(n):
answer = newNumber + oldNumber
oldNumber = newNumber
newNumber = answer
print answer
STOP = input("STOP!")
Postscript reminds me of FORTH
Yup sir.....
I just wrote a Fibonacci sequence using tail calls to optimize it so it doesn't use the stack. I think that would make an interesting video. Thanks for your work, I love the channel. Here's the links to my program, it's written in javaScript. jsfiddle.net/syntaxerrorforbearer/yjjbxhve/ - optimized (not using the stack), and jsfiddle.net/syntaxerrorforbearer/uku716z2/3/ - recursive version using the stack. If you put a large number in the recursive version the browser will crash because the stack gets overflowed, but the tail call version handles big numbers no problem because there are no pending computations between recursive calls.
Here's an example. it calculates the first 93 Fibonacci numbers almost instantly (caching previous values for performance).. Incidentally, 'theAnswer' = 12200160415121876738. I'll leave you to check manually if it is correct.numeric overflow started occurring just after 93 on my 64-bit PC.
using System.Collections.Generic;
namespace Fibbers
{
class Program
{
private static Dictionary _fibs = new Dictionary();
static void Main(string[] args)
{
_fibs.Add(1UL, 1UL);
_fibs.Add(2UL, 1UL);
ulong theAnswer = Fib(93);
}
private static ulong Fib(ulong i)
{
if (_fibs.ContainsKey(i))
return _fibs[i];
_fibs.Add(i, Fib(i - 1) + Fib(i - 2));
return _fibs[i];
}
}
}
Just because:
void fib(int* a, int* b)
{
Printf("%i
", *b);
*a += *b;
fib(b,a);
}
Stack frames?! I need a video on it, professor!
+CircleofMadness watch the previous one (what on earth is recursion)
Thanks, I think I got it. Basically every time a recursion goes one level down it creates a stack frame with it's own local variables and waiting for a return.
Fibonacci's real name is Leonardo of Pisa.
On a similar note, Da Vinci is Italian for "of Vinci", so it's not Leonardo Da Vinci's last name, rather, it's his birthplace.
And now the Ackermann function, please :)
This fibonacci programming they used in building of Pyramids.
Cocktail "Recursive": 20% of alcohol, 30% of water and 50% of cocktail "Recursive."
Aaaaand.... cliffhanger...
Am I the only one who, if I made a movie about recursion, would have it link to itself?
Google recursion. You are definitely not the only one :P
That's what I was thinking when I commented that. ;)
i guess for javascript:
var fibNum = 8; //Amount of numbers in the sequence (example: 6)
var fibArr = [];
fibArr[0] = 1,fibArr[1] = 1;
var fibString = 'Fibonacci Sequence: 1, 1';
var fibCn = 2;
for(var i = 2; i < fibNum; i++) {
fibArr[i]=fibArr[i-1]+fibArr[i-2];
fibString = fibString + ', ' + fibArr[i];
fibCn += fibArr[i];
}
var fibSum = 'Sum: ' + fibCn;
var total = fibString + ' ' + fibSum;
Do all of the people posting their O(N) solution for the nth Fibonacci number know that there is a closed form for the nth Fibonacci number that uses the Golden Ratio. The nth Fibonacci can be computed in O(1) using this.
this is the fibonacci programm in vb for an consoleapplication
Module Module1
Sub Main()
Do
Dim zähler As ULong = 2
Dim index As ULong = 1
Dim zwischenspeicher As ULong
Dim fm1 As ULong = 1
Dim limit As ULong
Console.WriteLine("Write the limit, until wich number it should be calculated.")
Do
Try
limit = Console.ReadLine()
Exit Do
Catch
Console.WriteLine("Please write a number greater or equal to 0")
End Try
Loop
Console.WriteLine("The value of fib 1 is 1")
Try
Do Until index > limit
Console.WriteLine("The value of fib " & zähler & " is " & index)
zwischenspeicher = fm1 + index
fm1 = index
index = zwischenspeicher
zähler = zähler + 1
Loop
Catch ex As Exception
Console.WriteLine("Error:")
Console.WriteLine(ex.Message)
End Try
Loop
End Sub
End Module
+AchDeFuckLP i keep getting an error at line 3 char 18
Saying the Fibonacci sequence is recursive is a little misleading. That is, on a Turing machine, the operation would be fine, but in reality, when you get up to the 50th or so number, it begins to call the function far too many times, looking for answers it's already computed an upteenth number of times. I believe it's an O(n^n) function.
By storing results in an array, you can decrease the running time to O(1), which is so infinitely better. It's the difference between a microprocessor and a supercomputer.
It being recursive has nothing to do with the capabilities of computers, but with how it is defined.
Also it can easily be calculated in linear time. O(1) can only be achieved, if the array is filled beforehand or if you use the formula (((1+sqrt(5))/2)^n+((1-sqrt(5))/2)^n)/sqrt(5).
Edit: The other answers weren't shown to me before oO
I think the answer is in maths. As Fibonacci sequence is a recurrent sequence of order 2 you can in fact simplify it's expression by something which looks like Un = A.(r1)^n + B.(r2)^n ; r1,r2 being the roots of the r^2=r+1 equation(fibonacci recurrence definition) which is r^2-r-1=0. A and B are factors that depends on the initial values of the sequence. Here U(0)=1 and U(1)=1. It is in fact similar to solving a differential equation in the end.
I think a small error slipped into this video.
You can write every recursive function without using recursion. However for some functions simple for-loops are not powerful enough.
Simple for-loops meaning, that they can only loop a finite number of times.
I'm not sure for all languages, but you can't do recursion forever either.
Python for instance will return RuntimeError: maximum recursion depth exceeded after 995 recursions.
I actually love "boring" courier
hello
OI! dont go dissing comic sans when in the recursive videos one of those n's was comic sans . . . but ye, comic sans . . . .
The question is: Just by watching this video, can you determine if Computerphile will ever stop making videos about recursion?
I can't understand, that every time the faculty and the fibonacci secence is used to explain recussion. At higher n this way is way too slow and most times impossible. Only a memoized recursion can slightly beat the iterative solution, because, it is basically the same. But there are better examples like the Euler Tour, actually recursion is extremly important for graphs, more examples in this directions please. Because what should I do with a simple recursion that didn't allow me to compute fac(100) or fib(55) because the recursion depth is way to deep for normal computers.
Yeah, I was surprised he didn't even talk about that. By the way, strictly speaking it's more the breadth of the recursion than its depth that's the issue here
fibonacci easy as 1,1,2,3
um, is this java? i think i need a comment for a code in javascript, but ya ill make one dont worry :)
Python FTW! :)
def fib(n):
if n < 0 or type(n) != int: raise ValueError
if n < 3: return int(bool(n))
return fib(n-1) + fib(n-2)
0:16 Printed Math code turns me on.
laik
that seems like an awful amount of code to produce fibonacci. This is in R
fiboSeq
Got a little programing challenge for anyone interested.
You have to find a way to swap the values of two integers. Sounds simple doesn't, But the catch is you can't use a third temporary integr.
Trivial. Let a and b be two integers.
a *= b;
b = a/b;
a = a/b;
x
works with xor, too
Before I try this, I need to ask: is this possible?
There are two perfectly functional solutions above your comment.
Ok, maybe this would have been the place to put 'Puff the Fractal Dragon', but it's a little late now.
de-re-cursed :)
i dont comment much but Professor Brailsford has to be related to hannibal lecter
I have an itchy Fibonacci
fib 10 = 55 ; 5+5 = 10 ... just saying
3rd oooooooooooooooooooo
So I've skipped a couple a episodes. Has Brady lost a tremendous amount of weight or was he abducted by aliens and replaced by a lousy replica? (In other words: Who the hell is the guy in the end of the video?)
Fizzbuzznacci