view release on metacpan or  search on metacpan

lib/Math/NumSeq/Fibonacci.pm  view on Meta::CPAN

     i     F[i]
    ---    ----
     0       0
    -1       1
    -2      -1       <----+ negative at even i
    -3       2            |
    -4      -3       <----+

When C<$value> exceeds the range of a Perl unsigned integer the return is a
C<Math::BigInt> to preserve precision.

=item C<$bool = $seq-E<gt>pred($value)>

Return true if C<$value> occurs in the sequence, so is a positive Fibonacci
number.

=item C<$i = $seq-E<gt>value_to_i_estimate($value)>

Return an estimate of the i corresponding to C<$value>.  See L</Value to i
Estimate> below.

=back

=head1 FORMULAS

=head2 Ith

Fibonacci F[i] can be calculated by a powering procedure with two squares
per step.  A pair of values F[k] and F[k-1] are maintained and advanced
according to bits of i from high to low

    start k=1, F[k]=1, F[k-1]=0
    add = -2       # 2*(-1)^k
    
    loop
      F[2k+1] = 4*F[k]^2 - F[k-1]^2 + add
      F[2k-1] =   F[k]^2 + F[k-1]^2

      F[2k] = F[2k+1] - F[2k-1]

      bit = next bit of i, high to low, skip high 1 bit
      if bit == 1
         take F[2k+1], F[2k] as new F[k],F[k-1]
         add = -2 (for next loop)
      else bit == 0
         take F[2k], F[2k-1] as new F[k],F[k-1]
         add = 2 (for next loop)

For the last (least significant) bit of i an optimization can be made with a
single multiple for that last step, instead of two squares.

    bit = least significant bit of i
    if bit == 1
       F[2k+1] = (2F[k]+F[k-1])*(2F[k]-F[k-1]) + add
    else
       F[2k]   = F[k]*(F[k]+2F[k-1])

The "add" amount is 2*(-1)^k which means +2 or -2 according to k odd or
even, which means whether the previous bit taken from i was 1 or 0.  That
can be easily noted from each bit, to be used in the following loop
iteration or the final step F[2k+1] formula.

For small i it's usually faster to just successively add F[k+1]=F[k]+F[k-1],
but when in bignums the doubling k-E<gt>2k by two squares is faster than
doing k many individual additions for the same thing.

=head2 Value to i Estimate

F[i] increases as a power of phi, the golden ratio.  The exact value is

    F[i] = (phi^i - beta^i) / (phi - beta)    # exactly

    phi = (1+sqrt(5))/2 = 1.618
    beta = -1/phi = -0.618

Since abs(beta)E<lt>1 the beta^i term quickly becomes small.  So taking a
log (natural logarithm) to get i,

    log(F[i]) ~= i*log(phi) - log(phi-beta)
    i ~= (log(F[i]) + log(phi-beta)) / log(phi)

Or the same using log base 2 which can be estimated from the highest bit
position of a bignum,

    log2(F[i]) ~= i*log2(phi) - log2(phi-beta)
    i ~= (log2(F[i]) + log2(phi-beta)) / log2(phi)

=head1 SEE ALSO

L<Math::NumSeq>,
L<Math::NumSeq::LucasNumbers>,
L<Math::NumSeq::Fibbinary>,
L<Math::NumSeq::FibonacciWord>,
L<Math::NumSeq::Pell>,
L<Math::NumSeq::Tribonacci>

L<Math::Fibonacci>,
L<Math::Fibonacci::Phi>

=head1 HOME PAGE

L<http://user42.tuxfamily.org/math-numseq/index.html>

=head1 LICENSE

Copyright 2010, 2011, 2012, 2013, 2014, 2016, 2019, 2020 Kevin Ryde

Math-NumSeq is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the Free
Software Foundation; either version 3, or (at your option) any later
version.

Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License for
more details.

You should have received a copy of the GNU General Public License along with
Math-NumSeq.  If not, see <http://www.gnu.org/licenses/>.

=cut