view release on metacpan or  search on metacpan

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

#!/usr/bin/perl
#
# Computes the Fibonacci sequence using the fast algorithm:  F(n) ~ g^n/sqrt(5),
# where g is the golden ratio and ~ stands for "take the nearest integer."
#
# Copyright (c) 1999-2000, Vipul Ved Prakash <mail@vipul.net>
# This code is free software distributed under the same license as Perl itself.
# $Id: Fibonacci.pm,v 1.5 2001/04/28 20:41:15 vipul Exp $

package Math::Fibonacci;
use strict;
use vars qw($VERSION @ISA @EXPORT_OK);
use POSIX qw(log10 ceil floor); 
require Exporter;
@ISA = qw(Exporter);
( $VERSION )  = '$Revision: 1.5 $' =~ /\s(\d+\.\d+)\s/; 

@EXPORT_OK = qw(term series decompose isfibonacci);

sub g ()     { "1.61803398874989" }  # golden ratio

sub term     { nearestint ((g ** shift) / sqrt(5)) } # nth term of the seq

sub series   { return map(term($_), 1..shift) } # n terms of the seq


sub decompose {                      # decomposes any integer into the sum of
                                     # members of the fibonacci sequence.
    my ($int) = @_;
    my $sum = decomp ($int);
    return @$sum;

}

sub decomp { 
    my ($a, $sum) = @_; 
    my $n = nearestint ((log10($a) + log10(sqrt(5)))/log10(g));
    my $fibn = term($n);
       if ( $fibn == $a ) { push @$sum, $a; return $sum } 
    elsif ( $fibn < $a  ) { push @$sum, $fibn; decomp( $a-$fibn, $sum ) }
    elsif ( $a < $fibn  ) { my $fibn1 = term($n-1); push @$sum, $fibn1; 
                            decomp( $a - $fibn1, $sum ) }
};


sub isfibonacci { 
    
    my $a = shift;
    my $n = nearestint ((log10($a) + log10(sqrt(5)))/log10(g));
    return $a == term($n) ? $n : 0;

}

sub nearestint {
    my $v = shift;
    my $f = floor($v); my $c = ceil($v);
    ($v-$f) < ($c-$v) ? $f : $c;
}


# routines to implement term and series with the familiar additive algorithm.

sub a_term     { return $_[0] < 3 ? 1 : a_term($_[0]-1) + a_term ($_[0]-2) }

sub a_series   {
    my @series = map(a_term($_), 1..shift);
    \@series;
}


1;


=head1 NAME

Math::Fibonacci - Fibonacci numbers.

=head1 VERSION

    $Revision: 1.5 $