Phase estimation hands back a fraction like 85/512, and the next step of period finding asks which simple fraction it is close to. Continued fractions answer that. Every fraction x = y/q \ge 0 can be written as
with whole numbers a_0 \ge 0 and a_1, a_2, \dots \ge 1, the terms. They come from this rule: a_0 = \lfloor x\rfloor; if x = a_0 stop, otherwise continue with x \leftarrow 1/(x - a_0) and repeat. Cutting the expansion after term a_k gives the convergent h_k/k_k, a fraction in lowest terms; the last convergent is y/q itself, reduced.
Write continued_fraction(y, q) that returns a pair (terms, convergents): the list of terms [a_0, a_1, \dots, a_n], and the list of convergents as pairs (numerator, denominator), one per term, in the same order.
The numbers get large (the tests go up to 2^{60}), so work with exact integers (//, %, or fractions.Fraction): floats give wrong terms after a few steps, even for 85/512.
Examples
Input: y = 85, q = 512
Output: ([0, 6, 42, 2], [(0, 1), (1, 6), (42, 253), (85, 512)])
Explanation: 85/512 = 0 + 1/(6 + 1/(42 + 1/2)). The convergent 1/6 is the simple fraction
hiding in 85/512. With floats, the expansion of 85/512 does not even stop after four terms.
Input: y = 3, q = 8
Output: ([0, 2, 1, 2], [(0, 1), (1, 2), (1, 3), (3, 8)])
Input: y = 0, q = 16
Output: ([0], [(0, 1)])
Constraints
0 <= y <= 2**61,1 <= q <= 2**61
Goals
- Expand a fraction into its continued-fraction terms with exact integer arithmetic
- Compute the convergents, the best simple fractions along the way