XPM Sieve Algorithm Study Group

[gudmunsn]

At tacotime's suggestion, I'm working on integrating a version (https://code.google.com/p/primesieve) of a prime-generating table into the code, but I wasn't sure where the big time-waste was in the miner.  Is it in the prime table generation, or is it more in the Weave() method? If I'm understanding it correctly, it looks like the vectors of vfCompositeCunningham1, vfCompositeCunningham2, etc are being filled with true/false values around line 553 of prime.cpp:

Code:

       if (((nBiTwinSeq & 1u) == 0))
            for (unsigned int nVariableMultiplier = nSolvedMultiplier; nVariableMultiplier < nSieveSize; nVariableMultiplier += nPrime)
                vfCompositeCunningham1[nVariableMultiplier] = true;

How can we examine this algorithm and hopefully come up with a more optimized version? Could this not be handled by filling a with a prime table? Or is there necessary computation going on there? 



Disclaimer: I'm not a strong math guy nor am I a strong C++ programmer, but I can at least look at the algorithms.

[mercSuey]

At tacotime's suggestion, I'm working on integrating a version (https://code.google.com/p/primesieve) of a prime-generating table into the code, but I wasn't sure where the big time-waste was in the miner.  Is it in the prime table generation, or is it more in the Weave() method? If I'm understanding it correctly, it looks like the vectors of vfCompositeCunningham1, vfCompositeCunningham2, etc are being filled with true/false values around line 553 of prime.cpp:

Code:

       if (((nBiTwinSeq & 1u) == 0))
            for (unsigned int nVariableMultiplier = nSolvedMultiplier; nVariableMultiplier < nSieveSize; nVariableMultiplier += nPrime)
                vfCompositeCunningham1[nVariableMultiplier] = true;

How can we examine this algorithm and hopefully come up with a more optimized version? Could this not be handled by filling a with a prime table? Or is there necessary computation going on there? 



Disclaimer: I'm not a strong math guy nor am I a strong C++ programmer, but I can at least look at the algorithms.

My first intro to the sieve was in an Abstract Algebra course.  and for large numbers, the sieve can get quite tedious and will definitely take time...but the list of primes can also get quite long and if there's a search of the list for collusion before inserting the prime in the list then this will also take time.  I'm also thinking about this and I've been working to port the code via openCL.