Serving the Quantitative Finance Community

 
User avatar
ExSan
Posts: 493
Joined: April 12th, 2003, 10:40 am

Compute the Nth Fibonacci nr using only + and *

April 4th, 2015, 10:46 am

QuoteOriginally posted by: outruna blog post about thisI liked this, though ellipses are optimun, not circles
°°° About ExSan bit.ly/3U5bIdq °°°
 
User avatar
ExSan
Posts: 493
Joined: April 12th, 2003, 10:40 am

Compute the Nth Fibonacci nr using only + and *

April 4th, 2015, 11:40 am

QuoteOriginally posted by: outrunQuoteOriginally posted by: ExSanQuoteOriginally posted by: outruna blog post about thisI liked this, though ellipses are optimun, not circlesPolytope is even smaller :D Didn't we discuss the ellipses a long time ago?yeap, we did
°°° About ExSan bit.ly/3U5bIdq °°°
 
User avatar
AVt
Posts: 90
Joined: December 29th, 2001, 8:23 pm

Compute the Nth Fibonacci nr using only + and *

April 6th, 2015, 6:51 pm

Hm ... I do not quite understand "O(n)": there are only few such numbers (*) in "usual" programs. So why not simply store them?(*) 46 for type int (1 more for unsigned int), 92 for type __int64
 
User avatar
AVt
Posts: 90
Joined: December 29th, 2001, 8:23 pm

Compute the Nth Fibonacci nr using only + and *

April 6th, 2015, 7:10 pm

One can compute them quickly (even by recursion) by the methods already discussed. However O(n) means "large n". This is what I do not understand.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Compute the Nth Fibonacci nr using only + and *

April 6th, 2015, 9:14 pm

It may be true that the Fibonacci numbers (especially the ones that fit in workaday data types) are easy to calculate or store in a LUT.1. What if you need Fn calculated a great many times, but for arbitrary n and varying floating point F0 and F1?2. What if you need variants of the Fibonacci progression with different coefficients on the sum: Fn+1 = c1*Fn + c2*Fn-1?3. What if you need Fn for extremely high n for some unusual crypto algorithm (e.g., the Fibonacci-number bits of the U[1,000,000,000] Fibonacci number)?The point is that this can be a more general method for approaching recursive series. Fibonacci is just the simple exemplar.
 
User avatar
AVt
Posts: 90
Joined: December 29th, 2001, 8:23 pm

Compute the Nth Fibonacci nr using only + and *

April 7th, 2015, 6:52 pm

Yes, complexity (I lurked it up, the naive way is O(N^2), no?). But which magnitude of N you have in mind for an application (since for the usual settings it does not matter)? Or is it a 'theoretical' question?PS: 1) analytical as well and 3) well ...
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Compute the Nth Fibonacci nr using only + and *

April 9th, 2015, 8:57 am

QuoteOriginally posted by: outrunThis is a good competitor IMO. I have a generic lattice in C++ for binomial/trinomial option pricing. I want to do a stress test and one idea I had was to create a large Pascal triangle, which I did. This is a super-user data. Now I can take views such as polygonal, Fibonacci numbers which involved nothing more than + and certainly not * nor SQRT.Even Sierpinski's triangle can be generated but my time is limited for hobbies at the moment. But a lot of stuff can be stored in and extracted from Pascal triangle. It's cool.Pascal rocks!I used nested STL vectors and they work fine for my purposes.Complexity?
Last edited by Cuchulainn on April 8th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Compute the Nth Fibonacci nr using only + and *

May 7th, 2015, 2:36 pm

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: outrunThis is a good competitor IMO. Update: If we take the creation of Pascal's triangle out of the discussion (create once, it is a once-off tax write off), we generate Fibonacci using only +). Also binomiial coefficients are a piece of cake:
Last edited by Cuchulainn on May 6th, 2015, 10:00 pm, edited 1 time in total.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Compute the Nth Fibonacci nr using only + and *

May 7th, 2015, 2:54 pm

QuoteOriginally posted by: Traden4AlphaIt may be true that the Fibonacci numbers (especially the ones that fit in workaday data types) are easy to calculate or store in a LUT.1. What if you need Fn calculated a great many times, but for arbitrary n and varying floating point F0 and F1?2. What if you need variants of the Fibonacci progression with different coefficients on the sum: Fn+1 = c1*Fn + c2*Fn-1?3. What if you need Fn for extremely high n for some unusual crypto algorithm (e.g., the Fibonacci-number bits of the U[1,000,000,000] Fibonacci number)?The point is that this can be a more general method for approaching recursive series. Fibonacci is just the simple exemplar.1. F0 and F1 are non-negotiable (== 1 whatever)?2. A generalized Pascal's triangle? (* is redundant in general IMO). (x + c1)^n .. Tribonacci, Tetranacci ..3 n = ?
Last edited by Cuchulainn on May 6th, 2015, 10:00 pm, edited 1 time in total.