MSratio
Routine

void MSratio (double Val, long int *N, long int *D, double tol,
long int MaxN, long int MaxD)
Purpose

Find a ratio of integers approximation to a floating point value
Description
A continued fraction expansion approximation to a given floating point
value is calculated iteratively. At successive stages in the expansion,
the approximation error for the convergents alternates in sign but with
diminishing magnitude. The expansion is terminated when either two
conditions is satisfied.

1: The magnitude of either the numerator or the denominator of the
approximation is larger than a given limit. If so, the secondary
convergents are tested to see if one provides a smaller error than
backing off to the convergent from the previous iteration.

2: The absolute value of the difference between the approximation (N/D) and
the given number is less than a specified value (tol).
If the input value is exactly a ratio of integers, this routine will find
those integers if tol is set to zero, and MaxN and MaxD are appropriately
large.
Consider that case that the iteration is stopped by either the numerator
exceeding MaxN or the denominator exceeding MaxD. The resulting fraction
N/D is the fraction nearest Val amongst those fractions with numerator and
denominator not exceeding the given limits.

References:
R. B. J. T. Allenby and E. J. Redfern, "Introduction to Number Theory with
Computing", Edward Arnold, 1989.
I. Niven and H. S. Zuckerman, "An Introduction to the Theory of Numbers",
4th ed., John Wiley & Sons, 1980.
Parameters

> double Val

Value to be approximated. This value should have a magnitude between
1/MaxD and MaxN.

< long int N

Numerator in the rational approximation to Val. N is negative if Val is
negative.

< long int D

Denominator in the rational approximation to Val.

> double tol

Error tolerance used to terminate the approximation

> long int MaxN

Maximum value for N. This value should be at least floor(Val).

> long int MaxD

Maximum value for D. This value should be at least floor(1/Val).
Author / revision
P. Kabal
/ Revision 1.7 2003/05/09
Main Index libtsp