mtsieve

[rogue]

I have committed a number of code changes to sourceforge to address the reported issues. The changes are not fully tested, but I think the reported issues are fixed. I haven't updated the distribution yet. I will do that as soon as I can.

[rogue]

I tracked down the memory leak in srsieve2. It was caused by an overloaded operator that was using a copy constructor.

[Citrix]

I am interested in low weight numbers of the form k*b^n+-1 with fixed k and b and variable n. (srsieve2.exe)

Is it possible to add support for large bases where b'=b^x and large k values where k'=k*b^y

where b is small <100
and b' is greater than 2^64

Currently the program does not automatically convert k*b^n+-1 to k'*b'^n+-1 to increase speed.

Thanks.

[rogue]

Originally Posted by Citrix

I am interested in low weight numbers of the form k*b^n+-1 with fixed k and b and variable n. (srsieve2.exe)

Is it possible to add support for large bases where b'=b^x and large k values where k'=k*b^y

where b is small <100
and b' is greater than 2^64

Currently the program does not automatically convert k*b^n+-1 to k'*b'^n+-1 to increase speed.

Thanks.

If I understand correctly, you want k*b^y*(b^x)^n+-1. Since this is k*b^(y+x*n)+-1, as long as k < 2^63, you can start with srsieve2, but then use a scripting language to eliminate all candidates that you don't fit. Could also also generate your input candidate file then start sieving from p=3.

Am I missing something?

[Citrix]

Originally Posted by rogue

If I understand correctly, you want k*b^y*(b^x)^n+-1.

Am I missing something?

Yes this is correct.

For a range of n=1 to 1000000 the discrete log would have 1000 BS and 1000 GS
If we know x =16
Then the range becomes n=1 to 62500 (for base b^16) and the discrete log would have 250 BS and 250 GS
4 times faster.

For extremely low weights (that I am working with) where x can be close to 10000 the program can be made significantly faster. (~100 times)

Currently the program does not automatically detect the pattern and calculate the value of x.

(To calculate x you just need the gcd of the difference of all the consecutive candidates left in the sieve. You can do this just once at the start of the sieve).

Thanks.

[henryzz]

Originally Posted by Citrix

Yes this is correct.

For a range of n=1 to 1000000 the discrete log would have 1000 BS and 1000 GS
If we know x =16
Then the range becomes n=1 to 62500 (for base b^16) and the discrete log would have 250 BS and 250 GS
4 times faster.

For extremely low weights (that I am working with) where x can be close to 10000 the program can be made significantly faster. (~100 times)

Currently the program does not automatically detect the pattern and calculate the value of x.

(To calculate x you just need the gcd of the difference of all the consecutive candidates left in the sieve. You can do this just once at the start of the sieve).

Thanks.

The old srxsieve programs will cope with that as they will sieve sub-sequences when only a few remain. This results in a huge speedup for low weight sequences. This is a feature than mtsieve should have if it doesn't already(I haven't used the srsieve2 yet so I don't know)

[Citrix]

Originally Posted by henryzz

The old srxsieve programs will cope with that as they will sieve sub-sequences when only a few remain. This results in a huge speedup for low weight sequences. This is a feature than mtsieve should have if it doesn't already(I haven't used the srsieve2 yet so I don't know)

Srxsieve also misses this at times. As it only looks at x=factors of 720.

[pepi37]

As you know I do many jobs with your twinsieve. Since I buy new 6 core CPU I noticed something I was not sow on 4 core CPU.
If I run sieve from start somewhere up to 2e15 I can get nearly 96% of CPU usage on 6 core CPU . But if I run it from 2e16 to 4e16 then I cannot get more then 45% of CPU usage. I can increase "W" option and can get around 62% of CPU usage but that is all I can get.
I assume on higher sieve depth CPU do less job since there is smaller number of primes to test, but how to get at least 90% of CPU usage on those, higher sieve depth? I try to increase worker number from 6 to 8 but that doesnot help.
Any other suggestion?

[rogue]

Originally Posted by pepi37

As you know I do many jobs with your twinsieve. Since I buy new 6 core CPU I noticed something I was not sow on 4 core CPU.
If I run sieve from start somewhere up to 2e15 I can get nearly 96% of CPU usage on 6 core CPU . But if I run it from 2e16 to 4e16 then I cannot get more then 45% of CPU usage. I can increase "W" option and can get around 62% of CPU usage but that is all I can get.
I assume on higher sieve depth CPU do less job since there is smaller number of primes to test, but how to get at least 90% of CPU usage on those, higher sieve depth? I try to increase worker number from 6 to 8 but that doesnot help.
Any other suggestion?

I'm guessing the bottleneck is where it gets the next block of primes for testing as only one thread can get a block of primes at a time. I don't have any great ideas as to how to address that right now.

One option would be to run two instances across two different ranges of primes, saving the factors (-O) then using -I to remove terms from the original input file.

[rebirther]

@rogue: Is there any progress for the srsieve2 prp output format. I could really need it.

[rogue]

Originally Posted by rebirther

@rogue: Is there any progress for the srsieve2 prp output format. I could really need it.

(going off of memory here) I think this is the -fB option. Can you verify that it exists in the latest released version and if it does, if that is what you are looking for?