Limb size faking and limb type
tg at gmplib.org
Sat Dec 24 00:25:52 CET 2011
A good student has been implementing a C++ class mp_limb_t, overloading
the arithmetic operations, and allowing any even limb size <= long int.
The purposes of this project are:
1. Improve pseudo-random testing by finding more corner cases for n-limb
numbers, for any n.
2. Allow exhaustive search for several algorithms, up to some size.
To be combined with --enable-minithres.
3. Allow huge operations for triggering certain possible conditions in
the current Schönhage-Strassen FFT code, as well as Niels' new small
primes code which utilises Cooley-Tukey's multidimensional tricks
(nowadays often referred as Bailey's 4-step). Why does this allow
huge operands? Because 8-bit limbs take one byte of memory, while a
limb on a 64-bit machine need 8 bytes.
In order to make this work, we need to use mp_limb_t for just limbs, not
for sizes or other parameters. This includes exponents in powering, and
n in nth root computations. I have made most of the necessary changes.
The proper type to use is not entirely clear. Perhaps a plain 'unsigned
long' is the right type in most places. We might also use either
mp_bitcnt_1 or size_t.
As far as I know, no published interface is affected. If they are, we
need to decide what do to. (Retain the old interface, or make this
change which will be really minor in practice.)
A status page for the current porting status can be found here:
Note that 4-bit and 6-bit limbs don't work well yet. Any functions
accepting or returning 'double' fail. Then about 15 more failures
happen for individual functions.
We intend to commit these changes into the main GMP repository in the
next few months.
More information about the gmp-devel