3 ms·

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, con

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-square-roots.html http://benpaulthurstonblog.blogspot.com/2012/05/estimating-s... [2] https://www.jstor.org/stable/1969389 https://www.jstor.org/stable/1969389

mihaic 5y ago
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.
ogogmad 5y ago
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.
contravariant 5y ago
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/ https://perl.plover.com/yak/cftalk/. In case anyone wants to try it out.
lupire 5y ago
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.
Q_is_4_Quantum 5y ago
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 http://www.math.chalmers.se/~wastlund/coinFlip.pdf]
abetusk 5y ago
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?comment_id=10215291928186213&comment_tracking=%7B%22tn%22%3A%22R%22%7D https://www.facebook.com/bshlgrs/posts/10215278471769811?com... [1] https://mathworld.wolfram.com/PeriodicContinuedFraction.html?fbclid=IwAR12CeFXoVpQ7JPvc2pMI_aQ3P79BSDYLHnv9AAaZO8dmtpr7HIej1Cn2nc https://mathworld.wolfram.com/PeriodicContinuedFraction.html...
whoomp12342 5y ago
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.

mihaic 5y ago

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.

ogogmad 5y ago

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.

contravariant 5y ago

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/ https://perl.plover.com/yak/cftalk/. In case anyone wants to try it out.

lupire 5y ago

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.

Q_is_4_Quantum 5y ago

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 http://www.math.chalmers.se/~wastlund/coinFlip.pdf]

abetusk 5y ago

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?comment_id=10215291928186213&comment_tracking=%7B%22tn%22%3A%22R%22%7D https://www.facebook.com/bshlgrs/posts/10215278471769811?com... [1] https://mathworld.wolfram.com/PeriodicContinuedFraction.html?fbclid=IwAR12CeFXoVpQ7JPvc2pMI_aQ3P79BSDYLHnv9AAaZO8dmtpr7HIej1Cn2nc https://mathworld.wolfram.com/PeriodicContinuedFraction.html...

whoomp12342 5y ago

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.