[seqfan] Re: A1595 mentioned in Medium article

[Fred Lunnon]

  In the (handwritten!) article by Dijkstra cited by A001595 at
    https://www.cs.utexas.edu/users/EWD/ewd07xx/EWD797.PDF
[ beware: his indices  n  are offset by 1 from standard usage! ]
equn. (7) gives
    L(n+1)  =  2 F(n+1) - 1 ,
where  L(n) , F(n)  denote Leonardo, Fibonacci  sequences resp.;
it follows that
    F(n) - L(n)  =   1 - F(n)  <  0  for  n > 2 .

  A simple efficient algorithm for computing isolated values of  F(n)
uses the explicit formula from equn. (6), in the more usual form
    F(n)  =  ( t^n - s^n ) / sqrt(5) ,
where
    t = ( 1 + sqrt(5) )/2 ,  s = ( 1 - sqrt(5) )/2 ;
each exponential requires order  log(n)  multiplications;
and since  |s| ~ 0.618  <  1  one may just ignore  s^n  for  n >= 2 ,
instead rounding the result to the nearest integer.

  [ With a little more care, the recursion can be improved via "divide
and conquer" in the same way as exponentiation, to use entirely integers,
again requiring order  log(n)  multiplications. ]

  There is nothing wrong with using the recursion directly for small
values: simply compute each  F(m)  in turn for  2 <= m <= n ,
requiring order  n  additions.

WFL



On 11/9/20, Alonso Del Arte <alonso.delarte at gmail.com> wrote:
> I mention A001595 in my Medium article about timeouts in JUnit 5:
> https://levelup.gitconnected.com/asserting-timeouts-in-junit-5-4477054f82d3
> The obvious algorithm for calculating Fibonacci numbers is extremely
> inefficient for all but the smallest positive indices. And even for small
> indices it requires a lot of recursion. That's what led me to A001595, and
> I use it to predict that it would take some 36 million years to calculate
> Fibonacci(100).
>
> I've been wondering about Fibonacci(*n*)  − A001595(*n*). That's probably
> already in the OEIS, though maybe without signs. It does change sign, right?
>
> Al
>
> --
> Alonso del Arte
> Author at SmashWords.com
> <https://www.smashwords.com/profile/view/AlonsoDelarte>
> Musician at ReverbNation.com <http://www.reverbnation.com/alonsodelarte>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>