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;
}

### Like this:

Like Loading...

*Related*