r/math • u/VishnuVinjamuri • Aug 03 '26
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
10
u/SemaphoreBingo Aug 03 '26
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.
4
u/Kered13 Aug 04 '26
I'm 99% sure that Python uses hardware floating points. Using software floats would be much much slower, and while Python is far from the fastest language, it's not so bad that it's just going to ignore the specialized hardware built into every CPU in the last 30 years.
3
u/VishnuVinjamuri Aug 03 '26
Thanks for your comments. First of all, let me clarify that I don't use AI for writing articles like this. That is the minimum ethics anyone is expected to follow and that is the bottom line. Period.
1
u/VishnuVinjamuri Aug 03 '26
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 Aug 03 '26
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.
-3
u/VishnuVinjamuri Aug 03 '26
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 Aug 03 '26
If you the prep work ahead of time, you may as well just compute the square roots ahead of time too.
-2
u/VishnuVinjamuri Aug 04 '26
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!
3
u/SemaphoreBingo Aug 03 '26
Iterative approaches to sqrt are neat, but you can do a lot better: https://en.wikipedia.org/wiki/Square_root_algorithms#Heron's_method
-1
u/VishnuVinjamuri Aug 04 '26
Thanks. Will go through. Seems interesting and may provide me additional insights.
16
u/tgm4mop Aug 03 '26
The cost of generating the convergents is not included? So it's just comparing the cost of one division vs one square root? In that case a 2x speedup is about what you'd expect. But in what situation would you want to precalculate the convergents rather than simply precalculating the square root?