sqrt algorithm

Marco Bodrato bodrato at mail.dm.unipi.it
Wed Jul 29 22:19:36 UTC 2015


On Wed, July 29, 2015 10:38 pm, Niels Möller wrote:
> Hmm, but if we shift to make the *root* normalized, that also means that
> the input will always be an even number of limbs. Not entirely sure
> that's good, in particular for smallish sizes. But it ought to simplify
> some things.

Current code adds a limb to odd-sized operands.

Assume we need the square root of a 7-limb number. Is it better to shift
it to 8 limbs and compute the higher 2 limbs of the result followed by the
lowest 2 limbs (we can use divappr, because we don't really need the
lowest bits)? Or ...compute the higher 1.5 limbs, then iterate twice?



More information about the gmp-devel mailing list