Hacker News Reader

Comment by misja111 | Hacker News Reader

It probably has been tried already by someone, but how about this: all square roots can be written as repeating continued fractions [1]. With a bit of work, continued fractions can also be summed [2] and compared. Wouldn't this take less than exponential time?

[1] http://benpaulthurstonblog.blogspot.com/2012/05/estimating-s...

[2] https://www.jstor.org/stable/1969389

View on HN

The article points to a Facebook post that considers this method and then is subsequently invalidated [0].

The argument is that the continued fraction representation for sqrt(N) grows as O(lg(N) sqrt(N)), making the representation blow up.

[0] https://www.facebook.com/bshlgrs/posts/10215278471769811?com...

[1] https://mathworld.wolfram.com/PeriodicContinuedFraction.html...

You're assuming that the period will remain of manageable size. I see no reason why this should be the case.

Edit: Also found a more accessible website describing how to do arithmetic with continued fractions: https://perl.plover.com/yak/cftalk/. In case anyone wants to try it out.

In practice I think the problem is linear, in that the required precision is proportional to log maxValue, that would be enough for a certain answer.

It's just that a proof of this is considerably harder, since you can't just assume the fractional part of irrational numbers is random.

Without looking into the details, the problem might be that two n-bit numbers x and y might have continued fractions for sqrt(x) and sqrt(y) which differ very far along. Also, the continued fractions themselves can get more and more expensive to compute as you go along; possible exponentially more, but I'm not sure.

Also, two continued fractions are not necessarily easy to compare. It's not a positional notation like decimal or binary.

Can't resist mentioning my personal favorite expansion of a sqrt:

sqrt(1-x) = 1- \sum_n C(n)/2^(2n+1) x^(n+1)

where x is in (0,1) and C(n)=binomial(2n,n)/(n+1) is the n'th catalan number.

[Learned this from http://www.math.chalmers.se/~wastlund/coinFlip.pdf]

Continued fraction approxmations are not a separable monotonically increasing sequence like decimal approximations are (the approximation goes up and down and the error range overlaps other nearby fractions of the same size), so you have no idea when you can terminate a partial computation.

that is a really good point. What coding language/library is best at representing fractions as opposed to floating points. Even though there might be overhead storing the numerator and denominator, it would prove useful with this problem.

Reply on news.ycombinator.com