Wolfram|Alpha

Computing...

Input interpretation:

Gosper\'s digit-based continued fraction arithmetic (continued fraction result)


Continued fraction algorithm:

Given two regular continued fraction expansions for real numbers A and B\nA = a_0 + (continued fraction k)_(k=1)^(n_A) 1\/a_k\nB = b_0 + (continued fraction k)_(k=1)^(n_B) 1\/b_k\n(with n_A and\/or n_B possibly infinity), an arithmetic operation f (addition, subtraction, multiplication, and division) can be carried out on the sequences of partial denominators {a_k}_(k=0)^(n_A) and {b_k}_(k=0)^(n_B) directly to obtain the partial denominators c_k of\nC = f(A, B) = c_0 + (continued fraction k)_(k=1)^(n_C) 1\/c_k.\nMore generally, the partial denominators c_k of the expression\nC = f(A, B) = (a A B + b A + c B + d)\/(e A B + f A + g B + h)\n(with the special cases for two continued fractions\naddition | a = 0 | b = 1 | c = 1 | d = 0 | e = 0 | f = 0 | g = 0 | h = 1\nsubtraction | a = 0 | b = 1 | c = -1 | d = 0 | e = 0 | f = 0 | g = 0 | h = 1\nmultiplication | a = 1 | b = 0 | c = 0 | d = 0 | e = 0 | f = 0 | g = 0 | h = 1\ndivision | a = 0 | b = 1 | c = 0 | d = 0 | e = 0 | f = 0 | g = 1 | h = 1\nfor the basic arithmetic operations)\nfor given rational expressions a, b, c, d, e, f, g can be computed directly from the partial denominator sequences {a_k}_(k=0)^(n_A) and {b_k}_(k=0)^(n_B).\nObserving that the expression\n(a A B + b A + c B + d)\/(e A B + f A + g B + h)\n(i) under the substitution A->a_k + 1\/A changes as\n(a(a_k + 1\/A) B + b(a_k + 1\/A) + c B + d)\/(e(a_k + 1\/A) B + f(a_k + 1\/A) + g B + h) = ((c + a a_k) A B + (d + b a_k) A + a B + b)\/((g + e a_k) A B + (h + f a_k) A + e B + f), \n(ii) under the substitution B->b_k + 1\/B\n(a A(b_k + 1\/B) + b A + c (b_k + 1\/B) + d)\/(e A(b_k + 1\/B) + f A + g (b_k + 1\/B) + h) = ((b + a b_k) A B + a A + (d + c b_k) B + c)\/( (f + e b_k) A B + A e + (h + g b_k) B + g), \n(iii) and\n1\/( (a A B + b A + c B + d)\/(e A B + f A + g B + h) - c_k) = (e A B + f A + g B + h)\/((a - e c_k) A B + (b - f c_k) A + (c - g c_k) B + (d - h c_k))\nshows the shape invariance of the expression\n(a A B + b A + c B + d)\/(e A B + f A + g B + h)\nunder the operations (i), (ii), and (iii).\nThe two substitutions A->a_k + 1\/A and B->b_k + 1\/B can be thought as using the kth partial denominators and denoting the remainders by the symbolic variable A or B.\nThe operation (iii) can be interpreted as extracting the kth digit c_k from F(A, B).\nObserving that substituting A->a_k + 1\/A and B->b_k + 1\/B repeatedly (a_k, and b_k are positive integers from the regular continued fraction expansions of A and B) into an expression of the form\n(a A B + b A + c B + d)\/(e A B + f A + g B + h)\nand denoting the result of this substitution by\ng({a, b, c, d, e, f, g}, {a_k, a_(k + 1), ..., a_(k + m)}, {b_j, b_(j + 1), ..., b_(j + n)})\nand taking into account that the remainders A and B are bounded from below by 1, allows to bound this expression from above and below. For sufficiently large m and n, there exists an integer omega such that\nomega<=g({a, b, c, d, e, f, g}, {a_k, a_(k + 1), ..., a_(k + m)}, {b_j, b_(j + 1), ..., b_(j + n)})<omega + 1.\nThen omega is the next partial denominator of the regular continued fraction expansion of f(A, B).\nSo, applying (possibly multiple times) (i) and (ii) and then (iii) repeatedly, allows to extract a continued fraction digit from F(A, B). This process can be repeated to obtain the sequence of partial denominators {c_k}_(k=0)^(n_C).

ComputingComputing...