[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Fibonacci
From: |
Kevin Ryde |
Subject: |
Re: Fibonacci |
Date: |
07 Jul 2001 08:56:40 +1000 |
User-agent: |
Gnus/5.0808 (Gnus v5.8.8) Emacs/20.5 |
Emil Jerabek <address@hidden> writes:
>
> A comment in mpz/fib_ui.c says something about computing the Fibonacci
> numbers using Lucas numbers, since that would enable to replace
> general multiplication by squaring in the recursive formula.
>
> There is a simple way how to achieve this without using the Lucas numbers as
> an auxiliary sequence:
>
> F[2n] = 2*F[n+1]^2 - 3*F[n]^2 - (-1)^n
> F[2n+1] = F[n+1]^2 + F[n]^2
Thanks, yes, that comment wasn't well thought through. The simple
relations between F[n],F[n+1] and F[n],L[n], or L[n],L[n+1], mean of
course doubling can be done with any of those using just two squares.
The next release will have some new code based on F[n],F[n-1] and will
include functions returning a pair of Fibonacci numbers or a single or
pair of Lucas numbers. Brief description below, for interest.
Fibonacci Numbers
-----------------
The Fibonacci functions `mpz_fib_ui' and `mpz_fib2_ui' are designed
for calculating isolated F[n] or F[n],F[n-1] values efficiently.
For small n, a table of single limb values in `__gmp_fib_table' is
used. On a 32-bit limb this goes up to F[47], or on a 64-bit limb up
to F[93]. For convenience the table starts at F[-1].
Beyond the table, values are generated with a binary powering
algorithm, calculating a pair F[n] and F[n-1] working from high to low
across the bits of n. The formulas used are
F[2k+1] = 4*F[k]^2 - F[k-1]^2 + 2*(-1)^k
F[2k-1] = F[k]^2 + F[k-1]^2
F[2k] = F[2k+1] - F[2k-1]
At each step, k is the high b bits of n. If the next bit of n is 0
then F[2k],F[2k-1] is used, or if it's a 1 then F[2k+1],F[2k] is used,
and the process repeated until all bits of n are incorporated. Notice
these formulas require just two squares per bit of n.
It'd be possible to handle the first few n above the single limb
table with simple additions, using the defining Fibonacci recurrance
F[k+1]=F[k]+F[k-1], but this is not done since it turns out to be
faster for only about 10 or 20 values of n, and including a block of
code for just those doesn't seem worthwhile. If they really mattered
it'd be better to extend the data table.
Using a table avoids lots of calculations on small numbers, and
makes small n go fast. A bigger table would make more small n go fast,
it's just a question of balancing size against desired speed. For GMP
the code is kept compact, with the emphasis primarily on a good
powering algorithm.
`mpz_fib2_ui' returns both F[n] and F[n-1], but `mpz_fib_ui' is only
interested in F[n]. In this case the last step of the algorithm can
become one multiply instead of two squares. One of the following two
formulas is used, according as n is odd or even.
F[2k] = F[k]*(F[k]+2F[k-1])
F[2k+1] = (2F[k]+F[k-1])*(2F[k]-F[k-1]) + 2*(-1)^k
F[2k+1] here is the same as above, just rearranged to be a multiply.
For interest, the 2*(-1)^k term both here and above can be applied
just to the low limb of the calculation, without a carry or borrow into
further limbs, which saves some code size. See comments with
`mpz_fib_ui' and the internal `mpn_fib2_ui' for how this is done.
Lucas Numbers
-------------
`mpz_lucnum2_ui' derives a pair of Lucas numbers from a pair of
Fibonacci numbers with the following simple formulas.
L[k] = F[k] + 2*F[k-1]
L[k-1] = 2*F[k] - F[k-1]
`mpz_lucnum_ui' is only interested in L[n], and some work can be
saved. Trailing zero bits on n can be handled with a single square
each.
L[2k] = = L[k]^2 - 2*(-1)^k
And the lowest 1 bit can be handled with one multiply of a pair of
Fibonacci numbers, similar to what `mpz_fib_ui' does.
L[2k+1] = 5*F[k-1]*(2*F[k]+F[k-1]) - 4*(-1)^k
- Fibonacci, Emil Jerabek, 2001/07/03
- Re: Fibonacci,
Kevin Ryde <=