🚀 go-pugleaf

In article <1992Dec28.193616.13854@cc.umontreal.ca>, 
soubyran@ERE.UMontreal.CA (Soubyran Richard) writes:

|> Can anyone give me an algorithm to find the fractional
|> representation of a real number?

Essentially you construct a truncated continued fraction that
approximates the number.  Example: You want to find a fraction
representing approximately 3.1415926 (just a "random" number :-)).

3.14159  = 3 + 1/7.06251
	 = 3 + 1/(7 + 1/15.9966)     (* you decide to stop here *)
	~= 3 + 1/(7 + 1/16)
	 = 355/113

The latter fraction has an approximate value of 3.141592920.  An
alternative is not to truncate but to round, which keeps the ab-
solute values of the denominators above 2 and converges faster.
You can have both signs then.  Compare approximations for the
square root of three:

1.73205  = 1 + 1/1.36602 = 1 + 1/(1 + 1/2.73205) = ...(periodic)
	~= 1+1/(1+1/(2+1/(1+1/(2+1/(1+1/(2+1/3))))))   
	 = 239/138  ~=  1.73188

versus

1.73205  = 2 - 1/3.73205 = 2 - 1/(4 - 1/3.73205) = ...(periodic)
	~= 2-1/(4-1/(4-1/(4-1/4)))
	 = 362/209  ~=  1.73206

It shouldn't be too hard to turn this algorithm into a program.
A stopping criterion must be conceived.  Note that for numbers
with a precision of 16 digits (about "double" precision), the
generated sequence will diverge after 12 to 20 iterations. The
truncated fraction, of course, converges to the starting number.

=================================================================
	Christian Brechbuehler         <brech@vision.ethz.ch>

	Communication Technology Lab, Image Science Group
	Federal Institute of Technology (ETH) Zurich, Switzerland
=================================================================