On 10/3/2015 2:38 AM, Andrew Haley wrote:
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.
For an initial implementation, I think it is acceptable to use a simple
algorithm that is clearly correct. That algorithm can then be replaced
with faster ones once adequate tests are built up (with the original
implementation perhaps retiring to the regression tests area where it
can be used for comparison purposes).
-Joe
