Re: [Bug-apl] Fibonacci sequence

[Frederick H. Pitts]

Elias,

        The best I can do in the way of a non-recursive one-liner follows

G ← {⍎,⊃((⍵>2),(⍵=2 1 0))/('1 1,(g¨2↓⍳ ⍵)' '1 1' '1' '0⍴0'),0⍴f←⍵
⍴1,0⍴g←{f[⍵]←+/f[⍵+¯1 ¯2]}}

        I speculate the time complexity of this solution is O(n).  The solution
gives the same results as the F function.  BTW, by the 93th Fibonacci
number the integer upper limit is exceeded and somewhere between the
1000th and 2000th Fibonacci number the upper limit of floating point is
exceeded.

        I did not attempt to conduct timing tests, but F and G appear to take
about the same amount of time to execute for a given argument.

Regards,

Fred
Retired Chemical Engineer


On Fri, 2014-07-04 at 10:14 +0800, Elias Mårtenson wrote:
> Thanks. Interesting solutions.
> 
> 
> Frederick, AFAICT your solution has a time complexity of O(n²). Is
> there a one-line solution that (like David's) is O(n) but does not use
> an explicit loop?
> 
> 
> Regards,
> Elias
> 
> 
> On 4 July 2014 09:12, Frederick H. Pitts <address@hidden>
> wrote:
>         Elias,
>         
>                 While Jurgen's solution is correct for the problem as
>         you stated it,
>         'Problem 3 - Tell a Fib' in
>         
> https://studentcompetitions-general.s3.amazonaws.com/testing-challenge/dyalog/2014%20PhaseI%20Problems.pdf
>         actually asks for the first n Fibonacci numbers, not the
>         Fibonacci
>         sequence up to a given number.
>         
>                 A GNU APL solution for the problem as stated in the
>         challenge is:
>         
>         F ← { ⍎ , ⊃ ((⍵>1) (⍵=1) (⍵=0)) / ( 'λ , + / ¯2 ↑ λ ← F ⍵−1' )
>         '1'
>         '0⍴0' }
>         
>         This solution returns an empty vector for F 0, 1 for F 1 and
>                 1 1 2 3 5 8 13 21 34 55
>         for F 10.
>         
>         Regards,
>         
>         Fred
>         Retired Chemical Engineer
>         
>         On Thu, 2014-07-03 at 22:12 +0800, Elias Mårtenson wrote:
>         > I was playing around with solving the Dyalog challenge, and
>         I found
>         > them pretty easy with the exception of one.
>         >
>         >
>         > The goal was to write a lambda function that given a single
>         integer,
>         > returns a list of the Fibonacci series up to that number.
>         >
>         >
>         > The only way I can think of solving it is by using a full
>         function and
>         > a loop. That can't possibly be the easiest way.
>         >
>         >
>         > Any suggestions?
>         >
>         >
>         > Regards,
>         > Elias
>         
>         
>         
> 
>