Re: 48G fraction capability...WOW!! Message #12 Posted by Valentin Albillo on 18 Sept 2006, 6:00 a.m., in response to message #1 by Hal Bitton
Hi, Hal:
Hal posted:
"But the (amazing!) 48G found a non-integer common factor of
9.90205873703, which reduced 2356789/10000000 to 238010/1009791. This must be one sophisticated algorithm to do that converting decimals to fractions"
Nothing of the sort, and certainly no "non-integer common factors" in sight. This is usually done by continued fractions.
As part of one of my S&SMC challenges (#13, to be precise), I gave this simple routine, DEC2FRC, which does exactly that, and further allows
extra control of the desired precision. As it is so short and perfectly understandable (it uses nothing but basic arithmetic functions, INT is "integer part", "FP" is fractional part, "INF" is "infinity" i.e., 1E99 or so), you'll be able to easily understand it and port it to any desired machine or language.
The listing, description, and examples follows. Best regards from V.
---------
Here's a 5-line subprogram I wrote for the occasion which will do the conversion:
100 SUB DEC2FRC(X,N,D,W) @ IF X=0 THEN N=0 @ D=1 @ END
110 U=0 @ V=1 @ N=1 @ D=0 @ Y=INF @ Z=ABS(X) @ F=SGN(X) @ X=Z @ W=ABS(W)
120 C=INT(X) @ IF FP(X)=0 THEN N=N*F @ END ELSE X=1/FP(X) @ S=N @ T=D
130 N=N*C+U @ U=S @ D=D*C+V @ V=T @ R=N/D @ IF ABS(R/Z-1)<W THEN N=N*F @ END
140 IF R=Y OR MAX(N,D)>1.E+12 THEN N=U*F @ D=V @ END ELSE Y=R @ GOTO 120
This subprogram is based in the continued fraction expansion of the given decimal
number, and it simply computes the subsequent approximants till the tolerance
is met, returning the last one.
To use it, you simply call DEC2FRC, passing it the following parameters:
X: passed by value, is the decimal number to convert to fractional form
N: passed by reference, is the variable where the numerator will be returned
D: passed by reference, is the variable where the denominator will be returned
W: passed by value, is a tolerance value which lets you control the
relative error of the fraction so you can get smaller
fractions which still result in acceptable errors;
specifying this tolerance as 0 will return the most
precise fraction (smallest error) found
For example, let's convert -PI to fractional form calling DEC2FRC from
the command line:
>CALL DEC2FRC(-PI,N,D,0) @ N,D,N/D,PI
-1146408 364913 -3.14159265359 3.14159265359
so our fraction is -1146408/364913, which agrees with PI to 12 digits.
Let's suppose that we don't want so close an approximation, but prefer
instead a simpler fraction. We'll call DEC2FRC again, but this time
we'll specify a tolerance of 0.00001 for the maximum relative error:
>CALL DEC2FRC(-PI,N,D,1E-5) @ N,D,N/D,PI
-355 113 -3.14159292035 3.14159265359
and so this time our fraction is -355/113, which agrees with -PI to nearly
8 digits, far better than our tolerance would have us believe. So our subprogram
does work, and you can freely use it in your own programs which require fraction
output.
---------------
Best regards from V.
Edited: 18 Sept 2006, 6:02 a.m.
|