mpn_sqrtrem1

[Niels Möller]

"Marco Bodrato" <bodrato at mail.dm.unipi.it> writes:

> I decided to try an as-branch-free-as-I-can Karatsuba implementation for
> umul_ppmm in the simpler environment: mini-gmp.
>
> Apply the following patch, define UMUL_PPMM_USE_KARATSUBA, and experience
> a slowed-down, larger-code version of mini-gmp ;-D

> +    __x1 = (mp_limb_t) __ul * __vl;				\
[...]
> +    if (__vh)							\
> +      {								\
> +	__x2 += __x1;						\
> +	__ul += __x2 < __x1;					\
> +      }								\
> +    else							\
> +      {								\
> +	__ul -= __x1 > __x2;					\
> +	__x2 -= __x1;						\
> +      }								\

I think I'd arrange this as a branch free conditional negation +
sign-extend of __x1. If __vh represents sign as 0 or ~0, that would be
something like

  __x1 = (__x1 ^ __vh) - __vh;

Now {__vh, __x1} is a two-limb two's complement representation of the
product (__ul - __uh) * (__vl - __vh), where the notation in the latter
expression refers to the initial values of these variables. Which can be
accumulated into the final product.

But it still won't beat the plain version on any machine with a
reasonable mul-instruction.

/Niels

-- 
Niels Möller. PGP-encrypted email is preferred. Keyid 368C6677.
Internet email is subject to wholesale government surveillance.