mul_fft, cleaning up some details of the code
Marco Bodrato
bodrato at mail.dm.unipi.it
Tue Mar 8 16:11:06 CET 2022
Ciao Paul,
Il 2022-03-08 12:56 Paul Zimmermann ha scritto:
>> Since you deeply know how this code works, I ask you one more
>> question.
>> The last lines of the function mpn_fft_mul_2exp_modF (branch m < n)
>> contain:
>>
>> /* now subtract cc and rd from r[m..n] */
>>
>> r[n] = -mpn_sub_1 (r + m, r + m, n - m, cc);
>> r[n] -= mpn_sub_1 (r + m, r + m, n - m, rd);
>> if (r[n] & GMP_LIMB_HIGHBIT)
>> r[n] = mpn_add_1 (r, r, n, CNST_LIMB(1));
>>
>> This code assumes that there can only be a single borrow. Is it
>> correct?
> yes there can only be a single borrow, since since cc is 0 or 1,
Uhm, the last line of code just before that ones is:
cc = mpn_sub_1 (r, r, m, cc) + 1;
/* add 1 to cc instead of rd since rd might overflow */
So that I'd say that cc is 1 or 2.
Then the case cc=2, m=n-1, r[m]=0, and rd=GMP_NUMB_MAX seems very very
unlikely, but possible.
> if r[n] is non zero after r[n] = -mpn_sub_1 (r + m, r + m, n - m, cc),
> this can only happen for cc=1 and {r+m,n-m} = 000...000 before the
> mpn_sub_1 call, and {r+m,n-m} = 111...111 after, then the second
> mpn_sub_1 call cannot produce a borrow.
Of course a second borrow may only happen if n-m=1,
i.e. if {r+m,n-m} contains a single limb.
Ĝis,
m
More information about the gmp-devel
mailing list