3
$\begingroup$

Give the continued fraction expansion of two real numbers $a,b \in \mathbb R$, is there an "easy" way to get the continued fraction expansion of $a+b$ or $a\cdot b$?

If $a,b$ are rational it is easy as you can easily conver the back to the 'rational' form, add or multiply and then conver them back to continued fraction form. But is there a way that requres no conversation?

Other than that I found no clues whether there is an "easy" way to do it for irrational numbers.

$\endgroup$
3
$\begingroup$

Gosper found efficient ways to do arithmetic with continued fractions (without converting them to ordinary fractions or decimals). Here is a page with links to Gosper's work, but also with an exposition of Gosper's methods.

See also this older m.se question, Faster arithmetic with finite continued fractions

$\endgroup$
  • $\begingroup$ Thank you very much, this was exactly what I was looking for! $\endgroup$ – flawr Jan 2 '16 at 16:34
0
$\begingroup$

You need a representation of the real number to start with. Real numbers such as $e = \sum\frac1{n!}$ are easy to work with (in particular, using that representation). Real numbers such as $\gamma = \lim_{n\rightarrow\infty}\left(\sum_{k=1}^n\frac1k - \ln n\right)$ are going to be a bit "harder" to work with. And try real numbers such as "the number of nontrivial zeros of the Riemann zeta function".

You could start with a decimal expansion of a real number, but isn't that begging the question? A decimal expansion is a mediocre rational approximation. A continued fraction is a very good rational approximation. So you need to consume more and more decimal digits to be able to compute the next term of the continued fraction.

Rational numbers you can solve using Euclid's algorithm. Square roots are actually relatively easy and don't require any complex operations. I'm not sure about other algebraic numbers.

You can write an "explicit" formula down for an arbitrary real number using a lot of floor functions.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.