mul_fft, cleaning up some details of the code

[Marco Bodrato]

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