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 *

February 3rd, 2015, 3:31 pm

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?
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Compute the Nth Fibonacci nr using only + and *

February 3rd, 2015, 3:36 pm

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.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Compute the Nth Fibonacci nr using only + and *

February 3rd, 2015, 3:45 pm

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

Compute the Nth Fibonacci nr using only + and *

February 3rd, 2015, 3:52 pm

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.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Compute the Nth Fibonacci nr using only + and *

February 3rd, 2015, 3:55 pm

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

Compute the Nth Fibonacci nr using only + and *

February 3rd, 2015, 4:01 pm

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.
 
User avatar
Cuchulainn
Posts: 20250
Joined: July 16th, 2004, 7:38 am
Location: 20, 000

Compute the Nth Fibonacci nr using only + and *

February 3rd, 2015, 4:21 pm

It would be interesting to produce code for all the offerings? Whose up for it?
 
User avatar
tlin123
Posts: 0
Joined: March 8th, 2015, 4:22 pm

Compute the Nth Fibonacci nr using only + and *

March 10th, 2015, 1:54 am

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.