#!/usr/bin/perl -w
use strict;
use warnings;
use diagnostics;



=head1
cf takes a bigrat for its input, and returns an array as a continued
fraction.  In textbooks a continued fraction is often represented as
something like:

	1
_______________
	2 + 1
	___________
		2 + 1
			____
			2 + ...

Publishers hate this because it uses up lots of empty paper, which they
find annoying for some reason.  A shorthand way of writing this is:

[1; 2, 2, 2, 2 ...],

which is considerably easier to type.  I follow this
convention in these scripts, when discussing continued fractions.

An intriguing property of continued fractions is that they will form a
repeating set of numbers when square roots are represented in that form.
For example, the square root of 2 is 1.41421356237309504880168872420969807...,
give or take a bit.  This representation continues indefinitely, meaning the
number of digits in this representation is infinite.  Not only that, the
digits do not repeat any pattern.

The continued fraction representation of sqrt(2) is simply [1; 2, 2, 2, ...].
Although the numbers continue indefinitely, the pattern repeats.  This is true
of all square roots of rational numbers.

Some other values also have a repeating pattern, for example e.  Its
representation in continued fraction format is:
[2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, 1, 10, 1, 1, 12, 1, 1, 14,
1 1 16 1 1...]

While it doesn't exactly *repeat*, it does have a discernible pattern that
can be used to advantage.  The sequence of digits can be expanded at will,
and converting a continued fraction back into a bigrat will generate e
to any desired accuracy.  This also applies to square roots of rational
numbers.

=cut
sub cf	{
use bigrat;
my $number=Math::BigRat->new(shift);
my $pvar = 50; # Arbitrary limit to number of continued fraction elements.
my $count=0;
my $int1;
my @array;

while($number &&($count<$pvar))	{
	$int1=$number->copy->bfloor($number);
	$array[$count]=($int1);
	$number-=$int1;
	if($number)	{
		$number=(1/$number);
		}
	else	{
	last;
		}
	$count++;
	}
return @array;
}



=head1
This sub takes an array of values that it interprets as a continued fraction.
For this sub, the format for a continued fraction is an array containing the
integer part of the real number as its first element (zeroth element.  Each
successive element, if any, represents an integer formed by subtracting the
previous integer from the value, and then inverting it.  In other words, you
take the number, subtract its integer portion (saving it in the array).  If
the fractional part is not zero, you then invert the remaining fractional
part.  Since this value was less than one before the inversion, it will be
greater than 1 afterwards.  This means it will again have an integer part
that can be subtracted.  You keep this up until you get zero as a remaining
part, which of course can't be inverted.  Or else, you just get tired, since
any irrational number will repeat endlessly.  Or you could just keep going,
but this becomes tiresome after a while.
=cut

sub cf2rat(@)	{
my @a=@_;
my $max=@a;
if($max==1)	{
	return(@a);
	}
my (@p,,@q);
$p[0]=$a[0];
$q[0]=1;
$p[1]=$a[1]*$a[0]+1;
$q[1]=$a[1];
my @r;
my $k=2;
while($k<$max)	{
	$p[$k]=$a[$k]*$p[$k-1]+$p[$k-2];
	$q[$k]=$a[$k]*$q[$k-1]+$q[$k-2];
	$k++;
	}
for(my $i=0;$i<$max;$i++)	{
		$r[$i]="$p[$i]".'/'."$q[$i]";
	}
return(@r);
}

__END__


=head1 NAME

CFrac

=head1 SYNOPSIS

Scripts for converting between rational numbers and continued fractions.
Very alpha...

=head1 DESCRIPTION


One use of continued fractions is to generate arbitrarily accurate decimal
expansions of certain irrational numbers.  Since these particular continued
fractions repeat or have a pattern, one can construct arbitrarily long
continued fractions, and then perform the operations to convert the
continued fraction back to a rational approximation to the irrational.  The
accuracy depends only on how long the continued fraction is.

To calculate e out to a gazillion places, start with a continued fraction
that is quite lengthy - I cannot actually say how long it must be, in order
to attain a given accuracy.  However, the longer, the better.  For e, the
pattern is [2; 1, 2, 1, 1, 4, 1, 1, 6, ..] - two ones, followed by a
number that increases by 2 each time it shows up again.  Simple enough.

=head1 SEE ALSO

Math::BigInt, Math::BigRat, bignum, bigrat, etc.

=head1 AUTHOR

Baruch Ben-David (baruch@cpan.org)

Copyright 2005 Baruch Ben-David, All Rights Reserved.

This program 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 2 of the License, or
(at your option) any later version.

This program 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 this program; if not, write to the

Free Software Foundation, Inc.
59 Temple Place - Suite 330
Boston, MA 02111-1307, USA.

=cut