FIBONACCI

[Xlambda]

FIBONACCI !! recursive !! calculates the nth term of the famous Fibonacci sequence . This is more of a fun quest than a useful function. ( did this on a YT channel also, had fun with Rico about this).
This reflects how limited our computers are. You will be surprised. This time is not about recursion "iterations" limit, is about the limit of the number of calculations that a computer can perform.
Open a new workbook, define the lambda FIBONACCI. Very important, first, try values of n less then 20!! . Call FIBONACC(15) ...(19) ..etc. and increase it bit by bit.
For what number "n" do you think that your computer will start struggling giving you the answer?? Share with us here, if you please, how long it took your computer to calculate FIBONACCI(35)..(38) and (40). Eventually what type of computer you are using. Processor ,RAM etc. After all, 40 is a very small number.? Give it a try!!
Note: Fibonacci sequence is this one : 1,1,2,3,5,8,13,21,34,55,89,144....the value of n term is the sum of the previous 2 terms fib( n)=fib(n-1) + fib(n-2), and fib(1)=1,fib(2)=1
Fortunately , Fibonacci has also an explicit solution (non recursive), you can define another lambda to check the results FIB( n)=LAMBDA( n,LET(a,SQRT(5),x,((1+a)/2)^n,y,((1-a)/2)^n,1/a*(x-y)))

=LAMBDA(n,IF(n<3,1,FIBBONACCI(n-1)+FIBONACCI(n-2)))

LAMBDA 6.0.xlsx
	A	B	C	D	E	F	G	H
1	FIBONACCI		recursive	ckeck(non recursive)
2		n value	=FIBONACCI(B3)	=FIB(B3)	time(can use phone's stopwatch)
3		15	610	610	instant
4		18	2584	2584	instant
5		20	6765	6765	instant
6		30	832040	832040	1s
7		35	9227465	9227465	?s	share this
8		38	39088169	39088169	?s	values
9		40	102334155	102334155	?s	with us ?
10
FIBONACCI post

Cell Formulas
Range	Formula
C2:D2	C2	=FORMULATEXT(C3)
C3:C9	C3	=FIBONACCI(B3)
D3:D9	D3	=FIB(B3)

 

[GeertD]

Hey, Cesar, that you?

 

[GeertD]

General warning: don't take the bait of this this challenge: it's a trap!
[...looking for my notes made in the context of a previous interaction...]

Explanation:

• Because the recursive formula for the Fibonacci numbers calls itself *twice* (asymmetrically) on every recursive iteration, this formula is highly inefficient.
• The emphasis here is on the word "twice", as in: "more than once".
• If you take a single function call as a unit of computational effort, the total computational effort for calculating the Fibonacci numbers recursively, can be expressed as a Fibonacci number itself.
• My maths findings are this: fc(n) = 2*F(n)-1.
• in other words the computational effort fc(n) to calculate the n-th Fibonacci number F(n) is equal to twice the corresponding Fibonacci number itself (minus 1).
• and since the sequence of Fibonacci numbers itself is a quickly diverging sequence, the effort for computing it recursively is even more diverging.

Conclusion:

• don't use this kind of recursive formula's.
• recursive formula's that call themselves only once should be fine.

 

[GeertD]

General warning: don't take the bait of this this challenge: it's a trap!
[...looking for my notes made in the context of a previous interaction...]

Explanation:

• Because the recursive formula for the Fibonacci numbers calls itself *twice* (asymmetrically) on every recursive iteration, this formula is highly inefficient.
• The emphasis here is on the word "twice", as in: "more than once".
• If you take a single function call as a unit of computational effort, the total computational effort for calculating the Fibonacci numbers recursively, can be expressed as a Fibonacci number itself.
• My maths findings are this: fc = 2*F-1.
• in other words the computational effort fc to calculate the n-th Fibonacci number F is equal to twice the corresponding Fibonacci number itself (minus 1).
• and since the sequence of Fibonacci numbers itself is a quickly diverging sequence, the effort for computing it recursively is even more diverging.

Conclusion:

• don't use this kind of recursive formula's.
• recursive formula's that call themselves only once should be fine.

PS: strangely this web interface does not allow for maths notation very well:

• stands for ( n )

 

[smozgur]

Welcome to the MrExcel Message Board, @GeertD!

PS: strangely this web interface does not allow for maths notation very well:

That's correct. It is because of the BB codes that are used for smilies. However, you can solve it by using the plain tag as below:

• My maths findings are this: fc(n) = 2*F(n)-1.

I just wrapped the formula section by using the plain tag as shown below.

My maths findings are this: [plain]fc(n) = 2*F(n)-1[/plain]

This way, the n between parentheses won't be rendered as a special emoji code.

I just fixed your post to apply this, so it should look ok now.

 

[GeertD]

Welcome to the MrExcel Message Board, @GeertD!


That's correct. It is because of the BB codes that are used for smilies. However, you can solve it by using the plain tag as below:

• My maths findings are this: fc(n) = 2*F(n)-1.

I just wrapped the formula section by using the plain tag as shown below.


This way, the n between parentheses won't be rendered as a special emoji code.

I just fixed your post to apply this, so it should look ok now.

You, sir, have magic powers!
Thank you for your Devine intervention.
I'll try my best to remember your -trick.
(It would also be a benefit if I were able to edit my own posts to solve or work around the issues I encounter.)

 

[smozgur]

(It would also be a benefit if I were able to edit my own posts to solve or work around the issues I encounter.)

You can, for 10 minutes after the initial submission due to certain limitations in the forum. Every thread has its own chronological order, and the discussion could be hard to follow if previous posts are edited freely. Next posts sent as a reply to a previous post, then the previous post is changed to say something entirely opposite tomorrow, etc.
(Personally, I don't even understand why edit action is ever considered a public privilege in the forum software development world.)

If you ever make a mistake that must be corrected in any of your posts, then you can simply click on the Report button at the bottom of the post, and explain the problem. A moderator will help to fix it.

 

[GeertD]

You can, for 10 minutes after the initial submission due to certain limitations in the forum. Every thread has its own chronological order, and the discussion could be hard to follow if previous posts are edited freely. Next posts sent as a reply to a previous post, then the previous post is changed to say something entirely opposite tomorrow, etc.
(Personally, I don't even understand why edit action is ever considered a public privilege in the forum software development world.)

If you ever make a mistake that must be corrected in any of your posts, then you can simply click on the Report button at the bottom of the post, and explain the problem. A moderator will help to fix it.

Thanks for your reply. I understand your concern.
I guess I'm not used to moderated message boards. As a Facebook and YouTube commenter I'm used to fend for myself – in relative independence.
I have the habit of self-moderating my own posts in all personal integrity – no hiding behind fake pseudonyms and all that.
I will adapt. resistance is futile.

 

[Xlambda]

Hi Geert, now you have scared everybody out with the "trap" word. ??. Is no trap. Is fun to see how different computers get different timing results and how these results are proportional with computer power.
PS. to get rid of the emoji you can insert a space f( n) like I did.
What are your computer timing results for FIBONACCI(35)..(38) ..(40) ? Share this. ?
setting a counter inside the formula, nr. of calculations that computer does (or how many times the function is called) is as follows
n = 30 => 2692538 times
n = 31 => 4356618 times
n = 42 => 866988874 times (2^n-C)

 

[GeertD]

Hi Cesar,
Sorry, if I scared everybody off. It was intended as a bit of a funny remark, hence the wink .
Anyway, here are some calculation times for my computer:

• F(35) => 8.5 à 8.7 seconds
• F(40) => 106 à 108 seconds

I used the FastExcel V4 Calculation Manager for timing this.
I don't think the CPU, RAM, etc. is all that important, because my PC used less than 1 core for this and far less memory than is present in any modern computer.
I think my computer did average.

What about yours?