sec_karatsuba

[bodrato at mail.dm.unipi.it]

Ciao,

Il Mer, 12 Febbraio 2014 8:59 am, Niels ha scritto:
> bodrato at mail.dm.unipi.it writes:

>> I used evaluation in +1 instead of -1, to avoid branches due to the
>> sign,
>
> For the -1 point, one could use mpn_sub + mpn_cnd_neg to compute
> |a-b|. And then also conditonally negate and sign-extend the
> corresponding product. I don't know what's best, it's a couple of
> negations vs an extra limb in the product.

Unfortunately, I had not the time to try with the -1 option, but I believe
+1 is faster. The couple of negation (plus one more for the result) are a
linear cost in the number of limbs of the operand.
The extra limb is a linear cost only if the product cost is quadratic, and
it's under-linear above the Karatsuba range...

Regards,
m

-- 
http://bodrato.it/