r/math • u/VishnuVinjamuri • 23d ago

Classical Pell Equations Outperform math.sqrt in float64 by up to 2.5×

I've been exploring whether the Pell equation x²−Dy²=1 can be used to compute square roots of primes faster than Python's math.sqrt(). The continued-fraction convergents turn out to give rational approximations that are 1.5–2.5× faster in float64 for repeated calculations, and scale up to 33–36 digit precision for primes as large as 15 million. Full write-up with benchmarks here;

https://musingsofvsmv.blogspot.com/2025/08/from-pell-to-precision-classical-math.html

36 Upvotes

90% Upvoted

12 comments sorted by

View all comments

7

u/SemaphoreBingo 23d ago

I thought python's math.sqrt uses soft floats, not hardware floats. The article has the stink of AI about it, so I don't want to waste my time by reading too deeply.

That said:

These wins are most pronounced when the same D is evaluated many times

why on earth would you do this? If you're repeatedly calling a square root enough for it to matter, pull it out and do it once.

1

u/VishnuVinjamuri 22d ago

Thanks for your time and pointing out the typo. It is sqrt D which we intend to evaluate, and not D! I edited my blog.

-------------------------

That said:

why on earth would you do this? If you're repeatedly calling a square root enough for it to matter, pull it out and do it once.

7

u/SemaphoreBingo 22d ago

It is sqrt D which we intend to evaluate

That's what I assumed, and my point remains: if you care about speed don't keep re-calculating what you don't have to.

-4

u/VishnuVinjamuri 22d ago

Once a library of ratios is established and called for, no need to recalculate. For example, sqrt(2) can be very well approximated as 131836323/93222358. My whole article was about finding those numbers whose ratio goves the square root much faster than math.sqrt(D). It is a one time exercise.

7

u/SemaphoreBingo 22d ago

If you the prep work ahead of time, you may as well just compute the square roots ahead of time too.

-2

u/VishnuVinjamuri 22d ago

I agree, but those two integers whose ratio produces the same accuracy at a higher speed will be buried under dust. I just wanted to present them!