On 02/10/15 21:41, Brian Burkhalter wrote:
> Any suggestions as to the improvement of the approach concerning
> memory use or any other aspect of the algorithm would be
> appreciated, as would be suggestions regarding the test.
This algorithm doesn't look like the best to me because it's got this
slow division in the middle. If we calculate 1/sqrt(x) instead we can
use a version of Newton's iteration which requires no division.
Starting with an approximation y = 1/sqrt(x) using the first few digits,
y = y * (3 - x*y^2)
---------------
2
... and fix it all up with a single iteration of Heron's algorithm at the
end.
But even better is Karatsuba Square Root:
https://hal.inria.fr/inria-00072854/document
I guess it all depends on how much work we think this deserves. In
general the core algorithms in BigInteger are among the best, and it
would be nice to continue this tradition.
Andrew.
