 ExSan
Posts: 4550
Joined: April 12th, 2003, 10:40 am

### Compute the Nth Fibonacci nr using only + and * ExSan
Posts: 4550
Joined: April 12th, 2003, 10:40 am

### Compute the Nth Fibonacci nr using only + and *

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 Didn't we discuss the ellipses a long time ago?yeap, we did AVt
Posts: 1074
Joined: December 29th, 2001, 8:23 pm

### Compute the Nth Fibonacci nr using only + and *

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 AVt
Posts: 1074
Joined: December 29th, 2001, 8:23 pm

### Compute the Nth Fibonacci nr using only + and *

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. Posts: 23951
Joined: September 20th, 2002, 8:30 pm

### Compute the Nth Fibonacci nr using only + and *

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. AVt
Posts: 1074
Joined: December 29th, 2001, 8:23 pm

### Compute the Nth Fibonacci nr using only + and *

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 ... Cuchulainn
Posts: 61185
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Compute the Nth Fibonacci nr using only + and *

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.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget Cuchulainn
Posts: 61185
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Compute the Nth Fibonacci nr using only + and *

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.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget Cuchulainn
Posts: 61185
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

### Compute the Nth Fibonacci nr using only + and *

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.
http://www.datasimfinancial.com
http://www.datasim.nl

Every Time We Teach a Child Something, We Keep Him from Inventing It Himself
Jean Piaget  