 Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

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

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

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?
My C++ Boost code gives
262537412640768743.999999999999250072597198185688879353856337336990862707537410378210647910118607313

http://www.datasimfinancial.com
http://www.datasim.nl Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

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

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

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 *
My C++ Boost code gives
262537412640768743.999999999999250072597198185688879353856337336990862707537410378210647910118607313

http://www.datasimfinancial.com
http://www.datasim.nl Posts: 23951
Joined: September 20th, 2002, 8:30 pm

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

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

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

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

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

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.  