SERVING THE QUANTITATIVE FINANCE COMMUNITY

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

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

Yes, there certainly are solutions to this problem using +, and *. The funny part was the unstated requirement of doing it in integers and the notion that the problem poser had a very specific means-of-solution in mind and would not accept solutions that meant the original requirements.A secondary issue is that although the solution can be written in various programming languages with various degrees of terseness and elegance, the problem statement was written in English. Why can't we state problems in the same language that we state the solutions?Will programming languages always be second-class languages as long as one still needs English in order to define the problem?

Cuchulainn
Posts: 61185
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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

QuoteOriginally posted by: Traden4AlphaYes, there certainly are solutions to this problem using +, and *. The funny part was the unstated requirement of doing it in integers and the notion that the problem poser had a very specific means-of-solution in mind and would not accept solutions that meant the original requirements.A secondary issue is that although the solution can be written in various programming languages with various degrees of terseness and elegance, the problem statement was written in English. Why can't we state problems in the same language that we state the solutions?Will programming languages always be second-class languages as long as one still needs English in order to define the problem?OP was probably obsessed/concerned with performance. Implicit requirement. Aka Requirements Elicitation, that's life.Mathematically, output is an integer, so sqrt(5) is an aberration.Anyways, the problem can be done with integers. QuoteWill programming languages always be second-class languages as long as one still needs English in order to define the problem?In that sense, yes. But its' a wee bit navel-gazing.
Last edited by Cuchulainn on February 2nd, 2015, 11: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 *

And this solution is explicitly computable in integer arithmetic QuoteF_n = (m1^n - m2^n)/sqrt(5) (1)
Last edited by Cuchulainn on February 2nd, 2015, 11: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

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

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

QuoteOriginally posted by: outrunFor sure.. Surely.. No? ... Whatever...Just show us the solution: only *,+ and in log(n)!**) exclamation point, not factorial.!*) see above\*) note indicator, not multiplication sign\\) escape characterHAHAHAHAHAHA!!!! (yes, factorial^4th)That was one thing I liked about APL -- the special character set reduced the problem of programming vs. speaking language character ambiguities.

Cuchulainn
Posts: 61185
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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

QuoteWhat's that ^ and / ?Power and division. But don't compute it that way. Use the fact m1 = (1+sqrt(5))/2. m2 = (1-sqrt(5))/2and binomial and see which terms drop off.
http://www.datasimfinancial.com
http://www.datasim.nl

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

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

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

QuoteOriginally posted by: CuchulainnQuoteOriginally posted by: Traden4AlphaYes, there certainly are solutions to this problem using +, and *. The funny part was the unstated requirement of doing it in integers and the notion that the problem poser had a very specific means-of-solution in mind and would not accept solutions that meant the original requirements.A secondary issue is that although the solution can be written in various programming languages with various degrees of terseness and elegance, the problem statement was written in English. Why can't we state problems in the same language that we state the solutions?Will programming languages always be second-class languages as long as one still needs English in order to define the problem?OP was probably obsessed/concerned with performance. Implicit requirement. Aka Requirements Elicitation, that's life.Mathematically, output is an integer, so sqrt(5) is an aberration.Anyways, the problem can be done with integers. Hmmmm... It's actually not clear if the float solution is slower than the integer solution given that the integer solution computes x^y twice.To me, the better brainteasers admit multiple solutions rather than one anointed answer.QuoteQuoteWill programming languages always be second-class languages as long as one still needs English in order to define the problem?In that sense, yes. But its' a wee bit navel-gazing.You may be right. Yet a more complete programming language would enable:1) Completeness! It seems funny to me that half of the overall process of programming must use a non-programming language.2) Minimizing the two-language problem (is ! a factorial or an exclamation point?)3) Writing algorithms that can naturally express the process of writing algorithms.

Cuchulainn
Posts: 61185
Joined: July 16th, 2004, 7:38 am
Location: Amsterdam
Contact:

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

It would be interesting to produce code for all the offerings? Whose up for it?
http://www.datasimfinancial.com
http://www.datasim.nl

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

tlin123
Posts: 5
Joined: March 8th, 2015, 4:22 pm

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

Here is a python 2 code for some of the algorithms mentioned here.
Last edited by tlin123 on March 9th, 2015, 11:00 pm, edited 1 time in total.

Wilmott.com has been "Serving the Quantitative Finance Community" since 2001. Continued...

 JOBS BOARD

Looking for a quant job, risk, algo trading,...? Browse jobs here...

GZIP: On