Serving the Quantitative Finance Community

 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Compute the Nth Fibonacci nr using only + and *

May 7th, 2015, 3:53 pm

QuoteOriginally posted by: CuchulainnQuoteOriginally 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 = ?1&2. Although F0 and F1 might be fixed for classic Fibonacci, what if you have some AR-like process that posits that the future state of the system is a weighted linear sum of the previous states of the system. One might be doing an MC of millions or billions of starting values for F0 and F1 and desire a fast calculation of FN.3. n might be quite large, millions, billions, or trillions and only be concerns with parts of the bit pattern of a Fibonacci-like process rather than the entire value.This brainteaser is only irrelevant in the strictest sense of the Fibonacci numbers. Many other systems have a recursive structure that is like the Fibonacci system.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Compute the Nth Fibonacci nr using only + and *

May 9th, 2015, 8:33 am

QuoteThis brainteaser is only irrelevant in the strictest sense of the Fibonacci numbers. Many other systems have a recursive structure that is like the Fibonacci system. irrelevant or do you mean relevant?BTW Fibonacci can be done solely with Pascal's triangle and '+'. We can then have the no true Scotman's question; how efficient is it?
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Compute the Nth Fibonacci nr using only + and *

May 9th, 2015, 1:07 pm

QuoteOriginally posted by: CuchulainnQuoteThis brainteaser is only irrelevant in the strictest sense of the Fibonacci numbers. Many other systems have a recursive structure that is like the Fibonacci system. irrelevant or do you mean relevant?BTW Fibonacci can be done solely with Pascal's triangle and '+'. We can then have the no true Scotman's question; how efficient is it?"Irrelevant " My comments were in reply to some earlier comments that seemed to question the relevance of this brainteaser's task because the basic Fibonacci algorithm is very fast and there's only 92 Fibonacci numbers in 64-bit integers.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Compute the Nth Fibonacci nr using only + and *

May 9th, 2015, 6:34 pm

QuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: CuchulainnQuoteThis brainteaser is only irrelevant in the strictest sense of the Fibonacci numbers. Many other systems have a recursive structure that is like the Fibonacci system. irrelevant or do you mean relevant?BTW Fibonacci can be done solely with Pascal's triangle and '+'. We can then have the no true Scotman's question; how efficient is it?"Irrelevant " My comments were in reply to some earlier comments that seemed to question the relevance of this brainteaser's task because the basic Fibonacci algorithm is very fast and there's only 92 Fibonacci numbers in 64-bit integers.I thought OP was QuoteA naive algorithm would consecutively sum the two previous numbers N times, i.e. the algorithm is O(N). Can you do it faster than that?Remember, you can't use the sqrt function, only + and *
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Compute the Nth Fibonacci nr using only + and *

May 9th, 2015, 8:57 pm

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: Traden4AlphaQuoteOriginally posted by: CuchulainnQuoteThis brainteaser is only irrelevant in the strictest sense of the Fibonacci numbers. Many other systems have a recursive structure that is like the Fibonacci system. irrelevant or do you mean relevant?BTW Fibonacci can be done solely with Pascal's triangle and '+'. We can then have the no true Scotman's question; how efficient is it?"Irrelevant " My comments were in reply to some earlier comments that seemed to question the relevance of this brainteaser's task because the basic Fibonacci algorithm is very fast and there's only 92 Fibonacci numbers in 64-bit integers.I thought OP was QuoteA naive algorithm would consecutively sum the two previous numbers N times, i.e. the algorithm is O(N). Can you do it faster than that?Remember, you can't use the sqrt function, only + and * Yes, that was the OP. This was in reply to subsequent discussion about an O(1) solution of a look-up table because the number of Fibonacci numbers is so small they can be pre-computed, stored, and looked up. An M-bit integer encompasses O(M) Fibonacci numbers so for most integer ranges that most applications would work with, a pre-computed table is the most efficient solution.
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Compute the Nth Fibonacci nr using only + and *

May 10th, 2015, 10:58 am

QuoteOriginally posted by: outrunThank you. I'm now requesting the jury to take all evidence into consideration in this very complicated matter and form a judgement about the validity of the discussion-references and all indirect references therein.Can the jury decide this is less than O(N) time?
 
User avatar
Traden4Alpha
Posts: 3300
Joined: September 20th, 2002, 8:30 pm

Compute the Nth Fibonacci nr using only + and *

May 10th, 2015, 11:21 am

Technically, none of the proposed methods is actually as fast as it seems. The cited time complexities only work for bounded N. Both addition and multiplication require increasing time complexity for increasing bit-length numbers and the The bit length of FN grows O(N). Addition is O(N) and multiplication depends on the algorithm (which might be as fast as M(N) = O(N log N log log N) ). The Pascal triangle method would thus grow O(N^3) and the recursive algorithm would be O(M(N) log n) which is faster than O(N log N).No solutions so far meet the OP's requirements of faster than O(N) time.
 
User avatar
katastrofa
Posts: 7440
Joined: August 16th, 2007, 5:36 am
Location: Alpha Centauri

Re: Compute the Nth Fibonacci nr using only + and *

June 1st, 2021, 9:31 pm

Variation on Fibonacci sequence where a_n+1 is the sum of two of the preceding n Fibonacci numbers drawn with probability 1/n. It's a terribly insightful result, also for finance people with their Markovian models, I think...