Real to fraction...

Thread View: sci.math.num-analysis

2 messages

[T] Back to Threads [V] Tree View [G] Group Articles

2 total messages Started by Soubyran Richard Mon, 28 Dec 1992 19:36

#903

Author: Soubyran Richard
Date: Mon, 28 Dec 1992 19:36

13 lines
651 bytes

Hello Mathers!

May be this one has already been posted... but I am taking the
chance...

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

I thank you very much in advance,

Richard Soubyran

soubyran@alize.ere.umontreal.ca

Re: Real to fraction...

#1064

Author: Christian Brechbuehler
Date: Fri, 08 Jan 1993 11:45

43 lines
2210 bytes

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
=================================================================

Thread Navigation

This is a paginated view of messages in the thread with full content displayed inline.

Messages are displayed in chronological order, with the original post highlighted in green.

Use pagination controls to navigate through all messages in large threads.

Back to All Threads