Converting a real number to a rational
Johan Kahrstrom
I've created a class in C++ that handles rational numbers, and I want
to
make it possible to convert a number from a double (real), to my
object,
rational. Is there any algoritms for doing this?
Johan Kahrstrom
joh...@mbox302.swipnet.se
Larry Brasfield
>Hi!
Hi.
> I've created a class in C++ that handles rational numbers, and I want to
> make it possible to convert a number from a double (real), to my object,
> rational. Is there any algoritms for doing this?
What should this algorithm do at the limits
of accuracy for a double?
One approach is to recognize that all floating
point numbers are really rationals with a power
of 2 denominator. So if you get the exponent
with frexp(), convert it to the equivalent integer
(pow(2, exp)), normalize the mantissa to a (big
enough) integer) then do gcd, you should get
the closest rational to the real you started with.
--Larry Brasfield
Above opinions may be mine alone.
(Humans may reply at unundered larry_br@sea_net.com )
Ron Natalie
>
> Hi!
>
> I've created a class in C++ that handles rational numbers, and I want
> to
> make it possible to convert a number from a double (real), to my
> object,
> rational. Is there any algoritms for doing this?
In actuallity, computers "real" numbers are almost always some
rational number with a divisor of a large power of two.
Mirian Azoubel Abram
the other is the number of decimals used to get an rational approximation
of the real number you started with.
Johan Kahrstrom wrote:
> Hi!
>
> I've created a class in C++ that handles rational numbers, and I want
> to
> make it possible to convert a number from a double (real), to my
> object,
> rational. Is there any algoritms for doing this?
>
> Johan Kahrstrom
> joh...@mbox302.swipnet.se
Bob Wheeler
convergents take the form N/M, where N and M are
integers. One can take sufficient terms for a real
x, such that e=|x-N/M| is as small as desired. A
problem which may not bother you, is that there is
no guarantee that M will always be the smallest
for a given e; for example the approximation
355/113 to pi may not be found in this way.
Bob Wheeler --- (Reply to: bwhe...@echip.com)
ECHIP, Inc.
Larry Brasfield wrote:
>
> Johan Kahrstrom wrote in message <36C90E...@mbox302.swipnet.se>...
> >Hi!
> Hi.
>
> > I've created a class in C++ that handles rational numbers, and I want to
> > make it possible to convert a number from a double (real), to my object,
> > rational. Is there any algoritms for doing this?
>
Darrah Chavey
Johan Kahrstrom asks:
> > I've created a class in C++ that handles rational numbers, and I want
> > to make it possible to convert a number from a double (real), to my
> > object, rational. Is there any algoritms for doing this?
> >
> > Johan Kahrstrom
> > joh...@mbox302.swipnet.se
R.W. Hutchinson responds:
> For "general purpose" use, what would serve you best is probably
> "Continued Fractions."
>
> Other solutions to the problem exist, of which the best known is probably
> "Farey Fractions." Fortunately, the Continued Fraction Algorithm can easily be
> modified to generate Farey Fractions. There are other solutions as well.
Let me expand on this. If you consider a floating point number, say 3.14159,
and you want to get a good rational approximation with the smallest possible
denominator, the Farey sequence achieves it as follows:
Take the fractions 3/1 and 4/1, one larger than the real number and one
smaller. Repeatedly form the intermediate value by adding numerators and
denominators; in this case to form 7/2. Since 7/2 > 3.14159, discard the
fraction 4/1, and repeat the operation with 3/1 and 7/2. If at some point
your denominators are d1 and d2, with d1 > d2, then you are guaranteed
that the most accurate approximation involving a fraction with denominator
no larger than d1 is one of your two fractions. C++ code to achieve this
is given below. This is written as a constructor that constructs a new
fraction object from an initial floating point value.
Fraction::Fraction( float ToApproximate ) {
/** Function to convert a floating point into a fraction. The fraction will not
* have the exact value, of the floating number but is as close as possible.
*/
const float accuracy = 0.000001; // sets the degree of accuracy
int SmallerNumerator;// numerator for fraction that is smaller than the float
int SmallerDenom; // denominator of the smaller fraction
int LargerNumerator; // numerator for fraction that is larger than the float
int LargerDenom; // denominator of larger number
float Frac; // real number value of closest fraction so far
SmallerNumerator = (int) ToApproximate;
LargerNum = SmallerNumerator + 1;
SmallerDenum = LargerDenum = 1;
Frac = (float)(SmallerNum + LargerNum) / (float)(SmallerDenum +
LargerDenum);
// calculate the initial approximation from the floating point we are
estimating
// - float type cast to get floating value
while ( abs(Frac-ToApproximate) > accuracy) {
numerator = LargerNumerator + SmallerNumerator;
denominator = SmallerDenom + LargerDenom;
Frac = (float) numerator / (float) denominator;
if (Frac > ToApproximate) {
LargerNumerator = numerator;
LargerDenom = denominator;
}
else {
SmallerNumerator = numerator;
SmallerDenom = denominator;
}
}
}
--Darrah Chavey Department of Math & Computer Science
cha...@beloit.edu Beloit College; 700 College St; Beloit, Wisc.
(608)-363-2220 http://www.beloit.edu/~chavey 53511
-- The main reason Santa is so jolly is because he knows where all the naughty girls live.
rwh...@nr.infi.net
>to
> make it possible to convert a number from a double (real), to my
>object,
> rational. Is there any algoritms for doing this?
>
> Johan Kahrstrom
> joh...@mbox302.swipnet.se
For "general purpose" use, what would serve you best is probably
"Continued Fractions."
Other solutions to the problem exist, of which the best known is probably
"Farey Fractions." Fortunately, the Continued Fraction Algorithm can easily be
modified to generate Farey Fractions. There are other solutions as well.
--------------------------------------------------------------
"I would predict that there are far greater mistakes waiting
to be made by someone with your obvious talent for it."
Orac to Vila. [City at the Edge of the World.]
-----------------------------------------------
R.W. Hutchinson. | rwh...@nr.infi.net
Dik T. Winter
> One way is to use a continued fraction. The
> convergents take the form N/M, where N and M are
> integers. One can take sufficient terms for a real
> x, such that e=|x-N/M| is as small as desired. A
> problem which may not bother you, is that there is
> no guarantee that M will always be the smallest
> for a given e;
A result from the theory of continued fractions is that if N/M is an
approximant to x, that all rational approximations N'/M' with M' < M
have |x - N'/M'| > |x - N/M|. So there is some guarantee. So in a
sense continued fraction approximants are the "best" approximations
to a real. The opposite does not hold. However, there is a class of
rational numbers easily derived from approximants (call them derived
approximants) such that the following holds: given a rational
approximation N/M to a real number x. If for every rational N'/M'
with M' < M holds that |x - N'/M'| > |x - N/M| then N/M is either
a continued fraction approximant or a number derived from such.
Given three successive approximants: N1/M1, N2/M2 and N3/M3. It is
known that N3 = N1 + k.N2 and M3 = M1 + k.M2 for some integer k.
The derived approximants are Nx/Mx with Nx = N1 + i.N2 and
Mx = M1 + i.M2 with ceil(k/2) <= i < k.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, +31205924131
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/
Martin Ambuhl
>
> Hi!
>
> I've created a class in C++ that handles rational numbers, and I want
> to
> make it possible to convert a number from a double (real), to my
> object,
> rational. Is there any algoritms for doing this?
As a C++ question and as an algorithm question, this question is
definitely off-topic in comp.lang.c. Please cross-post only to relevant
newsgroups.
However ...
Your double value is almost certainly defined as a mantissa of some
number of bits (call it N). If your implementation involves a hidden
MSB, then N is just 1 bit bigger. The exact rational form, apart from
the sign and the multiplier implied by the exponent, is
mantissa/pow(2,N).
The only common factors of the mantissa and the denominator are powers
of 2, recognizable by trailing 0s in the mantissa.
--
Martin Ambuhl (mam...@earthlink.net)
Note: mam...@tiac.net will soon be inactive
rwh...@nr.infi.net
>convergents take the form N/M, where N and M are
>integers. One can take sufficient terms for a real
>x, such that e=|x-N/M| is as small as desired. A
>problem which may not bother you, is that there is
>no guarantee that M will always be the smallest
>355/113 to pi may not be found in this way.
The following pair of "guarantees" is available.
a) If M/N is a continued fraction for x, then the difference is less than the reciprocal
of the square of N.
b) If there exists an approximation M/N for x such that the difference is less than
the reciprocal of DOUBLE the square of N, then the continued fraction algorithm will
find it.
Both theorems are in Hardy & Wright.
For approximations M/N such that the difference is between 1/N-squared
and 1/(2 * N-squared), the approximation may or may not be in the continued
fraction approximation sequence.
Incidentally, 355/115 does happen to be in the continued fraction approximating
sequence for Pi.
John Savard
>Hi!
>
> I've created a class in C++ that handles rational numbers, and I want
>to
> make it possible to convert a number from a double (real), to my
>object,
> rational. Is there any algoritms for doing this?
>
> Johan Kahrstrom
> joh...@mbox302.swipnet.se
This little program
input "Enter number to be approximated: ";a#
DIM d%(10)
FOR i% = 1 TO 10
k% = INT(a#)
d%(i%) = k%
b# = k%
a# = a# - b#
a# = 1# / a#
PRINT "Next continued fraction number, "; k%
IF i% = 1 THEN 20
de& = d%(i%)
nu& = 1 + d%(i% - 1) * de&
IF i% = 2 THEN 10
FOR j% = i% - 2 TO 1 STEP -1
nn& = nu& * d%(j%) + de&
de& = nu&
nu& = nn&
NEXT j%
10 PRINT nu&
PRINT "----------"
PRINT de&
LINE INPUT "Press ENTER to continue:"; dummy$
20 REM
NEXT i%
produces continued fraction approximations to a real that I input, so
you can use this algorithm - with some upper limit to the size of the
numerator and denominator - to solve your problem.
John Savard
http://www.freenet.edmonton.ab.ca/~jsavard/index.html
Paul Schlyter
Alan Miller <amiller @ vic.bigpond.net.au> wrote:
> Darrah Chevey gave code in C++. Here is the equivalent for oldies
> like me, in Fortran.
Thanks, but it was somewhat incomprehensible to me. I'm an "oldie"
who once did a lot of programming in Fortran-77. But I moved to C
and later C++ before Fortran-90 appeared, thus I never learnt
Fortran-90.
Since C++ and in particular C predated Fortran-90, one cannot consider
Fortran-90 programmers "oldies" any more than C or C++ programmers.
--
----------------------------------------------------------------
Paul Schlyter, Swedish Amateur Astronomer's Society (SAAF)
Grev Turegatan 40, S-114 38 Stockholm, SWEDEN
e-mail: pau...@saaf.se paul.s...@ausys.se pa...@inorbit.com
WWW: http://hotel04.ausys.se/pausch http://welcome.to/pausch
jordi romeu
integration and interpolation algorithms
on the surface of a sphere?
alex heldring