CODEWITHSUNDEEP
algorithmmathprecisionrational-numbercontinued-fractions
Sophie
Sophie

Reputation: 131

Finding the continued fraction of 2^(1/3) to very high precision

Here I'll use the notation

enter image description here

It is possible to find the continued fraction of a number by computing it then applying the definition, but that requires at least O(n) bits of memory to find a0, a1 ... an, in practice it is a much worse. Using double floating point precision it is only possible to find a0, a1 ... a19.

An alternative is to use the fact that if a,b,c are rational numbers then there exist unique rationals p,q,r such that 1/(a+b*21/3+c*22/3) = x+y*21/3+z*22/3, namely

enter image description here

So if I represent x,y, and z to absolute precision using the boost rational lib I can obtain floor(x + y*21/3+z*22/3) accurately only using double precision for 21/3 and 22/3 because I only need it to be within 1/2 of the true value. Unfortunately the numerators and denominators of x,y, and z grow considerably fast, and if you use regular floats instead the errors pile up quickly.

This way I was able to compute a0, a1 ... a10000 in under an hour, but somehow mathematica can do that in 2 seconds. Here's my code for reference 

#include <iostream>

#include <boost/multiprecision/cpp_int.hpp>
namespace mp = boost::multiprecision;

int main()
{
    const double t_1 = 1.259921049894873164767210607278228350570251;
    const double t_2 = 1.587401051968199474751705639272308260391493;
    mp::cpp_rational p = 0;
    mp::cpp_rational q = 1;
    mp::cpp_rational r = 0;
    for(unsigned int i = 1; i != 10001; ++i) {
        double p_f = static_cast<double>(p);
        double q_f = static_cast<double>(q);
        double r_f = static_cast<double>(r);
        uint64_t floor = p_f + t_1 * q_f + t_2 * r_f;
        std::cout << floor << ", ";
        p -= floor;
        //std::cout << floor << " " << p << " " << q << " " << r << std::endl;
        mp::cpp_rational den = (p * p * p + 2 * q * q * q +
                                4 * r * r * r - 6 * p * q * r);
        mp::cpp_rational a = (p * p - 2 * q * r) / den;
        mp::cpp_rational b = (2 * r * r - p * q) / den;
        mp::cpp_rational c = (q * q - p * r)     / den;
        p = a;
        q = b;
        r = c;
    }
    return 0;
}

Upvotes: 3

Views: 543

Answers (2)

ptrj
ptrj

Reputation: 5222

The Lagrange algorithm

The algorithm is described for example in Knuth's book The Art of Computer Programming, vol 2 (Ex 13 in section 4.5.3 Analysis of Euclid's Algorithm, p. 375 in 3rd edition).

Let f be a polynomial of integer coefficients whose only real root is an irrational number x0 > 1. Then the Lagrange algorithm calculates the consecutive quotients of the continued fraction of x0.

I implemented it in python

def cf(a, N=10):
    """
    a : list - coefficients of the polynomial,
        i.e. f(x) = a[0] + a[1]*x + ... + a[n]*x^n
    N : number of quotients to output
    """
    # Degree of the polynomial
    n = len(a) - 1

    # List of consecutive quotients
    ans = []

    def shift_poly():
        """
        Replaces plynomial f(x) with f(x+1) (shifts its graph to the left).
        """
        for k in range(n):
            for j in range(n - 1, k - 1, -1):
                a[j] += a[j+1]

    for _ in range(N):
        quotient = 1
        shift_poly()

        # While the root is >1 shift it left
        while sum(a) < 0:
            quotient += 1
            shift_poly()
        # Otherwise, we have the next quotient
        ans.append(quotient)

        # Replace polynomial f(x) with -x^n * f(1/x)
        a.reverse()
        a = [-x for x in a]

    return ans

It takes about 1s on my computer to run cf([-2, 0, 0, 1], 10000). (The coefficients correspond to the polynomial x^3 - 2 whose only real root is 2^(1/3).) The output agrees with the one from Wolfram Alpha.

Caveat

The coefficients of the polynomials evaluated inside the function quickly become quite large integers. So this approach needs some bigint implementation in other languages (Pure python3 deals with it, but for example numpy doesn't.)

Upvotes: 2

David Eisenstat
David Eisenstat

Reputation: 65508

You might have more luck computing 2^(1/3) to high accuracy and then trying to derive the continued fraction from that, using interval arithmetic to determine if the accuracy is sufficient.

Here's my stab at this in Python, using Halley iteration to compute 2^(1/3) in fixed point. The dead code is an attempt to compute fixed-point reciprocals more efficiently than Python via Newton iteration -- no dice.

Timing from my machine is about thirty seconds, spent mostly trying to extract the continued fraction from the fixed point representation.

prec = 40000
a = 1 << (3 * prec + 1)
two_a = a << 1
x = 5 << (prec - 2)
while True:
    x_cubed = x * x * x
    two_x_cubed = x_cubed << 1
    x_prime = x * (x_cubed + two_a) // (two_x_cubed + a)
    if -1 <= x_prime - x <= 1: break
    x = x_prime

cf = []
four_to_the_prec = 1 << (2 * prec)
for i in range(10000):
    q = x >> prec
    r = x - (q << prec)
    cf.append(q)
    if True:
        x = four_to_the_prec // r
    else:
        x = 1 << (2 * prec - r.bit_length())
        while True:
            delta_x = (x * ((four_to_the_prec - r * x) >> prec)) >> prec
            if not delta_x: break
            x += delta_x
print(cf)

Upvotes: 1

Related Questions