The Perl Toolchain Summit 2025 Needs You: You can help 🙏 Learn more

VIPUL / Math-Fibonacci-1.5 / lib / Math / Fibonacci.pm 

            

              
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
—
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134

              
#!/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 $
=head1 SYNOPSIS
    use Math::Fibonacci qw(term series decompose);
    my $term = term ( 42 );
    my @series = series ( 42 );
    my @sum = decompose ( 65535 );
=head1 DESCRIPTION
This module provides a few functions related to Fibonacci numbers.
=head1 EXPORTS ON REQUEST
term(), series() decompose(), isfibonacci()
=head1 FUNCTIONS
=over 4
=item B<term($n)> 
Returns the $n-th term of the Fibonacci sequence. The term is computed
using the fast algorithm: C<F(n) ~ g^n/sqrt(5)>, where g is the golden
ratio and ~ means "take the nearest integer".
=item B<series($n)> 
Computes and returns the first $n Fibonacci numbers.
=item B<decompose($int)> 
Decomposes $int into the sum of Fibonacci numbers. Returns the list of
Fibonacci numbers.  
=item B<isfibonacci($int)>
Returns the sequence number of $int if it is a Fibonacci number or a
non-true value if it is not.
=head1 AUTHOR
Vipul Ved Prakash, E<lt>mail@vipul.netE<gt>
=head1 LICENSE 
Copyright (c) 1999-2001, Vipul Ved Prakash.  
This code is free software; you can redistribute it and/or modify it under
the ARTISTIC license (a copy is included in the distribution) or under the
same terms as Perl itself.
=cut