2
$\begingroup$

I understand that there are algorithms (eg a famous one by Gosper) that generate, from certain pairs of continued fractions a, b, the continued fraction of the product.

I'm guessing that this algorithm only works for arguments with finite expansions, since I also read that these algorithms fail to generate 2 = [2;0,0,0,0,...] for the product of sqrt(2) = [1;2,2,2,2,...] with itself. I have a vague understanding of why they fail for this case, but I don't understand enough to know if this is a limitation of certain particular algorithms for if it is generally impossible to find an algorithm that generates the continued fraction of the product of any (i.e. possibly infinite, convergent) continued fractions.

$\endgroup$
2
  • 1
    $\begingroup$ It's true that boundary cases fail to produce output, but it is too harsh an assertion to say that Gosper's algorithm "only works" for finite expansions. You can see from his memo that he already had in mind the multiplication of two infinite continued fractions whose terms are generated algorithmically: if at any given stage there isn't enough precision to emit a term, it wil ingest more terms of the left/right factors. It just happens (and is acknowledged by Gosper) that in some cases, no amount of additional terms will suffice. $\endgroup$
    – Erick Wong
    Feb 2, 2018 at 16:28
  • $\begingroup$ Which is why having a halting problem oracle is equivalent to having an oracle for this problem. We can easily ensure that the interval of the next coefficient down to an arbitrarily small range, but with a halting problem oracle, we can say, "Will we every get it down to a range not containing an integer?" If we can't, we know the integer in the range is the coefficient, and the CF terminates there. If we can, we continue computing until we get to a small enough range with no integer, and take the floor of that range for the next coefficient. @ErickWong $\endgroup$
    – Thomas Andrews
    Feb 2, 2018 at 19:59

1 Answer 1

Reset to default
5
$\begingroup$

The answer is that no such algorithm can exist, because having such an algorithm lets you solve the halting problem.

For example, given a computer program $n$, you can write a computable continued fraction $[a_0,a_1,\dots]$ where $a_0=1$ and for $k>0,$ $a_k=2$ unless the program halts at step $n$ or earlier, then $a_k=2+(-1)^{k-1}$ (chosen so the resulting real number is $\leq \sqrt{2},$ with equality only when the program does not halt.)

Your algorithm would let us multiply this by $\sqrt{2}=[1,2,2,\dots]$ and we'd be able to solve the halting problem by whether the resulting continued fraction was $\geq 2$ or not.

Basically, your algorithm would have to "know" in a finite amount of time, and hence after perusing only a finite number of coefficients, whether a continued fraction would $\geq \sqrt{2}$. ($\sqrt{2}$ here is not special, just an easy example.)

It's almost trivially true, actually, that you can't figure out in finite time that a continued fraction is $\geq \sqrt{2}$. Presumably, we aren't even given an algorithm, just a stream of coefficients for our number $\alpha,$ so if $\alpha$ is actually $\sqrt{2}$, at what point do we figure out that $\sqrt{2}\alpha\geq 2$? If the algorithm figures this out after reading $n$ coefficients, then we can find infinitely many numbers $\beta<\sqrt{2}$ that agree with $\sqrt{2}$ in those coefficients, and thus will likewise return the same value.

I believe that if you can solve the halting problem (say, you are given an Oracle which solves it,) then you solve effective multiplication and addition of continued fractions. That is, you can write a program which:

  1. Takes two programs (which do not use the oracle) as input, which are interpreted as outputing two continued fractions.
  2. Outputs (using the oracle) a sequence of coefficients that represent the product (or sum.)
$\endgroup$
5
  • $\begingroup$ If I understand your explanation correctly, you are saying that no general algorithm can exist, because there will always be a way of constructing an example that fails. I can see that. But it is possible to modify Gosper's algorithm to only go for a certain number of rounds before emitting some value. This won't fix the problem - sqrt(2)*sqrt(2) returns a series of convergents [1,2,1,2,1,2,...] which never converge - but it ensures that the algorithm makes "progress" (albeit in a circle...). What I've never seen is any theoretical analysis of such a hack. Is there any such analysis? $\endgroup$
    – Paul Moore
    Feb 8, 2018 at 14:23
  • $\begingroup$ The problem is that if you halt after some number of steps, you are not only getting the wrong answer in the cases where it can't be solved, you are also getting the wrong answer in some cases here you can get a right answer. If you stop computing $\sqrt{2}\cdot \sqrt{2}$ after reading $n$ coefficients, you also stop computing $a*b$ for any $a,b$ that agree with $\sqrt{2}$ for the first $n$ coefficients. $\endgroup$
    – Thomas Andrews
    Feb 8, 2018 at 15:11
  • $\begingroup$ You can certainly come up with all sorts of imperfect continued fraction arithmetic. It would depend on your purpose for defining such things what imperfections you choose. $\endgroup$
    – Thomas Andrews
    Feb 8, 2018 at 15:19
  • $\begingroup$ Actually, doing some further research I found a paper "Effective Continued Fractions" by David Lester, that explains a method of modifying Gosper's algorithm to address these cases. I can't say I understand the reasoning in there yet, but it does specifically look at the case of sqrt(2) * sqrt(2). $\endgroup$
    – Paul Moore
    Feb 9, 2018 at 16:21
  • $\begingroup$ I'd be deeply suspect about the claims in that paper, given that we can prove there is no such thing. $\endgroup$
    – Thomas Andrews
    Feb 9, 2018 at 19:32

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .