CIT 591 Second Java Assignment: Fractions
CIT 591, David Matuszek, Fall 2002

Purpose:

(I know we haven't covered arrays yet. We will cover enough material by this Wednesday for you to get started on this assignment.)

The Math:

Everyone knows how to change a fraction, such as 7/12, into a decimal number: you simply divide the denominator into the numberator, to get 0.5833333.... However, a related technique that is no longer taught (in American schools, at least), is how to go the other direction: Given a number such as 0.5833333, how do you convert it to a fraction?

The usual (poor) answer is to put it over some power of ten: 58/100, or 583/1000, and so on. This technique will never give you 7/12.

The correct technique is based on inverting the number, that is, dividing it into 1. For example, if you take 0.25 and divide it into 1, you get 4.00000, and you can conclude immediately that the fraction is 1/4.

What happens if we try this with 0.5833333? On my calculator, 1 divided by 0.5833333 gives 1.7142858. This doesn't look promising, but by the above logic our fraction must be 1/1.7142858. Looked at another way, the fraction must be 1/(1+x), where x i 0.7142858, or the fractional equivalent. So let's do the same trick again with 0.7142858: Dividing 1 by 0.7142858 gives 1.3999998. Hence, our fraction becomes 1/(1+(1/1.3999998)).

We can stop this process at any point and turn the result into an ordinary fraction (with a single numerator and a single denominator) by repeatedly using the following formula:

1/(x + y/z) = z/(zx + y)

Let's follow this process out for 0.5833333. To shorten our discussion, we'll use x to represent the number 0.5833333. We get:

1 / 0.5833333 = 1.7142858, so x = 0 + 1/(1 + 0.7142858)
1 / 0.7142858 = 1.3999998, so x = 0 + 1/(1 + 1/(1 + 0.3999998))
1 / 0.3999998 = 2.5000012, so x = 0 + 1/(1 + 1/(1 + 1/(2 + 0.5000012)))
1 / 0.5000012 = 1.9999952, so x = 0 + 1/(1 + 1/(1 + 1/(2 + 1/(1 + 0.9999952))))
1 / 0.9999952 = 1.0000048, so x = 0 + 1/(1 + 1/(1 + 1/(2 + 1/(1 + 1/(1 + 0.0000048)))))
1 / 0.0000048 = 208333.33, so x = 0 + 1/(1 + 1/(1 + 1/(2 + 1/(1 + 1/(1 + 1/(208333 + 0.33))))))

We could continue this process, but the number 1/208333.33 is such a tiny correction that it hardly seems worth it. (In fact, the only reason we got this far is because of roundoff errors in the calculator; with perfect accuracy, we would have gotten 1.0000000 instead of 0.9999952 in an earlier step.) Hence we ignore this final term and use:

x = 0 + 1/(1 + 1/(1 + 1/(2 + 1/(1 + 1/(1 + 1/(208333 + 0.33)))))) =
x = 0 + 1/(1 + 1/(1 + 1/(2 + 1/(1 + 1/(1                   ))))))


Notice that the numerators are always 1. This is because of the way we created this very complicated fraction: we always divided into 1, so the numerator must always be 1. Using the 0 at the beginning and looking only at the denominators, we get:

x = 0 + 1/(1 + 1/(1 + 1/(2 + 1/(1 + 1/(1                   ))))))
    0      1      1      2      1      1


(Notice that we treat the whole number part of our decimal number, for example the 0 of 0.5833333, as the first denominator.) Working from right to left (most deeply nested first), we can repeatedly apply 1/(x+y/z) = z/(zx+y). Hence,

 
x = 0 + 1/(1 + 1/(1 + 1/(2 + 1/(1 + 1/1))))
                             -----------
                             1/(1*1+1) = 1/2
x = 0 + 1/(1 + 1/(1 + 1/(2 + 1/2)))
                      -----------
                      2/(2*2+1) = 2/5
x = 0 + 1/(1 + 1/(1 + 2/5))
               -----------
               5/(5*1+2) = 5/7
x = 0 + 1/(1 + 5/7))
        -----------
        7/(7*1+5) = 7/12
x = 0 + 7/12
    --------
    7/12

If we try this same trick with pi, 3.141592653589793, we get the sequence of denominators: 3, 7, 15, 1, 292, 1, 1, 1, 2, 1, 3, 1, 14. The number may be considered to be a "measure of goodness" of the fractional approximation. Hence, stopping just before 15 gives us 22/7; stopping just before the 292 gives us 355/113. The numbers towards the end of this sequence become unreliable, as they depend more and more on the accuracy of the decimal representation.

     pi = 3.14159265
   22/7 = 3.14285714
355/113 = 3.14159292

The Algorithm:

To turn this into a reasonable algorithm, we only need to deal with the denominators. We first calculate as many denominators as we need (counting the whole number part as a denominator), moving in a "forward" direction, for example,

    0      1      1      2      1      1

You should be able to figure out the algorithm from the examples above; it's a matter of repeatedly (1) taking off and saving the whole number part, and (2) inverting the fractional part. The whole number part of our input number, regardless of its value, will be our first "denominator."

Then we need three simple variables, which we will call temp (for temporary"), numerator, and denominator. Assign to them the initial values of numerator = 1, temp = 0 (denominator doesn't matter). Then repeatedly execute the following instructions:

denominator = numerator;
numerator = (numerator * last-unused-denominator) + temp;
temp = denominator;

where last-unused-denominator takes on the denominator values in reverse order: (1, 1, 2, 1, 1, 1, 0) for 7/12, or (14, 1, 3, 1, 2, 1, 1, 1, 292, 1, 15, 7, 3) for pi. When you finish (by using up the first denominator in the sequence), your final fraction is given by numerator and denominator. (For numbers greater than 1.0, this will be a so-called "improper fraction," where the numerator is larger than the denominator. Ignore what your elementary school teachers told you about this being "improper," there's nothing wrong with such a fraction.)

This is a highly condensed (and hard to figure out!) version of what we were doing above with complicated fractions. Feel free to derive it yourself; or, just take it on faith (but check your results!).

Your Assignment:

Write an application that:

  1. Prints out your name. (Actually, you should do this with any assignment.)
  2. Gets a double to use as the decimal number to be converted to a fraction. Print out this number.
  3. For N = 1, 2, 3, ....
    1. Compute N denominators for this number. Print these out on a single line.
    2. With these N denominators, calculate and print out:
      1. N
      2. The fraction that results from using these denominators.
      3. The decimal value of this fraction (just do the division).
      4. A "measure of goodness," which is just the integer part of what the next denominator would be.
      5. The "percentage error," calculated from 100 * Math.abs(computedValue - actualValue) / actualValue. Please display this as an integer.
    3. Stop when either (1) you have calculated 12 fractional approximations for this number, or (2) you have a measure of goodness greater than 20.

It might be easiest if you just go ahead and compute all the denominators first, then go through and use the first one, then do it again using the first two, then do it again using the first three, etc. You don't have to print things in exactly the order specified above, so long as you print all the information, for several fractional approximations to the input number.

Here's how to get a double to use:

To break a number up into the integer (whole number) part and the decimal fraction part:

  1. Cast the number to an int. This give you the whole number part.
  2. Subtract the int from the original number to get the decimal fraction part.

Due: Wednesday, October 2, via Blackboard.

Your program must work correctly to receive a nonzero grade. In addition, you should follow style rules 5, 6, 7, and 25, and you should avoid using "magic numbers" in your code.