View Single Post
Old 2007-12-18, 02:37   #8
geoff's Avatar
Mar 2003
New Zealand

13×89 Posts

Originally Posted by monst View Post
I'm using a version of MultiSieve that has a "SieveUntil" feature implemented through the ini file. I set this just high enough to sieve past the Max k (max n in gcwsieve) [/SIZE]
Be aware that gcwsieve doesn't actually reduce the size of the sieve as factors are found, it just marks the candiate so that duplicate factors are not reported, so to get best performance you will need to stop and restart it every now and then. This is because gcwsieve was designed for the deep end of the sieve where factor density is very low.

I am past the interim file manipulation request. I have better control with the method I'm using so I'm all set here. (Actually I had started writing a parser as you suggested when I decided on this other method.)[/SIZE]
This awk command will split a MultiSieve variable-base ABC file `in.txt' into seperate fixed-base files `<base>.txt' suitable for input to gcwsieve:
awk '/ABC/{H=$0;next}!F[$2]{F[$2]=$2".txt";print H>F[$2]}{print>>F[$2]}' in.txt
I have a working prototype of a program that will start sieving a single base from scratch. It had three phases:

1. Remove terms with algebraic factors and those divisible by two.

2. Remove terms with factors p in 2 < p <= sqrt(n_max). This takes up to p(p-1) modular multiplications for each p.

3. Remove terms with factors p in sqrt(n_max) < p <= n_max. This takes two modular multiplications per remaining term for each p.

(The algorithm gcwsieve uses takes one modular multiplication per remaining term for each p > n_max).

Last fiddled with by geoff on 2007-12-18 at 02:48 Reason: phase 2
geoff is offline   Reply With Quote