sqrt algorithm

Marco Bodrato bodrato at mail.dm.unipi.it
Mon Aug 3 18:48:41 UTC 2015


On Mon, August 3, 2015 12:02 pm, Torbjörn Granlund wrote:

> I don't think I ever considered a sqrlo.

I remember I thought about it when we introduced mullo, and I concluded
that it was hard to obtain an efficient version... but I don't remember
why, so I can be wrong.

> All the *_basecase assembly code is a major PITA to write for all
> relevant CPUs.  The effort behind what we have today is considerable,

Do we need a sqrlo_basecase? The D&C version of sqrlo would use a full
squaring and a single mullo, so that the base_cases for sqrlo_dc are
sqr_basecase, mul_basecase and mullo_basecase.

Writing a working sqrlo based on the current mullo code should be easy.



More information about the gmp-devel mailing list