QuoteOriginally posted by: outruna blog post about thisI liked this, though ellipses are optimun, not circles

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

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

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.

- Traden4Alpha
**Posts:**23951**Joined:**

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.

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:**62410**Joined:****Location:**Amsterdam-
**Contact:**

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.

- Cuchulainn
**Posts:**62410**Joined:****Location:**Amsterdam-
**Contact:**

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.

- Cuchulainn
**Posts:**62410**Joined:****Location:**Amsterdam-
**Contact:**

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.

GZIP: On