Euler Problem 64

This one was brutal. Initially I tried writing classes to do Square Roots of BigDecimal and Fractions of BigDecimal. What a Big mess. It was also a learning experience using Regex to find matching patterns in the results. Not pretty and pretty damn slow. My attempts usually ran for 20+ hours at a time.

After three weeks of always getting wrong answers, I started reading mathematical papers. This one caught my eye. Theorem 2.3 shows a method to determine length of a Continued Fraction. The paper even had a super short C routine that I translated for my purposes. No Big Decimal. No Regex. No need to import anything. Kind of embarrassing actually.

Works in about 6 seconds on verbose and 61 miliseconds with no reporting.

public String algorithm ()
    {
        int count = 0;
        for (int n = 1; n <= 10000; n++)
        {
            if ((int)Math.sqrt(n) == Math.sqrt(n))
                continue;
            int period = period_length(n);
            if (period % 2 != 0)
                count++;
            v.appendText(String.format("n:%d period:%d count:%d\n", n, period, count));
        }
        return String.format("\nAnswer = %s\n", String.valueOf(count));
    }
    public int period_length (int n)
    {
        int a_0, a, b, c, b_0, c_0, result=0;
        a_0 = (int) Math.sqrt(n);
        b = a_0;
        b_0 = b;
        c = n - a_0*a_0;
        c_0 = c;
        do
        {
            a = (a_0 + b) / c;
            b = a*c - b;
            c = (n - b*b) / c;
            result++;
        } while ((b != b_0) || (c != c_0));
        return result;
    }

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s