Serving the Quantitative Finance Community

 
User avatar
zumsel
Topic Author
Posts: 0
Joined: June 2nd, 2015, 4:16 pm

Highest Fibonacci number that can be computed recursively

June 3rd, 2015, 9:19 am

The following is a question I was asked in an interview with a quantitative hedge fund. I'm wondering how good/correct my answer was and what a better answer would have looked like. Note that I didn't have a calculator at hand, so all the estimates are very rough. The interview was for a Quantitative Analyst position and my background is physics, so they probably didn't expect me to be an expert, but rather to show some basic understanding.Question: Write a program that recursively calculates the Fibonacci numbers and estimate how many of the Fibonacci numbers can be calculated with your program.My answer (using C++):int fib (int n) { return n<=1 ? n : fib(n-2)+fib(n-1);}I can think of three limitations: integer overflow, computation time, and stack overflow. Let's estimate the upper bound on n due to each of these factors.Integer overflow: We know that fib(n)~1.6^n. An integer typically has 4 bytes, so MAX_INT=2^(4*8-1)-1. Solving 1.6^n~2^31 gives n~31*log(2)/log(1.6)~45. Obviously, this bound could be increased by using long instead of int.Computation time: The number of recursions necessary to compute fib(n) is ~fib(n). Elementary operations are performed with GHz frequency. Let's say we want to wait at most 10^3s (~15mins). The number of elementary operations we can perform in this time is 10^3s*GHz=10^12. Solving fib(n)~1.6^n~10^12 gives n~12*log(10)/log(1.6)~60.Stack overflow: We need ~fib(n) recursions. Each recursion needs some tens of bytes (??) of stack space. Stack size is typically 1MB. Solving fib(n)*10bytes~1MB gives 1.6^n~10^5 or n~5*log(10)/log(1.6)~25.In conclusion, it seems that stack size puts the most stringent bound on n, and we can only compute ~25 Fibonacci numbers in this way.
 
User avatar
bearish
Posts: 5186
Joined: February 3rd, 2011, 2:19 pm

Highest Fibonacci number that can be computed recursively

June 3rd, 2015, 10:25 am

As an empirical matter (I was curious) I can report that VBA for Excel can cope with fib(40), but that took a couple of minutes to return. It seems plausible that space will be more constraining than time in C++.
 
User avatar
zumsel
Topic Author
Posts: 0
Joined: June 2nd, 2015, 4:16 pm

Highest Fibonacci number that can be computed recursively

June 4th, 2015, 1:35 pm

Some updates from actually running the program:The number of calls to fib necessary to calculate fib(n) is 2*fib(n+1)-1, fib(n+1) of which are leaves. The proof is left as an exercise for the reader.The highest number which is calculated correctly is fib(46)~10^9, which takes 22s. So my estimate regarding integer overflow was very good, and the computation time is compatible with elementary operations being performed with GHz frequency.However, there has to be a serious flaw with the estimate regarding stack overflow. I'm grateful for any help.
Last edited by zumsel on June 3rd, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Highest Fibonacci number that can be computed recursively

June 4th, 2015, 1:44 pm

QuoteOriginally posted by: zumselSome updates from actually running the program:The number of recursions necessary to calculate fib(n) is 2*fib(n+1)-1, fib(n+1) of which are leaves. The proof is left as an exercise for the reader.The highest number which is calculated correctly is fib(46)~10^9, which takes 22s. So my estimate regarding integer overflow was very good, and the computation time is compatible with elementary operations being performed with GHz frequency.However, there has to be a serious flaw with the estimate regarding stack overflow. I'm grateful for any help.Couple of possibilities: 1) the default stack size varies by complier and environment; 2) the run-time behavior might not spawn all O(fib(n) recursions all at once -- a depth-first invocation of the branches of the recursion tree would only need a stack depth of O(n).
 
User avatar
zumsel
Topic Author
Posts: 0
Joined: June 2nd, 2015, 4:16 pm

Highest Fibonacci number that can be computed recursively

June 4th, 2015, 1:55 pm

Thanks.I checked for 1) with a functionvoid foo (int n) { if (n == 0) cout << "hello world\n"; else return foo(n-1);}I get an output up to n~300k, compatible with stacksize being megabytes.So I guess it's your answer 2).
 
User avatar
AVt
Posts: 90
Joined: December 29th, 2001, 8:23 pm

Highest Fibonacci number that can be computed recursively

June 4th, 2015, 6:16 pm

The following will do up to n=73 in VBA (and n=78 in C /double precision) almost immediately
 
User avatar
zumsel
Topic Author
Posts: 0
Joined: June 2nd, 2015, 4:16 pm

Highest Fibonacci number that can be computed recursively

June 5th, 2015, 7:39 am

Yes, obviously fib(n) can be calculated in O(n) time, but that was not the point of the question.
 
User avatar
AVt
Posts: 90
Joined: December 29th, 2001, 8:23 pm

Highest Fibonacci number that can be computed recursively

June 5th, 2015, 8:30 pm

That code needs some micro seconds and some dozens floats, using a table. No real need for more for this kind of recursion.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Highest Fibonacci number that can be computed recursively

June 6th, 2015, 10:08 am

QuoteOriginally posted by: AVtThat code needs some micro seconds and some dozens floats, using a table. No real need for more for this kind of recursion.You are entirely right that recursion is a slow way to compute fib. But the point of the question is not "how do we make fib go fast" but "what limits the max N for a recursive algorithm such as fib"?
Last edited by Traden4Alpha on June 5th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20253
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Highest Fibonacci number that can be computed recursively

June 6th, 2015, 11:20 am

QuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: AVtThat code needs some micro seconds and some dozens floats, using a table. No real need for more for this kind of recursion.You are entirely right that recursion is a slow way to compute fib. But the point of the question is not "how do we make fib go fast" but "what limits the max N for a recursive algorithm such as fib"?Is it not a question of finding N such thatFib(N) = MAX where MAX is some value?(?) You can use Newton-Raphson? You could use the analytic formula for Fib(N).BTW strictly speaking, Fib is iterative, not recursive. An implementation could be recursive, but not necessarily.// Fibonacci never fails to fascinate.
Last edited by Cuchulainn on June 5th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Highest Fibonacci number that can be computed recursively

June 6th, 2015, 11:51 am

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: AVtThat code needs some micro seconds and some dozens floats, using a table. No real need for more for this kind of recursion.You are entirely right that recursion is a slow way to compute fib. But the point of the question is not "how do we make fib go fast" but "what limits the max N for a recursive algorithm such as fib"?Is it not a question of finding N such thatFib(N) = MAX where MAX is some value?(?) You can use Newton-Raphson? You could use the analytic formula for Fib(N).BTW strictly speaking, Fib is iterative, not recursive. An implementation could be recursive, but not necessarily.// Fibonacci never fails to fascinate.Only the interviewer knows exactly WHY they asked the question but they explicitly asked for a recursive implementation of Fib and the maximum value of N, not the maximum value of fib(N) that the interviewee's recursive implementation is capable of. I like the OP's answer which posits three possible phenomena that could impose an upper bound on N: integer overflow, computation time, and stack overflow.
 
User avatar
Cuchulainn
Posts: 20253
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Highest Fibonacci number that can be computed recursively

June 6th, 2015, 12:34 pm

Quotethey explicitly asked for a recursive implementation of Fib and the maximum value of N, not the maximum value of fib(N) That was my understanding as well.So, N is the output, yes?
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Highest Fibonacci number that can be computed recursively

June 6th, 2015, 12:40 pm

QuoteOriginally posted by: CuchulainnQuotethey explicitly asked for a recursive implementation of Fib and the maximum value of N, not the maximum value of fib(N) That was my understanding as well.So, N is the output, yes?Yes, N is the output if by "output" you mean the value returned by the metafuction: NumberOfFibNumbersCalculated(YourRecursiveFibImplementation())
Last edited by Traden4Alpha on June 5th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
DominicConnor
Posts: 41
Joined: July 14th, 2002, 3:00 am

Highest Fibonacci number that can be computed recursively

June 7th, 2015, 11:18 am

Yes, this is mildly common interview question, usually asked in the context of:Write a function to calculate N! recursively.Then they ask:Do it for FibThe hole many candidates fall in is the one zumsl the original poster seems to have found (but possibly not fallen into).like any good interview question and like any recurive exploration of a domain, it can go deep in several directions.The correct answer is of course an O(N) recursion, which is a good trick, but zumsel is looking at tech limits...It is always worth remembering (and in an interivew saying out loud) that recursion is an illusion, that computers simply can't do itand emulate "recursion" by a form of iteration where much of the book keeping effort like managing multiple instances of a a stack variable with the same name are done for you. It follows that anything that can be done recursively may be done iteratively since it is being done iteratively. The difference is notational convenience, which is an important thing in expressing yourself to a computer, but ultimately is just syntactic sugar.May people believe stack size is a function of the memory of the computer it is running on, which is very rarely the case.C++ compilers allow you to set a max stack size for various reasons, one of which is that if you allow a function to recurse forever, it will use up all virtual memory and the system will either go so slowly it looks like it has crashed or simply crash.Other languages either follow the C/C++ convention or set it in a way you can't change or of course just let hte system consume itself.In C++, the exact semantics of f(n-1) + f (n-2) are tightly defined, which means that some of the obvious optimisaitons may not happen, functional languages may not be, so the calculation will not necessarily take the number of steps or depth of recursion you might think.