Ken Ward's Mathematics Pages

Number Theory Decimal to Fraction Conversion Using Euclid

Page Contents

Method

This method, algorithm, uses Euclid's Algorithm, as used to solve indeterminate linear equations. Another approach is more suited to decimal to vulgar fraction conversion, and is considered later.
Suppose we wish to express the number 0.69231 as a fraction. We wish to do this by finding a fraction with the smallest denominator consistent with our required accuracy.

We set up a table as follows and follow the instructions, which is in effect applying Euclid's Extended Algorithm:

k	x_k	y_k	r_k	q_k	Error= x_k/y_k-0.69231	Remarks
1	1	0	1			First set up the table with the 1's and the 0's as shown. r₁ is the larger of 1 and the decimal. r₂ is the smaller.
2	0	1	0.69231	1		Compute q₂=floor(r₁/r₂). Continue to do this, using the appropriate q's and r's until the remainder is zero, or the accuracy is sufficient. Compute: x₃=x₁-q·x₂=1, and y₃=y₃=y₁-q·y₂=-1
3	1	-1	0.30769	2	0.30769	Continue computing the x's and the y's
4	-2	3	0.07693	3	0.02564
5	7	10	0.0769	1	0.00769
6	-9	13	0.00003	2563	0.000002	At this point we have a decimal approximation that is accuracy to five figures. Because we might expect 0.69231 to be accurate within +/-0.000005, this may be the optimal answer. (Actually, this is the fraction I rounded to produce the starting decimal, and the remainder here is a rounding error).
7	-23074	33329	0.00001	3	0.0000000003	With greater accuracy, we have a large denominator. Going this far assumes that the initial decimal is actually 0.692310000
8	69231	-100000	0	-	0	The x's and y's are expressed as a decimal fraction, the same as 0.69231. This occurs when gcd=1

In seeking a vulgar fractional representation of a decimal fraction, we might often choose the fraction with the required accuracy or one with the accuracy of the expected accuracy of the original number.

Converting a Decimal Fraction to a Vulgar Fraction

Suppose we have a fraction:
a/b
Where a and b are integers, usually positive. We wish to express this fraction in the simplest fashion, say:
s/t
Where s and t are relatively prime.

a/b=s/t, or
at=bs
at-bs=0

We can always find integers s and t which are relatively prime and which suite this equation, according to Euclid's Extended Algorithm. (Often we refer to at-bs=1, but the at-bs=0 step always follows.)

Suppose also that
at-bs=c
Where c is a remainder in the steps of Euclid's Algorithm. We have proved that as the steps continue, c becomes smaller and smaller until it eventually becomes zero. Therefore, c represents the error in approximating the fraction a/b as s/t. As it becomes smaller, s/t approaches s/t and eventually c=0, when the error is also zero.

Using Decimals instead of Natural Numbers

Let us consider two trivial examples. First let
a/b=s/t=0.5, that is
s−0.5t=0 [3.1]

Now, Euclid's Algorithm says nothing about decimals, but we can multiply Equation 3.1 by 10 to get:
10s−5t=0 [3.2]

We can use natural numbers or we can continue to use decimals, because they are just a different number representation system.

Let us use decimals.
We have:
s/t=0.5
s−0.5t=0

Numerator and Denominator are Represented Differently

We can solve this equation, s−0.5t=0 , using Euclid, with the a=1 and b=0.5
We note that the first number in the table is always the larger. So the first number is 1, and the second 0.5

k	x	y	r	q
1	1	0	1
2	0	1	0.5	2
3	1	-2	0

The fraction 0.5 is therefore x/y, or 1/2. (Bear with me on these trivial examples!) Here the numerator is represented by y, but later we shall see this is not always the case.

Suppose we consider another fraction, 1.5 (that is an improper fraction).

here s=a=1.5 and t=b=1
We write the table for Euclid:

k	x	y	r	q
1	1	0	1.5
2	0	1	1	1
3	1	-1	0.5	2
4	-2	3	0

The fraction 1.5 is y/x or 3/2 (ignoring the signs).

Previously, when the decimal was less than 1, we had the fraction is x/y, but here, where the decimal is greater than 1, the fraction is y/x. Where x represented the numerator of the fraction, it here represents the denominator.

Sometimes, therefore, for instance in computer examples, we might choose to reverse the x and y's when the decimal is greater than 1, so the above table becomes:

k	y	x	r	q
1	1	0	1.5
2	0	1	1	1
3	1	-1	0.5	2
4	-2	3	0

And the fraction is still represented as x/y. As a computer program to convert decimals to fractions, the above algorithm has the advantage that arrays aren't necessary, and only a few values need to be stored.

Example

We seek to express 3.14159265 as a fraction. N represents the numerator and D the denominator. (The N is written before the D because the decimal is greater than 1, see above how the x's and y's reverse in Euclid's Algorithm.).

k	N_k	D_k	r_k	q_k	Error	Remarks
1	0	1	3.14159265
2	1	0	1	3
3	-3	1	0.14159265	7	0.1415926500
4	22	-7	0.00885145	15	0.0012644929	Accurate to 2 decimal places.
5	-333	106	0.0088209	1	0.0000832160
6	355	-113	0.00003055	288	0.0000002704	Accurate to 6 decimal places.
7	-102573	32650	0.0000225	1	0.0000000007	From now on the denominators become quite large.
8	102928	-32763	0.00000805	2	0.0000000002
9	-308429	98176	0.0000064	1	0.0000000001

Note how the errors become less and less as the steps increase. After the sixth step, the denominators become larger and larger, so 355/113 might be the best estimate, although for hundreds (or thousands) of years, 22/7 (Step 4) was used as a good estimate of π.

Number Theory Contents

Ken Ward's Mathematics Pages