View Single Post
Old 2015-11-16, 16:06   #4
R.D. Silverman
R.D. Silverman's Avatar
Nov 2003

22×5×373 Posts

Originally Posted by paul0 View Post
So there is an implicit "match the smooth pairs from both sides" step?
I don't know what you mean by "match the smooth pairs".

Initialize the sieve array. You sieve one side and identify which lattice points might be smooth.
Re-initialize by setting the values of those locations that can't be smooth to -oo, then sieve
the other side. You then identify which points might be smooth on the second side. Finally,
one attempts to factor those candidates that might be smooth on both sides. (i.e. the intersection
of the sub-lattices with just smooth points)

Note also that doing one side at a time reduces memory and makes bucket sieving a lot easier.

Note also that sieving both sides at the same time will increase paging, because the cache can't
hold even one factor base, let alone two, so you will spend a lot of extra time pulling in both
factors bases during sieving (as opposed to one at a time).

Give us some data. How long do you take to process a single special-q? Specify the size of your
factor base and the size of the sieve region. We can then let you know whether your siever
competes with others in terms of performance.

The time it spends should be directly proportional to the size of the sieve array times loglog(pmax)
where pmax is the largest prime in the factor base. The constant will change according to the speed
of your processor, size of cache, size of memory and whether you have one, two, or three LP on each side,
as well as the cleverness of your code.

Last fiddled with by R.D. Silverman on 2015-11-16 at 16:13
R.D. Silverman is offline   Reply With Quote