Big integer division efficiency

[Marian Kechlibar]

Dear GMP authors and geeks,

I work on an algebraic project (MPQS/SIQS/GNFS factorization algorithms)
that
depends a lot on effective big integer arithmetics. We use GMP library
for big
integer functionality.

One of the main bottlenecks in our code is a loop that needs to call the
function

*mpz_fdiv_qr_ui* 

very often (more than million times a second). This is an internal
feature of the
algorithms used, and cannot be circumvented. The number being divided is
a large decimal number with 30-130 decimal positions, and the divisor is
a small prime number, usually smaller than 2^24.

Now our code spends about 40 percent time, in some circumstances more,
doing this operation. I would therefore like to know whether the
dividing function
in GMP is already optimized (with regard to the current algorithmic
state-of-the-art),
or whether the declared improvement in GMP 5.0 ("all algorithms will be
sub-quadratic)
also concerns this dividing function. In the latter case, we might be
pushed to develop
some function like that ourselves, since the expected horizont of GMP
5.0 ("several
years") is too far for us.

Can you give me some "insider" information on the function? I am not an
assembler
hacker and the assembler operations in the source are just black box for me.

Best regards

Marian Kechlibar