Contributions to msieve source code

[bsquared]

Originally Posted by mickfrancis

I appreciate that people are more concerned with GNFS than SIQS, but I just thought I'd mention that I've got a speedup of around 6% (for C80, C90 and C100) by making the following change in sieve.c (conditional on __MDF__):

	/* choose the largest factor base prime that does not
	   use hashtables or reciprocals. We could make this
	   range empty, but it's better to start using hashtables
	   with primes somewhat larger than the block size.
	   This greatly reduces the amount of memory used by
	   the hashtables, and trial factoring by primes in this
	   range is extremely cheap */

	for (; i < fb_size && conf.factor_base[i].prime <
#if defined(__MDF__)
            sieve_block_size; i++) {
#else
            3 * sieve_block_size; i++) {
#endif
		/* nothing */
	}

I also tried using sieve_block_size/2, but that degrades performance. This is on an Intel i7-3770. Testing was after removing the PREFETCH in add_to_hashtable() in sieve_core.c, which may be important as that function will be more heavily loaded by this change if I'm not mistaken.

Cheers,

Mick.

I tried it out and it ran in exactly the same time on a C80 with this change. I'd expect this improvement to vary a lot more depending on the cpu/system, so this could be an isolated case. I'll try again with a larger number.

By the way, since it seems you are pretty gung-ho about siqs, feel free to look for optimizations in yafu as well .

It is between 1.5-2.5x faster than msieve now, so they may be harder to find, but the more eyes the merrier!

cheers,
- ben.

[mickfrancis]

Thanks Ben - it would be interesting to see if anyone else finds an improvement - it is 100% repeatable for me.

I do have a buildable yafu in NetBeans, but haven't had much of a look at that yet - it does seem fast, and it's great that it can multi-thread. I'm only a few weeks into learning about SIQS, so I'm using the goal of optimisation as a vehicle on the journey towards greater understanding of the theory and implementation techniques. Once I've got there, I'll start on the NFS, but there's a bit of an abstract algebra learning curve for me to climb first!

Cheers,

Mick.