Big integer division efficiency

[Paul Zimmermann]

> Our bottleneck is in the situation when you already "almost know for
> sure" that
> some value of Q(x) is smooth or partially smooth, because enough
> logarithms have
> aggregated for that x. We even know the precise primes from the factor base
> that divide Q(x): they are precisely those primes, for which their
> sieving indices
> collide with the offset of x within the sieving block. So, currently, I
> just walk
> through the FB, identify those primes whose sieving indices collide with
> the offset
> of x, and divide Q(x) with those primes. And it is precisely this
> process of division
> that is the bottleneck.

instead of dividing by each prime separately, I suggest you multiply those
primes together (using mpz_mul_ui, or even better using a product tree if
you have lots of them), and perform only one (exact) division.

Paul