ni...@lysator.liu.se (Niels Möller) writes:
I also had a quick look at the math, and I realized (some of you surely
knew that already) that floor(sqrt(a)) is mostly independent of the
lowest half of the bits of a.
Some of us indeed knew that... And this generalises to kth roots. It
is
t...@gmplib.org (Torbjörn Granlund) writes:
I haven't looked enough at your propposal to have an informed opinion.
Here's a sketch with some more details. I've tried to work out both
sqrt(B^{n-1} A) and sqrt(B^{n-2}). To my surprise, they seem
independent, not mutually recursive.
sqrt_nm1 (n,