Hello Hironobu-san,
> However, the implementation of the scatter operation in this patch overflows
> in many cases if the variable:size is 38 bit integer or greater. Because the
> variable:size and the item of the array:primes[] which stores 27-29 bit
> integers are multiplicated. If overflow occurs, the scatter operation does
> not satisfy bijective.
Indeed. Again, thanks for the debug! As you contributed some code, I added
you as a co-author in the CF entry.
Attached a v3, based on your fix, plus some additional changes:
- explicitly declare unsigned variables where appropriate, to avoid casts
- use smaller 24 bits primes instead of 27-29 bits
- add a shortcut for multiplier below 24 bits and y value below 40 bits,
which should avoid the manually implemented multiplication in most
practical cases (tables with over 2^40 rows are pretty rare...).
- change the existing shortcut to look a the number of bits instead of
using 32 limits.
- add a test for minimal code coverage with over 40 bits sizes
- attempt to improve the documentation
- some comments were updates, hopefully for the better
The main idea behind the smaller primes is to avoid the expensive modmul
implementation on most realistic cases.
--
Fabien.