The Twin Prime Search remains suspended due to lack of sieving. With NewPGen, the removal rate is about 3 candidates to 1 LLR test. This warrants more sieving.

However, we have decided to test a new twin prime sieve software developed by Geoff Reynolds. It may be faster than NewPGen. If so, we'll start a sieving reservation thread and hopefully attract users who wish to see the search continued.

But first, we must test. We need to make the following timing comparisons:

1. 32 bit NewPGen vs. 32 bit tpsieve (windows)
2. 32 bit NewPGen vs. 32 bit tpsieve (linux)
3. 32 bit NewPGen vs. 64 bit tpsieve (windows)
4. 32 bit NewPGen vs. 64 bit tpsieve (linux)
5. 32 bit tpsieve 1 instance vs. 32 bit tpsieve 2 instances (-t2)
6. 64 bit tpsieve 1 instance vs. 64 bit tpsieve 2 instances (-t2)

We already know that -t4 is slower than running 2 -t2's so no need to test that. We also know that tpsieve needs a lot of RAM so at least 1GB is recommended.

We need the following test results:

OS, CPU, RAM, time NewPGen ??bit, time tpsieve ??bit

The Software and Sieve file

NewPGen can be downloaded here (only 32 bit available):
- Windows
- Linux - dynamic
- Linux - static

tpsieve can be downloaded here (32 & 64 bit available):
- tpsieve-0.2.1-bin (Windows and Linux)

The test sieve file can be downloaded here:
- tps-8500T-test

Using the software

Our test range will be 100G. The sieve file is already set up for p=8500T. Therefore, our end depth P will be 8500100000000000 (8,500,100,000,000,000 or 85001e11). This should take 20-30 minutes to test.

NOTE: NewPGen removes the factors from the sieve file. Therefore, please make a copy from the original sieve file so that you can start your next test with an original file. OR, you could do the tpsieve test first then do the NewPGen test since tpsieve does not alter the sieve file.

We are comparing two things, testing time and factors. We want to know which program was faster and if the factors found match up in both tests.

To run tpsieve (command line):

single instance: tpsieve -i tps-8500T-test.out -p 85000e11 -P 85001e11
two instances: tpsieve -i tps-8500T-test.out -p 85000e11 -P 85001e11 -t2
(linux use ./tpsieve)

Factors will be written to tpfactors.txt

To run NewPGen (Windows):

Start at #4 on this instructional page. At step #7, paste the following end depth: 8500100000000000

You can stop at #10. Factors will be written to NewPGen.del.

To run NewPGen (Linux):

NewPGen 2.82 - Use Control-C to manually stop the current sieving.

What do you want to do now ?
0 : To create a new file.
1 : To continue sieving an old file.
2 : To change one or several option(s).
3 : To get a service.
4 : To get some help.
5 : To exit from this program.
Please, enter your choice (0) : 2

What option do you want to change ?
0 : Worker thread priority
1 : Automatically continue sieving the last file on startup
2 : Sieve until...
3 : Set max Mb RAM to store values...
4 : Minutes between automatic saves...
5 : Log the numbers removed
6 : Use two save files
Please, enter your choice (0) : 2

Sieve until :
0 : Sieve until manually stopped
1 : Sieve up to p = (1000)
2 : Sieve until there are (1000) k's or n's remaining
3 : Sieve for (24) hours
4 : Sieve until the rate is (0.1) seconds per k or n
Please, enter your choice (0) : 1

Sieve up to p = (1000) 8500100000000000

Automatically increment n or k when complete ? (n) : n

Pass the file to PFGW for PRP testing when complete ? (n) : n

Would you change any more option ? (n) : n

What do you want to do now ?
0 : To create a new file.
1 : To continue sieving an old file.
2 : To change one or several option(s).
3 : To get a service.
4 : To get some help.
5 : To exit from this program.
Please, enter your choice (0) : 1
Verify results ? (n) : n
Sieving an old file ; Input file name = tps-8500T-test.out
Output file name = tps-8500T-testa.out
Opened the input file - counting the number of k's and finding the range of k...
The file contains 12789270 k's - using array: allocating 97.6Mb of RAM...
...succeeded
base = 2, n = 333333, kmin =60000003135, kmax = 99999999879
Type : Twin: k.b^n±1
Use normal mode
There is a stop criterion for this sieve:

Sieve up to p = 8500100000000000.

Do you want to continue? (y) : y
Are you ready to start sieving ? (y) : y

NOTE: Both tpsieve and newpgen take some time initializing the sieve...which means there's a delay before actual sieving starts.

Please report back your observations. Remember, we're looking for the following information:

OS, CPU, RAM, time NewPGen ??bit, time tpsieve ??bit and whether or not the factor files matched.

We very much appreciate your help. Hopefully, this new sieve software will show promise and then we can move forward with the Twin Prime Search.
____________

As seen below, 64 bit Linux is by far the fastest. Also, in general, it looks like Linux has an advantage over Windows.

NewPGen - Windows XP 32 bit, Athlon64 @2.2GHz, 2G RAM
took ~40 secs to initialize
28:25 (1705 sec)
29:05 total
14 Factors

used ~402MB RAM

tpsieve - Windows XP 32 bit, Athlon64 @2.2GHz, 2G RAM
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 2055.77 sec. (346.86 init + 1708.91 sieve) at 58517003 p/sec.
Processor time: 1716.41 sec. (53.23 init + 1663.17 sieve) at 60126120 p/sec.
Average processor utilization: 0.15 (init), 0.97 (sieve)

used ~600MB RAM

tpsieve - Ubuntu 32 bit, Athlon64 @2.2GHz, 2G RAM
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 1516.47 sec. (39.89 init + 1476.58 sieve) at 67724284 p/sec.
Processor time: 1385.13 sec. (20.65 init + 1364.47 sieve) at 73288406 p/sec.
Average processor utilization: 0.52 (init), 0.92 (sieve)

used ~800MB RAM

tpsieve - Ubuntu 64 bit, Athlon64 @2.2GHz, 2G RAM
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 1000.83 sec. (25.88 init + 974.95 sieve) at 102569310 p/sec.
Processor time: 983.37 sec. (16.20 init + 967.17 sieve) at 103394252 p/sec.
Average processor utilization: 0.63 (init), 0.99 (sieve)

used ~800MB RAM
____________

When/Where/How? :-)

____________

NewPGen - Windows XP 64 bit, C2Q9450 @3.2GHz, 6G RAM
took ~20 secs to initialize
8:29 (509 sec)
8:49 total
14 Factors

used 110MB RAM

tpsieve - Windows XP 64 bit, C2Q9450 @3.2GHz, 6G RAM
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 531.66 sec. (15.58 init + 516.08 sieve) at 193769251 p/sec.
Processor time: 527.75 sec. (15.47 init + 512.28 sieve) at 195205410 p/sec.
Average processor utilization: 0.99 (init), 0.99 (sieve)

used 824MB RAM

tpsieve - Windows XP 64 bit, C2Q9450 @3.2GHz, 6G RAM, -t2 switch
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 279.05 sec. (15.53 init + 263.52 sieve) at 379484411 p/sec.
Processor time: 532.38 sec. (15.64 init + 516.73 sieve) at 193523165 p/sec.
Average processor utilization: 1.01 (init), 1.96 (sieve)

used 824MB RAM

Second test run on the quad, using blocksize=1024 instead of 512:

tpsieve - Windows XP 64 bit, C2Q9450 @3.2GHz, 6G RAM
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 523.02 sec. (16.14 init + 506.88 sieve) at 197287441 p/sec.
Processor time: 518.09 sec. (15.84 init + 502.25 sieve) at 199104175 p/sec.
Average processor utilization: 0.98 (init), 0.99 (sieve)

used 825MB RAM

tpsieve - Windows XP 64 bit, C2Q9450 @3.2GHz, 6G RAM, -t2 switch
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 262.83 sec. (15.52 init + 247.31 sieve) at 404347017 p/sec.
Processor time: 509.05 sec. (15.44 init + 493.61 sieve) at 202589490 p/sec.
Average processor utilization: 0.99 (init), 2.00 (sieve)

used 825MB RAM

Now it's at least faster than NewPGen, but the difference is not that big...

All tests done on a Q9300@2.5MHz 4GB RAM.

NewPGen Windows XP 32 bit
took ~20 secs to initialize
10:58 (658 sec)
11:18 total
14 Factors

used ~107MB RAM


tpsieve Windows XP 32 bit
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 1167.00 sec. (24.67 init + 1142.33 sieve) at 87540584 p/sec.
Processor time: 1166.30 sec. (24.59 init + 1141.79 sieve) at 87588507 p/sec.
Average processor utilization: 1.00 (init), 1.00 (sieve)

used 821MB RAM


tpsieve Windows XP 32 bit -t2 switch
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 598.28 sec. (24.55 init + 573.73 sieve) at 174296811 p/sec.
Processor time: 1171.05 sec. (24.52 init + 1146.53 sieve) at 87219665 p/sec.
Average processor utilization: 1.00 (init), 2.00 (sieve)

used 821MB RAM


More to come...
____________
There are only 10 kinds of people - those who understand binary and those who don't

to be able to compare a litle more, an llr test takes 3:15 min on this computer

NewPGen - ubuntu 9.04 64 bit, C2Q8300 @2.5GHz, 4G RAM
took ~20 secs to initialize
11:20
11:40 total
14 Factors

used 98MB RAM
note: no logfile with the found factors generated, only a new sieve file. I don't know if that is an option but else it will be hard to report completed tests.

tpsieve (1 core) - ubuntu 9.04 64 bit, C2Q8300 @2.5GHz, 4G RAM
I don't know exactly how much time, but is was more then 45 minutes.

used 835MB RAM
____________

Can't edit any more. Same machine, rebooted to XUbuntu 64 bit:

NewPGen XUbuntu 64 bit
took ~20 secs to initialize
11:32 (692 sec)
11:52 total
14 Factors

used ~98MB RAM


tpsieve XUbuntu 64 bit
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 637.79 sec. (14.12 init + 623.68 sieve) at 160339903 p/sec.
Processor time: 637.16 sec. (14.09 init + 623.07 sieve) at 160495484 p/sec.
Average processor utilization: 1.00 (init), 1.00 (sieve)

used ~801MB RAM

tpsieve XUbuntu 64 bit -t2switch
Thread 0 completed
Thread 1 completed
Waiting for threads to exit
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=2726367741,sum=0x44423850de0e0bf1
Elapsed time: 2755.43 sec. (14.26 init + 2741.16 sieve) at 36480871 p/sec.
Processor time: 3062.32 sec. (14.26 init + 3048.05 sieve) at 32807855 p/sec.
Average processor utilization: 1.00 (init), 1.11 (sieve)

System monitor showed one process with 834MB RAM. Two CPUs were at about 60% each. Something didn't work here.
____________
There are only 10 kinds of people - those who understand binary and those who don't

C2D mobile T7500 2.2GHz 2GB RAM



All factor files matched.

NPGen RAM ~98MB Ubuntu, ~107MB Win
tpsieve RAM ~801MB Ubuntu, ~822MB Win

C2Q6600 2,4Ghz WinXP 64 4Gb RAM

NewPgen 740 sec

tpsieve64 1 core 703 sec

tpsieve64 2 core 363 sec

tpsieve32 1core 939 sec

Lennart

tpsieve - Windows XP 64 bit, Core2Duo E6600@2.40GHz, 1G RAM
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 816.31 sec. (108.94 init + 707.38 sieve) at 141367834 p/sec.
Processor time: 706.09 sec. (26.81 init + 679.28 sieve) at 147214533 p/sec.
Average processor utilization: 0.25 (init), 0.96 (sieve)


tpsieve - Windows XP 64 bit, Core2Duo E6600@2.40GHz, 1G RAM -t2 switch
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 433.55 sec. (73.42 init + 360.13 sieve) at 277681560 p/sec.
Processor time: 730.88 sec. (24.22 init + 706.66 sieve) at 141511621 p/sec.
Average processor utilization: 0.33 (init), 1.96 (sieve)


NewPGen - Windows XP 64 bit, Core2Duo E6600@2.40GHz, 1G RAM
took ~25s to initialize
12:23 (743 sec)
12:48 total
14 factors






tpsieve - Windows XP 32 bit, Core2Duo E6600@2.40GHz, 1G RAM
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 1400.81 sec. (213.80 init + 1187.02 sieve) at 84244950 p/sec.
Processor time: 1213.08 sec. (31.23 init + 1181.84 sieve) at 84613615 p/sec.
Average processor utilization: 0.15 (init), 1.00 (sieve)


tpsieve - Windows XP 32 bit, Core2Duo E6600@2.40GHz, 1G RAM -t2 switch
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 627.47 sec. (29.36 init + 598.11 sieve) at 167193620 p/sec.
Processor time: 1219.83 sec. (25.28 init + 1194.55 sieve) at 83713811 p/sec.
Average processor utilization: 0.86 (init), 2.00 (sieve)


NewPGen - Windows XP 32 bit, Core2Duo E6600@2.40GHz, 1G RAM
took ~28 to initialize
12:36 (756 sec)
13:04
14 factors


More info to come... :)
____________

tpsieve - Windows Vista 32 bit, Core2Duo T9550@2.66GHz, 4G RAM
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 1082.89 sec. (22.15 init + 1060.74 sieve) at 94274090 p/sec.
Processor time: 1074.50 sec. (22.12 init + 1052.38 sieve) at 95022531 p/sec.
Average processor utilization: 1.00 (init), 0.99 (sieve)


tpsieve - Windows Vista 32 bit, Core2Duo T9550@2.66GHz, 4G RAM -t2 switch
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 585.50 sec. (22.24 init + 563.25 sieve) at 177539923 p/sec.
Processor time: 1090.12 sec. (21.50 init + 1068.62 sieve) at 93578487 p/sec.
Average processor utilization: 0.97 (init), 1.90 (sieve)



NewPGen - Windows Vista 32 bit, Core2Duo T9550@2.66GHz, 4G RAM
~25 seconds to initialize
10:26 (626 sec)
10:51 total
14 factors







tpsieve - Ubuntu 64 bit, Core2Duo T9550@2.66GHz, 4G RAM
used 800M memory
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 1843.77 sec. (31.82 init + 1811.95 sieve) at 55189232 p/sec.
Processor time: 1829.07 sec. (31.80 init + 1797.27 sieve) at 55640035 p/sec.
Average processor utilization: 1.00 (init), 0.99 (sieve)



tpsieve - Ubuntu 64 bit, Core2Duo T9550@2.66GHz, 4G RAM -t2 switch
used 800M memory
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 1125.79 sec. (35.83 init + 1089.96 sieve) at 91746463 p/sec.
Processor time: 1690.41 sec. (33.37 init + 1657.04 sieve) at 60348778 p/sec.
Average processor utilization: 0.93 (init), 1.52 (sieve)


I think something's wrong with the linux builds, 64 bits at least...

I didn't test linux version of nwepgen yet.



____________

I can see two problems occuring:

1. The usual Ubuntu Linux problem of CPU frequency scaling. Fix this by adding --priority=normal to the command line, or changing the priority= line in the tpconfig.txt file.

2. The configuration file tpconfig.txt contains a default setting of qmax=10e6. If you run the executable without a copy of the config file in the current working directory then this option will not be active and sieving will be much slower. Add --qmax=10e6 to the command line to be sure it is active.

If the CPU frequency reported on the status line is not close to the expected frequency for your machine then problem 1 could be the cause.

If the final report doesn't match count=3390028539, sum=0x9e7c61deb716ec9f, then problem 2 is likely the cause.

Note that the qmax parameter controlls the proportion of time spend sieving vs testing. Higher qmax values will spend more time sieving and less time testing. The optimal value depends on the speed of the sieve code (cache/memory access speed) vs the testing code (modular multiplication speed).

Also note that there are no SSE2 optimisations in tpsieve yet. Once added, SSE2 will speed up the testing step on 32-bit machines, and also the sieving step on both 32-bit and 64-bit machines.

Thanks for the tips, I'm going to try again today.
____________

The issue was on priority set to idle in tpconfig. qmax already set to 10e6.

Setting priority to normal:

tpsieve - Ubuntu 64 bit, Core2Duo T9550@2.66GHz, 4G RAM
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 563.06 sec. (11.35 init + 551.71 sieve) at 181255949 p/sec.
Processor time: 562.80 sec. (11.28 init + 551.52 sieve) at 181316406 p/sec.
Average processor utilization: 0.99 (init), 1.00 (sieve)



tpsieve - Ubuntu 64 bit, Core2Duo T9550@2.66GHz, 4G RAM -t2 switch
Sieve complete: 8500000000000000 <= p < 8500100000000000
Found 14 factors
count=3390028539,sum=0x9e7c61deb716ec9f
Elapsed time: 298.20 sec. (10.41 init + 287.79 sieve) at 347473994 p/sec.
Processor time: 583.88 sec. (10.41 init + 573.47 sieve) at 174377820 p/sec.
Average processor utilization: 1.00 (init), 1.99 (sieve)


I think it looks better now :-)
Thanks Geoff
____________

Will we start a sieve?
____________

Will we start a sieve?

I still experience problems with the -t switch under Linux 64bit. I get messages that child processes are started, but processor use is only ~150% where it should be 400% or close to that.

Starting seperate tasks on one machine helps, but it's a nuisance.

BTW: What's the best value for Qmax? 10e6 helps a lot, but is it optimal?

Thanks, Peter
____________
There are only 10 kinds of people - those who understand binary and those who don't

I still experience problems with the -t switch under Linux 64bit. I get messages that child processes are started, but processor use is only ~150% where it should be 400% or close to that.

Starting seperate tasks on one machine helps, but it's a nuisance.

BTW: What's the best value for Qmax? 10e6 helps a lot, but is it optimal?

Thanks, Peter

I've got this result on my Ubuntu 64bit box

Try 2 times -t2, this should result in barely any loose of cpu-power

Note that the qmax parameter controlls the proportion of time spend sieving vs testing. Higher qmax values will spend more time sieving and less time testing. The optimal value depends on the speed of the sieve code (cache/memory access speed) vs the testing code (modular multiplication speed).

Isn't is about time to get a new sieve-file?
..And to restart llr?
____________

Note that the qmax parameter controlls the proportion of time spend sieving vs testing. Higher qmax values will spend more time sieving and less time testing. The optimal value depends on the speed of the sieve code (cache/memory access speed) vs the testing code (modular multiplication speed).

Does this parameter change the number of factors we're finding or is it strictly a speed thing? I'm wondering if playing around with it might improve sieving speed but I don't want it to affect sieving quality.

Thanks, geoff!

Another question: Every now and then I get an "Invalid checkpoint" when restarting a sieve. Is there anything I can do about this? Apart from looking at the factor file and editing the command line accordingly I mean.

Peter
____________
There are only 10 kinds of people - those who understand binary and those who don't

Another question: Every now and then I get an "Invalid checkpoint" when restarting a sieve. Is there anything I can do about this? Apart from looking at the factor file and editing the command line accordingly I mean.

Hi, all,

I've made a new 64-bit version of tpsieve, posted here, that uses the hybrid Montgomery/floating point method I've been working on here. I couldn't download the original test file at the top of this thread, but I made my own small test file for N=333335, and on that the 64-bit version is up to 20% faster!

Obviously it needs more testing, and I only included Linux binaries, but I hope it's helpful. The benefits will decrease as N increases, but hopefully it's always faster. Also, I think the algorithm may be able to slightly improve sr2sieve, but I don't have the code for that, so I'm not sure.

I have incorporated Ken's conditional move idea in tpsieve 0.2.3, and with the few trials I have done on my Core 2 Duo the 64-bit code seems to be about 15% faster. But the TPS file is too big for me to download for real testing.

I didn't include the Mongomery multiplication code, as this didn't seem to make it any faster. But perhaps that is just on my machine, or a difference in compiler versions. More testing is needed I think.

Geoff, you were right about several things. First, I was surprised to find that the Montgomery code I had used didn't improve speed any. I didn't expect the cmov to make that much difference, so I didn't test it alone.

Second, you were right about inlining functions in C being a problem. That's why the first code I posted didn't get any speedup from the Montgomery math. The original Montgomery setup function I wrote for C++ didn't work in C, so I'd done something else; but when I wrote the original inline, I got about another 8% speed boost!

The new code is now posted at the same link.