[seqfan] Re: A1595 mentioned in Medium article
M. F. Hasler
oeis at hasler.fr
Mon Nov 9 22:50:55 CET 2020
Marc,
I think Alonso is aware of that, his article gives the "native" method
explicitly as bad example to produce a timeout.
The matrix computation method, Fib(n) = ( M^n )[1,2] = ( M^n )[2,1] = (
M^(n-1) )[2,2] with M = [0,1; 1,1]
is already given in some of the programs of oeis.org/A45, e.g., Julia.
But two more remarks should be made, given you mentioned this method:
- first, there is an explicit formula,
Fibonacci(n) = (Phi^n - Phi^-n)/sqrt(5) = floor(Phi^n / sqrt(5))
with the golden ratio Phi = (sqrt(5)+1)/2
which is usable "out of the box" with standard (double) precision [38
digits] up to almost Fib(200) (~ 10^41)
or beyond either with increased floating point precision,
or using exact arithmetic in (some implementation of) Z[sqrt(5)], see,
e.g., the PARI code with "quadgen(5)".
- The latter would probably, like your code for matrix multiplication, use
what is called binary exponentiation.
It's a bit confusing to make a procedure called matfibpow(), because
this is just the standard way of computing integer powers of matrices or
any other objects.
All sensible programming languages do implement M^n in that way.
I would find it very strange if Java didn't.
Let all SeqFans be assured that PARI/GP does that when you type
[0,1;1,1]^n, without need for a custom procedure.
Regards,
Maximilian
On Mon, 9 Nov 2020, 16:47 Marc LeBrun, <mlb at well.com> wrote:
It's sometimes useful to know that -- if you just want to get the N-th
Fibonacci number without computing so many prior ones -- you can do much
better: there's an approach where you can compute it with fixed storage in
O(log2 N) operations, by computing the N-th power of a 2x2 matrix the same
way numeric N-th powers are efficiently calculated:
To do this, let the identity matrix be
1 0
I :=
0 1
and also define a "multiplier" matrix
0 1
M :=
1 1
and then evaluate the following recursive procedure
matfibpow(N):=
if N==0
then return I
else
let F = matfibpow(floor(N/2))
set F = F * F
if N is odd
then return M * F
else return F
Finally, the N-th Fibonacci number will be the [2,1] element of the
returned matrix.
Basically M encodes the the linear recurrence relationship. This approach
can be applied for different initial values by modifying the final step,
and for different recurrences by using a different multiplier matrix M.
> On Nov 9, 2020, at 10:22 AM, Alonso Del Arte <alonso.delarte at gmail.com>
wrote:
>
> Thank you for finding A1610, David. I think I made a mistake when I tried
> to calculate that sequence, so it didn't matter if I omitted the initial
> terms. I decided I did not actually need the sequence for the article, so
I
> set it aside. Now that I've had time to sleep on it, I've verified that
> A1610 with a 1 joined at the beginning is the sequence I was looking for.
>
> I should mention that I omitted one line from the article:
>
> public static BigInteger fibonacci(int n) {
> *counter++;*
> switch (n) {
> case 0: return BigInteger.ZERO;
> case 1: return BigInteger.ONE;
> default:
> return fibonacci(n - 2).add(fibonacci(n - 1));
> }
> }
>
> counter is a static variable that keeps track of how many times
fibonacci()
> is called.
>
> Fred wrote that
>
>> 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.
>
> I think that would be the case if the program remembers previously
computed
> values.
>
> I remember a JavaScript whiteboarding meet-up where the moderator used a
> JavaScript implementation like the Java one quoted above. She used it to
> solve a Project Euler problem regarding even Fibonacci numbers. It was
only
> necessary to go up to Fibonacci(50), if I recall correctly. It took
> something like a full minute to give a result. No one said anything.
>
> The simple act of saving previously computed values cuts down computation
> times: Fibonacci(50) in a millisecond or two instead of a full minute, and
> Fibonacci(100) in a few milliseconds instead of the theoretical 36 million
> years.
>
> Al
>
> On Mon, Nov 9, 2020 at 8:47 AM David Seal <david.j.seal at gwynmop.com>
wrote:
>
>>> On 09/11/2020 05:34 Alonso Del Arte <alonso.delarte at gmail.com> wrote:
>>> ...
>>> 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?
>>
>> From the definition of the Fibonacci numbers (A000045), which is "F(n) =
>> F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1", and from the definition of
>> A001595, which is "a(n) = a(n-1) + a(n-2) + 1, with a(0) = a(1) = 1", it
is
>> very easy to prove by induction that a(n) >= F(n) for all n >= 0 (with
>> equality if and only if n = 1), and so the difference of the two
sequences
>> does not change sign.
>>
>> Is there some subtlety about this question whose significance I'm
missing?
>> - for instance, a meaning of "*n*"?
>>
>> A search for the first ten values of A001595(n) - A000045(n), which are
>> 1,0,2,3,6,10,17,28,46,75, says that it doesn't match any sequence in the
>> OEIS. However, leaving off its initial 1 finds A001610, described as
"a(n)
>> = a(n-1) + a(n-2) + 1" - an incomplete definition, so I have submitted a
>> change to add "with a(0) = 0 and a(1) = 2". With that completed
definition,
>> it's also very easy to prove by induction that A001610(n) = A001595(n+1)
-
>> A000045(n+1) for all n >= 0.
>>
>> David
>>
>> --
>> Seqfan Mailing list - http://list.seqfan.eu/
>>
>
>
> --
> 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/
--
Seqfan Mailing list - http://list.seqfan.eu/
On Mon, 9 Nov 2020, 16:47 Marc LeBrun, <mlb at well.com> wrote:
> It's sometimes useful to know that -- if you just want to get the N-th
> Fibonacci number without computing so many prior ones -- you can do much
> better: there's an approach where you can compute it with fixed storage in
> O(log2 N) operations, by computing the N-th power of a 2x2 matrix the same
> way numeric N-th powers are efficiently calculated:
>
> To do this, let the identity matrix be
>
> 1 0
> I :=
> 0 1
>
> and also define a "multiplier" matrix
>
> 0 1
> M :=
> 1 1
>
> and then evaluate the following recursive procedure
>
> matfibpow(N):=
> if N==0
> then return I
> else
> let F = matfibpow(floor(N/2))
> set F = F * F
> if N is odd
> then return M * F
> else return F
>
> Finally, the N-th Fibonacci number will be the [2,1] element of the
> returned matrix.
>
> Basically M encodes the the linear recurrence relationship. This approach
> can be applied for different initial values by modifying the final step,
> and for different recurrences by using a different multiplier matrix M.
>
>
> > On Nov 9, 2020, at 10:22 AM, Alonso Del Arte <alonso.delarte at gmail.com>
> wrote:
> >
> > Thank you for finding A1610, David. I think I made a mistake when I tried
> > to calculate that sequence, so it didn't matter if I omitted the initial
> > terms. I decided I did not actually need the sequence for the article,
> so I
> > set it aside. Now that I've had time to sleep on it, I've verified that
> > A1610 with a 1 joined at the beginning is the sequence I was looking for.
> >
> > I should mention that I omitted one line from the article:
> >
> > public static BigInteger fibonacci(int n) {
> > *counter++;*
> > switch (n) {
> > case 0: return BigInteger.ZERO;
> > case 1: return BigInteger.ONE;
> > default:
> > return fibonacci(n - 2).add(fibonacci(n - 1));
> > }
> > }
> >
> > counter is a static variable that keeps track of how many times
> fibonacci()
> > is called.
> >
> > Fred wrote that
> >
> >> 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.
> >
> > I think that would be the case if the program remembers previously
> computed
> > values.
> >
> > I remember a JavaScript whiteboarding meet-up where the moderator used a
> > JavaScript implementation like the Java one quoted above. She used it to
> > solve a Project Euler problem regarding even Fibonacci numbers. It was
> only
> > necessary to go up to Fibonacci(50), if I recall correctly. It took
> > something like a full minute to give a result. No one said anything.
> >
> > The simple act of saving previously computed values cuts down computation
> > times: Fibonacci(50) in a millisecond or two instead of a full minute,
> and
> > Fibonacci(100) in a few milliseconds instead of the theoretical 36
> million
> > years.
> >
> > Al
> >
> > On Mon, Nov 9, 2020 at 8:47 AM David Seal <david.j.seal at gwynmop.com>
> wrote:
> >
> >>> On 09/11/2020 05:34 Alonso Del Arte <alonso.delarte at gmail.com> wrote:
> >>> ...
> >>> 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?
> >>
> >> From the definition of the Fibonacci numbers (A000045), which is "F(n) =
> >> F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1", and from the definition of
> >> A001595, which is "a(n) = a(n-1) + a(n-2) + 1, with a(0) = a(1) = 1",
> it is
> >> very easy to prove by induction that a(n) >= F(n) for all n >= 0 (with
> >> equality if and only if n = 1), and so the difference of the two
> sequences
> >> does not change sign.
> >>
> >> Is there some subtlety about this question whose significance I'm
> missing?
> >> - for instance, a meaning of "*n*"?
> >>
> >> A search for the first ten values of A001595(n) - A000045(n), which are
> >> 1,0,2,3,6,10,17,28,46,75, says that it doesn't match any sequence in the
> >> OEIS. However, leaving off its initial 1 finds A001610, described as
> "a(n)
> >> = a(n-1) + a(n-2) + 1" - an incomplete definition, so I have submitted a
> >> change to add "with a(0) = 0 and a(1) = 2". With that completed
> definition,
> >> it's also very easy to prove by induction that A001610(n) =
> A001595(n+1) -
> >> A000045(n+1) for all n >= 0.
> >>
> >> David
> >>
> >> --
> >> Seqfan Mailing list - http://list.seqfan.eu/
> >>
> >
> >
> > --
> > 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/
>
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>
More information about the SeqFan
mailing list