2
$\begingroup$

I am curious when the following Definition was formulated. Is this a product of Dan Shanks' work?

The following algorithm computes the simple continued fraction expansion of $\frac{P+\sqrt{D}}{Q}$, where $D$ is a nonsquare positive rational and $P$, $Q\neq0$ are any integers. Let $P_0=P$, $Q_0=Q$, and $a_0=\left\lfloor \sqrt{D}\right\rfloor$. For $i\geq1$, define

$P_i=a_{i-1}Q_{i-1}-P_{i-1} \tag{A}$

$Q_i=\frac{D-P_i^2}{Q_{i-1}} \tag{B}$

$a_i=\left\lfloor \frac{P_i+\sqrt{D}}{Q_i} \right\rfloor. \tag{C}$

  • 0
    It could very well go back to Lagrange, or even to Euler.2012-03-01

2 Answers 2

3

It's a well-known ancient algorithm for computing the continued fraction of quadratic irrationals. Below is what Knuth says about the history in TAOCP vol. $2$, solution to exercise $4.5.3.12$ (which contains a complete derivation and proof of correctness)

enter image description here enter image description here

Probably much more can be said on the history. A good place to start is David H. Fowler's The Mathematics of Plato's Academy: A New Reconstruction (which, in addition to history, also provides a nice introduction to the main algebraic properties of continued fractions; see also Chrystal's Algebra).

  • 0
    @Jason Perhaps the result was proved earlier, did you check Dickson's History? In any case, there are plenty of simple proofs in elementary number theory that have not been presented simply because they have never been investigated.2012-03-02
2

It's not a definition, it's an algorithm. I first saw it in an early edition of the textbook by Niven and Zuckerman, but I don't know where they might have found it.

  • 0
    Ok definition of an algorithm but thank you.2012-03-01