view release on metacpan or  search on metacpan

lib/Math/Rational/Approx.pm  view on Meta::CPAN

                # if $x is actually rational, round off error in ( $x - $int )
                # can drive the iteration beyond its true end point, causing
                # bogus results.  Let's hope that 10 digits is enough.
                last if ( $x - $int)->bfround(-10)->is_zero;
                $x = $one->copy->bdiv( $x - $int );
        }

        return $p, $x;
}

sub contfrac_nd {

	# ignore extra parameter to ease use of contfrac_nd( contfrac ( ... ) )
    my ( $terms ) = validate_pos( @_, { type => ARRAYREF }, 0 );
    my @p = reverse @$terms;

    my $n = Math::BigInt->bone;
    my $d = Math::BigInt->new( (shift @p) );

    for my $p ( @p ) {

            $n += $d * $p;

            ( $n, $d ) = ( $d, $n );

    }

    ( $n, $d ) = ( $d, $n );
    return ( $n, $d );
}


1;



__END__

=head1 NAME

Math::Rational::Approx - approximate a number with a rational number


=head1 SYNOPSIS

  use Math::Rational::Approx ':all';

  #
  # find rational approximation with maximum denominator
  ($n, $d, $bounds ) = maxD( $x, 10 );

  # refine; note reuse of $bounds from previous call
  ( $n, $d ) = maxD( $x, 20, $bounds );


  #
  # find rational approximation to arbitrary precision using
  # continued fractions

  # one shot, 10 iterations
  ( $numerator, $denominator ) =
                   contfrac_nd( contfrac( 1.234871035, 10 ) );

  # multiple calls on same number; useful for convergence tests
  # keep array containing terms; get fraction and perhaps test it
  ( $terms, $residual ) = contfrac( 1.234871035, 3 );
  ( $n, $d ) = contfrac_nd( $terms  );

  # continue for an additional number of steps; note reuse of $terms;
  # new terms are appended to it
  ( $terms, $residual ) = contfrac( $residual, 3, $terms );

  # new results
  ( $n, $d ) = contfrac_nd( $terms );


=head1 DESCRIPTION

This module and its object oriented companion modules provide various
means for finding rational number approximations to real numbers.  The
object oriented versions are suitable when repeated refinements are
required.  See L<Math::Rational::Approx::MaxD> and L<Math::Rational::Approx::ContFrac>.



=head1 INTERFACE

=head2 Maximum denominator

B<maxD> finds the best rational approximation (n/d) to a fraction with
a denominator less than a given value.  It uses Farey's sequence and
is based upon the algorithm given at
L<http://www.johndcook.com/blog/2010/10/20/best-rational-approximation/>.

This is an iterative procedure, searching a given range for the
best approximation.   To enable further refinement, the
limiting denominator may by adjusted; the approximation
will be continued from the last calculation.

=over

=item maxD

  ( $n, $d, $bounds ) = maxD( $x, $maxD, );
  ( $n, $d, $bounds ) = maxD( $x, $maxD, $bounds );

Calculate the rational number approximation to C<$x> with denominator
no greater than C<$maxD>.

The optional argument, C<$bounds>, is a reference to a four element
array containing the initial bounds on the region to search.  It takes
the form

  bounds => [ a, b, c, d ]

where the elements are all non-negative integers and the bounds are
given by

  a/b < x < c/d
  b < maxD && d < maxD