A multiple k/c sieve for Sierpinski/Riesel problems

[Joe O]

Originally Posted by Rogue

TextPad is even better...

Originally Posted by Greenbank

With cygwin comes vi, but then I don't want to start a holy editor war. :-)

You are both right. But consider the context. A Windows user working with Cygwin for the first time. Doesn't specify the name of the "text editor" so possibly Notepad. Probably very familiar with Notepad, possibly familiar with WordPad. Wordpad already installed as part of the Default installation of Windows. Easiest thing for them to try is WordPad. This question would not even have come up if they were Unix aware, and or had other text editor experience. So, simplest recommendation try WordPad. It's there, it's a familiar interface, costs nothing to try, no learning curve. Baby Steps first then Giant Steps <G>.

[geoff]

Originally Posted by Greenbank

Seems that the gcc I have (3.4.4) really didn't like the '_mulmod62' and '_one_over_p' references. I had to remove the leading underscore before they would compile properly.

Thanks I will change this, but it will be a few days before I can post updated source. Version 0.0.12 still has the underscores.

I think the only features that might prevent it compiling in Windows without Cygwin are the alarm signals and getrusage() call.

[rogue]

64-bit CPUs give warnings on %ju. Why don't you try this:

#ifdef __ppc64__
#define PRINTF_LLU "%llu"
#else
#define PRINTF_LLU "%ju"
#endif

Then use:

printf("blah="PRINTF_LLU"\n", blah);

instead of

printf("blah=%ju\n", blah);


If there is an easier way to detect 32-bit vs 64-bit which does not depend upon checking the architecture, then use it.

[geoff]

Originally Posted by rogue

64-bit CPUs give warnings on %ju. Why don't you try this:

#ifdef __ppc64__
#define PRINTF_LLU "%llu"
#else
#define PRINTF_LLU "%ju"
#endif

"%llu" works fine for 32 bit CPUs, I thought it would not work for 64 bit ones which is why I used "%ju" :-) I will change it back next time.

Meanwhile 0.0.13 should fix the underscore problem on Windows compiles, and provides an alternative to getrusage() if it is not available.

[rogue]

Originally Posted by geoff

"%llu" works fine for 32 bit CPUs, I thought it would not work for 64 bit ones which is why I used "%ju" :-) I will change it back next time.

Meanwhile 0.0.13 should fix the underscore problem on Windows compiles, and provides an alternative to getrusage() if it is not available.

On 64-bit CPUs, %llu is used for uint64_t and %lu is used for uint32_t.

geoff, I've been working on some changes so that the current release can be built on PPC, but I've run into a small problem that I need to work out. I use magic numbers for the mulmod and powmod, but they are only calculated in the in sieve32 and sieve64. There is a call to powmod32 in is_pprime that cannot use the powmod that I've written. I have bypassed it by using my own sieve. I could send it on to you if you're interested. I use the same sieving technique in MultiSieve. It uses a callback which passes the next prime so it is structured a little differently than your sieve.

[axn]

%ju is not recognised by gcc (under Cygwin) Going to find & replace everything to %llu

[geoff]

I have inlined mulmod62() for a small speedup in the 64 bit sieve, and there is a 'check' target for make that tests the srsieve binary.

Originally Posted by rogue

On 64-bit CPUs, %llu is used for uint64_t and %lu is used for uint32_t.

I see there are some macros PRIu32, PRIu64 etc. defined in <inttypes.h> that can be used to deal with this problem, they make the printf() format strings a bit hard to read but they are probably the most portable solution.

geoff, I've been working on some changes so that the current release can be built on PPC, but I've run into a small problem that I need to work out. I use magic numbers for the mulmod and powmod, but they are only calculated in the in sieve32 and sieve64. There is a call to powmod32 in is_pprime that cannot use the powmod that I've written. I have bypassed it by using my own sieve. I could send it on to you if you're interested. I use the same sieving technique in MultiSieve. It uses a callback which passes the next prime so it is structured a little differently than your sieve.

Yes I would be interested to see it. It shouldn't be a problem to have different mulmod/powmod functions for each sieve.

[geoff]

I have included rogue's prime sieve code, add -DUSE_PRIME_SIEVE to the CFLAGS in the Makefile to use this instead of the existing probable prime functions.

I have lifted the restriction on c in k*b^n+c so it can be any number relatively prime to k and b. I am not 100% sure whether it is correct to allow this, but it seems to work OK.

Since the NewPGen file format only allows c=+1,-1 and PRP only reads NewPGen files (I think?), I have added a --pfgw switch which writes the sieve file in a format suitable for input to pfgw.

[geoff]

This version fixes a problem with the assembler version of mulmod64 that has been present since it was inlined in version 0.0.15. It probably didn't affect any released version of srsieve, but potentially factors could have been missed in the 64 bit sieve. If anyone wants to be sure whether or not the version they have been using is affected by the bug then they can send me a copy of the bsgs.o object file and I will check it. (It depends on compiler version and optimisation flags used).

On a more positive note, a much improved hashtable should speed up large sieves (e.g. the size of the current base 5 project) by about 60%, and small sieves by 5-10%.

[axn]

Originally Posted by geoff

On a more positive note, a much improved hashtable should speed up large sieves (e.g. the size of the current base 5 project) by about 60%, and small sieves by 5-10%.

When you said 60% speedup I had imagined 60% improvement in throughtput - I didn't realise that it was 60% _reduction_ in time !!

Right now I am getting a better than 2x thruput. This calls for a

[geoff]

Originally Posted by axn1

When you said 60% speedup I had imagined 60% improvement in throughtput - I didn't realise that it was 60% _reduction_ in time !!

I did mean a 60% throughput improvement, but I only tested on my P4. The improvement is mainly due to the hashtable being smaller and staying in cache longer, so the actual improvement will depend a lot on cache size.