Ciao,
Il 2019-10-04 14:31 ni...@lysator.liu.se ha scritto:
Depends on the details... Say we start with r in canonical
Additive redc:
r' = (r^2 + q m) / B < m^2 / B + m
Subtractive redc:
r' = (r^2 - qm) / B, -m < r' < m^2 / B
This can obviously underflow, and if we check for that
Marco Bodrato writes:
No, there are branches in the code above, once compiled.
Note "gcc" on shell is clang, which produces much inferior code for GMP.
To see what gcc produces on shell, please use the commands gcc8, gcc7,
gcc6, etc.
(I should do something about that gcc points to clang.)
Il 2019-10-03 21:10 Marco Bodrato ha scritto:
Il Gio, 3 Ottobre 2019 8:39 am, Niels Möller ha scritto:
"Marco Bodrato" writes:
if (r0 <= (m0 >> 1))
r0 <<= 1;
else if (r0 >= m0)
r0 = (r0 - m0) << 1;
else
Ciao,
Il Gio, 3 Ottobre 2019 8:39 am, Niels Möller ha scritto:
> "Marco Bodrato" writes:
>> I implemented it with two variants of that portion:
>>
>> #ifdef BRANCHLESS
>> int cond1 = (r0 >= m0);
>> int cond2 = (r0 > (m0 >> 1));
>>
>> r0 -= m0 & -
"Marco Bodrato" writes:
> I implemented it with two variants of that portion:
>
> #ifdef BRANCHLESS
> int cond1 = (r0 >= m0);
> int cond2 = (r0 > (m0 >> 1));
>
> r0 -= m0 & - (mp_limb_t) cond1;
> r0 <<= 1;
> r0 -= m0 & -
Ciao,
Il Mer, 2 Ottobre 2019 3:29 pm, Torbjörn Granlund ha scritto:
> "Marco Bodrato" writes:
> I wrote the doubling-modulo step with 3 possible operations:
>if it can not overflow, simply lshift;
>otherwise choose between (x*2-m) and ((x-m)*2)
>
> Do you choose that at each step?
"Marco Bodrato" writes:
I tried... the attempt is attached.
I wrote the doubling-modulo step with 3 possible operations:
if it can not overflow, simply lshift;
otherwise choose between (x*2-m) and ((x-m)*2)
Do you choose that at each step? That might be a cause for delay due to
Ciao,
Il Gio, 19 Settembre 2019 10:39 pm, Marco Bodrato ha scritto:
>> Il Mer, 4 Settembre 2019 10:44 am, Niels Möller ha scritto:
>>> I think I've seen comments in the literature saying that 2^e mod m is
>>> "obviously" more efficient than general modular exponentiation. But as
> If nobody
Ciao,
Il Mer, 4 Settembre 2019 5:07 pm, Marco Bodrato ha scritto:
> Il Mer, 4 Settembre 2019 10:44 am, Niels Möller ha scritto:
>> I think I've seen comments in the literature saying that 2^e mod m is
>> "obviously" more efficient than general modular exponentiation. But as
> This means writing
