mul_fft, cleaning up some details of the code
bodrato at mail.dm.unipi.it
Sun Mar 6 11:14:49 CET 2022
I looked into the code published by Samuel Vivien.
I realised that in mul_fft there are a lot of _add_1 and _sub_1. At
least some of them can be easily replaced by _INCR_U or _DECR_U...
Specifically I'd focus into a suspicious piece of code, shared by both
our current code and Vivien's.
The function mpn_mul_fft_decompose has a branch "if (dif > Kl)", that
ends with the following lines:
if (cy >= 0)
cy = mpn_add_1 (tmp, tmp, Kl, cy);
cy = mpn_sub_1 (tmp, tmp, Kl, -cy);
Can those lines be correct? Can the value in cy be used after this code
both if it contains the carry or if it contains the borrow of the
operation on tmp?
I believe this is an error, I'd change the last line into
cy = 1 - mpn_sub_1 (tmp, tmp, Kl, -cy - 1);
and I propose the attached patch changing this and some other _1
This is not really needed to solve a bug.
The comment before the mpn_mul_fft_decompose function says "We must have
nl <= 2*K*l", this means that we should never have ((dif = nl - Kl) >
Kl), and the code in that branch should never be used.
According to the coverage analisys, the code is not explored by the
The "bug" is never triggered.
Maybe the branch could be used if someone re-enables mpn_mul_fft_full
and uses it for very unbalanced (more than 4x1) operands?
-------------- next part --------------
A non-text attachment was scrubbed...
Size: 4103 bytes
Desc: not available
More information about the gmp-devel