FIBONACCI

=FIBONACCI(n)
n
integer, the nth term of the sequence
calculates the nth term of a Fibonacci sequence
Xlambda

Xlambda

Well-known Member
Joined
Mar 8, 2021
Messages
837
Office Version
  1. 365
Platform
  1. Windows
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)))
Excel Formula: 
=LAMBDA(n,IF(n<3,1,FIBBONACCI(n-1)+FIBONACCI(n-2)))
LAMBDA 6.0.xlsx
ABCDEFGH
1FIBONACCIrecursiveckeck(non recursive)
2n value=FIBONACCI(B3)=FIB(B3)time(can use phone's stopwatch)
315610610instant
41825842584instant
52067656765instant
6308320408320401s
73592274659227465?sshare this
8383908816939088169?svalues
940102334155102334155?swith us ?
10
FIBONACCI post
Cell Formulas
RangeFormula
C2:D2C2=FORMULATEXT(C3)
C3:C9C3=FIBONACCI(B3)
D3:D9D3=FIB(B3)
 
Upvote 0
Hey, Cesar, that you? :)
 
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.
 
Last edited by a moderator:
GeertD said:
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.
Click to expand...
PS: strangely this web interface does not allow for maths notation very well:
  • (n) stands for ( n )
 
Welcome to the MrExcel Message Board, @GeertD!

GeertD said:
PS: strangely this web interface does not allow for maths notation very well:
Click to expand...
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]
Click to expand...

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.
 
smozgur said:
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.
Click to expand...
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.)
 
GeertD said:
(It would also be a benefit if I were able to edit my own posts to solve or work around the issues I encounter.)
Click to expand...
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.
 
Last edited:
smozgur said:
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.
Click to expand...
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. ;)
 
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)
 
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?
 
You must log in or register to reply here.

Forum statistics

Threads
1,216,499
Messages
6,131,012
Members
449,613
Latest member
MedDash99

Share this page

We've detected that you are using an adblocker.

We have a great community of people providing Excel help here, but the hosting costs are enormous. You can help keep this site running by allowing ads on MrExcel.com.
Allow Ads at MrExcel

Which adblocker are you using?

Disable AdBlock

Follow these easy steps to disable AdBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the icon in the browser’s toolbar.
2)Click on the "Pause on this site" option.
Go back

Disable AdBlock Plus

Follow these easy steps to disable AdBlock Plus

1)Click on the icon in the browser’s toolbar.
2)Click on the toggle to disable it for "mrexcel.com".
Go back

Disable uBlock Origin

Follow these easy steps to disable uBlock Origin

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back

Disable uBlock

Follow these easy steps to disable uBlock

1)Click on the icon in the browser’s toolbar.
2)Click on the "Power" button.
3)Click on the "Refresh" button.
Go back
Back
Top