From Six Operations

That brings us to the main event, the discussion of individual operations. The first six come from Six Operations. Do you need to go read that? Not really—most of what's there is also here. Also, if you do go, remember that in that context the first coefficient had to be positive.

For these operations we'll be thinking of the expansion as a data structure, like an array or a linked list.

1. To concatenate two expansions, …

   Method C (atomic): multiply the matrices.

   Method D (composite): if the left operand consists of a single coefficient, take the reciprocal of the right operand and then add the single coefficient (arithmetically).

   We have used this method and method 6D in More About Symmetry and other places.

   Note #1 about composite methods: You might think that composite methods wouldn't need to check for excluded cases, that if the operation as a whole didn't make sense, then one of the component operations would just naturally fail. Well, method 1D is a counterexample, the only one we're going to see. If we remove the checks, the method succeeds in cases Z and N and produces results that are guaranteed to be incorrect because there are no correct results. Case Z is particularly easy to understand. The method does still fail for the specific continued fraction [0], though.

2. To reverse an expansion, take the transpose of the matrix.
3. To get the first coefficient, …

   Method F (atomic): divide down the first column and take the integer part by applying the floor function.

   The math doesn't work for case II. We can fix that after the division by checking and maybe subtracting 1, as described in Six Operations, or we can fix it before the division by performing the first classification. As in the “better way” above, in cases PI and II we can just take the first coefficient directly from the matrix. It's only in case NE that we need to divide.

   Method H (atomic): do the same thing, but use the second column. In general, that actually works, since using the second column has the same effect as removing the last coefficient.

   pn	/	qn	= [a0, a1, a2, … , an−3, an−2, an−1, an]
   pn−1	/	qn−1	= [a0, a1, a2, … , an−3, an−2, an−1]

   There are three special cases, L0, PI, and S3.

   • I'm not supposed to talk about case L0.
   • As above, we can handle case PI (and case II) by taking the first coefficient directly from the matrix.
   • For case S3, we can get a₀+1 from the matrix and then subtract 1.
4. To get the last coefficient, …

   Method E (composite): reverse the expansion and then get the first coefficient.

   Method F (atomic): amalgamate the two operations in method E. In other words, divide across the first row and take the integer part by applying the floor function. In even more other words, do the same thing as in method 3F, but transposed.

   Since the method is transposed, the special case is also transposed, or rather reversed: case RII. We can fix it before or after the division, just as above.

   That all sounds pretty good. Unfortunately, it doesn't take into account what happens in cases Z and N. Method E just fails. Method F usually involves division by a negative number, but, for reasons we shouldn't delve into lest we awaken balrogs, still mostly works. However, the zone where it doesn't work is a hodgepodge of nonstandard special cases that are difficult to detect, so in practice the method is unusable.

   What should we do? Here's the obvious solution.

   Method G (composite): make method E more composite by adding a block of code to handle cases Z and N.

   if (Z or N) {
      getFirst
      removeFirst
   }
   reverse
   return getFirst

   But what if we remove the first coefficient and then there aren't any coefficients left? We can avoid getting into that situation by adding another block of code up front.

   if (PI) {
      return getFirst
   }

   Although that works, it's not pretty. Here's the pretty solution.

   Method H (atomic): do the same thing as in method F, but use the second row. Equivalently, do the same thing as in method 3H, but transposed. Either way, that works well, since the second row contains the denominators, and the denominators are always positive. In fact, using the denominators has exactly the same effect as removing the troublesome first coefficient!

   p_n / p_n−1 = [a_n, a_n−1, a_n−2, … , a₃, a₂, a₁, a₀]
   q_n / q_n−1 = [a_n, a_n−1, a_n−2, … , a₃, a₂, a₁]

   (For more about those equations, see The Discriminant.)

   As before, since the method is transposed, the special cases are also transposed. Fortunately, the special cases from method 3H, namely L0, PI, and S3, all look the same when transposed and can be handled in more or less the same way.

5. To remove the last coefficient, …

   Method A (atomic): multiply by P₁(a)⁻¹ on the right. If you don't already know the coefficient, then the first step is to get it, and the method is composite.

   Method B (composite): reverse, remove the first coefficient, and reverse. (It's not a good method.)

   Note #2 about composite methods: Composite methods must fail in excluded cases, but in theory they might fail in other cases as well. In practice, they fail in cases Z and N for the three methods 4E, 5B, and 6B that start by reversing the expansion. Why would we want methods that fail? Well, first, they're simple, and they work just fine if you happen to know that the first coefficient is positive. Second, I already mentioned two of them in Six Operations. Third, we need method 4E as the first step on the way to better methods for operation 4.

6. To remove the first coefficient, …

   Method A (atomic): multiply by P₁(a)⁻¹ on the left. If you don't already know the coefficient, then the first step is to get it, and the method is composite.

   Method B (composite): reverse, remove the last coefficient, and reverse. It's not a good method, I only mention it here to be consistent with Six Operations.

   Method D (composite): subtract the coefficient and then take the reciprocal. If you don't already know the coefficient, then the first step is to get it, and the method is even more composite.

   We have used this method and method 1D in More About Symmetry and other places.

The seventh operation also comes from Six Operations. I kept it separate because it takes linear time (in terms of expansion length, not the obvious parameter for a matrix), while the other operations take constant time. The original idea was that the other operations required no more than one matrix multiplication each, but that's not exactly true any more.

1. To get the whole expansion, …

   Method J (composite): get the first coefficient, remove it, and repeat.

   Method K (composite): run the first algorithm (essentially the Euclidean algorithm) on the value from the first column and then check whether the expansion is proper or improper. We can check directly by getting the last coefficient, as in Six Operations, or we can check indirectly by computing the determinant, which is 1 for even length and −1 for odd length.

   This method is essentially the same as method J. The difference is that in that method we check for special cases at every step, special cases that mostly don't occur, while in this method we check for special cases only at the start (L0).

   Method L (composite): get the last coefficient, remove it, and repeat.

   Method M (composite): run the algorithm from Matrices That Represent Continued Fractions, which is essentially the Euclidean algorithm applied to the denominators from the second row.

   This method is essentially the same as method L. Again, the difference is that in that method we check for special cases at every step, special cases that mostly don't occur, while in this method we check for special cases only at the start.

   In fact, we only need to check for case L0. In Matrices That Represent Continued Fractions we also needed to check for cases PI and II, but here the non-exception case of the algorithm is able to handle them, partly because we already know that the matrix represents a continued fraction.

   Finally, let's compare and contrast methods K and M a little. Earlier we saw these methods for getting coefficients.

   	first	second
   column	3F	3H
   row	4F	4H

   Method 3F was slightly nicer than method 3H, but method 4F was unusable due to cases Z and N. That's why method K uses the entries in the first column, but method M uses the entries in the second row.

   It's also interesting that method K checks whether the expansion is proper or improper, but method M doesn't. The reason is that an equivalent check is built into the algorithm from Matrices That Represent Continued Fractions. If the assumed parity of the expansion length is wrong, we get into trouble and have to backtrack one step.

The eighth operation is a bonus!

2. To get the length of an expansion, get the whole expansion and then check how long it is. I don't think there are any shortcuts.