Primes in π

[J F]

No disagreement here. I do not really want or need a --start_string=<huge>.
In the absence of an offset I tried it as (non working) workaround.
So waiting for --lmin it is.

[rogue]

Hopefully I can get around to testing tonight, but I had to make a number of changes to the asm code, which I probably broke because I'm not an x86 asm expert. All I can say is that it compiles right now. My first attempt to test will be to make sure that I didn't break what it does right now. Then I get to test the harder stuff.

[rogue]

Here is the latest, with source. I know this doesn't work because it crashes somewhere in the asm code. I do not know how easy the problem is to fix. Maybe someone with more asm experience than me can point out what I'm doing wrong.

[rogue]

I believe that I have found and fixed the bug. You can find the latest executable and source here. Although only a Windows build is included, it should build and run on Linux and OS X. Unfortunately it crashes on OS X and I don't know why yet, so I'm still investigating.

I have added the -l parameter and I have added a -N parameter to start a new sieve. Previously it used the existence of the index file to determine if a new sieve would be started. An example of the usage would be:

pixsieve -l40000 -L50000 -S20 -P1e9 -spi.txt -iterms.txt -Rterms.pfgw -N

This will search for the string "20" in the decimal representation of the number in pi.txt. It will then sieve all numbers from 40000 to 50000 decimal digits that start with that "20" up to 1e9. The terms.txt file is only used for sieving more deeply after a sieve has completed, although I haven't tested that out. -R is the file that you need to input to pfgw. There is a -f option to output factors that can be validated with pfgw 3.8. You can also run with multiple threads, but I haven't tested that either. This will also output a compressed decimal representation of numbers with a factor.

Why pfgw 3.8? Previous versions of pfgw had a limit of 5000 characters for input strings. This means that it could not verify factors of numbers longer than that. I upped that limit to 5000000 characters.

[rogue]

Originally Posted by rogue

Unfortunately it crashes on OS X and I don't know why yet, so I'm still investigating.

The bug will affect linux too. It is no longer crashing as I found the cause, but the OS X build is missing factors where as the Windows build does not (based upon the testing I have done).

[J F]

Did some quick tests, found some bugs, unfortunately not
only cosmetic ones. pixs1 is old version (v0.1), pixs2 new one (v1.1),
result file were deleted between runs.
-repeated runs with same input produce different results, multi-threaded both
versions, single-threaded v1.1 too, not sure if v0.1 single-threaded too
-sometime there are lines like
p=30523395, 598.5K p/sec, 496 terms left, 61.0% done
p=36397059, 1.573M p/sec, 490 terms left, 72.8% done
Shouldn't p be prime?
-writing intermediate file, v0.1 to _idx (-i), v1.1 to _NoF (-R)
-v1.1 incorrect updates '...terms left', probably same bug as the one above
-v1.1 crashes without -N, if there are no other files to continue from

Sample outputs:

t:\test>pixs1 -sPi1M.txt -S10 -i_idx -R_NoF -f_fac -L20000 -P1e8 -m1e9 -r20
pixsieve version 0.1.0 (testing)
Compiled May 14 2016 with GCC 4.9.2
Starting with 20000 terms
5285 terms remaining after removing terms divisible by 2, 3, and 5
Primes in X sieve initialized: n <= 20000
Sieve started: 3 <= p < 100000000
Thread 0 starting
p=2019331, 100.9K p/sec, 1128 terms left, 2.0% done
p=7032835, 250.5K p/sec, 1043 terms left, 7.0% done
...
Wrote 899 terms to output file `_idx'
p=85895171, 316.4K p/sec, 899 terms left, 85.9% done
p=92274691, 318.7K p/sec, 895 terms left, 92.3% done
p=98678787, 320.0K p/sec, 892 terms left, 98.7% done
Thread 0 completed
Waiting for threads to exit
Wrote 890 terms to output file `_idx'
Sieve complete: 3 <= p < 100000000
Found factors for 19110 terms, 890 remain
count=5761454,sum=0x0000fdf0985fb44a
Elapsed time: 344.53 sec. (0.02 init + 344.51 sieve) at 290272 p/sec.
Processor time: 336.57 sec. (0.02 init + 336.56 sieve) at 297132 p/sec.
Average processor utilization: 1.00 (init), 0.98 (sieve)

t:\test>dir _*
28.05.2016  10:45        43.998.817 _fac
28.05.2016  10:45             5.743 _idx
28.05.2016  10:45         8.889.704 _NoF

t:\test>pixs2 -sPi1M.txt -S10 -i_idx -R_NoF -f_fac -L20000 -P1e8 -m1e9 -r20 -N
pixsieve version 1.1 (testing)
Compiled May 27 2016 with GCC 4.9.2
Starting with 20000 terms
5285 terms remaining after removing ones divisible by 2, 3, and 5
Sieve started: 3 <= p < 100000000
Thread 0 starting
p=1370115, 68.50K p/sec, 949 terms left, 1.4% done
p=5648387, 213.8K p/sec, 943 terms left, 5.6% done
...
Wrote 943 terms to output file `_NoF'
p=67943427, 244.7K p/sec, 943 terms left, 67.9% done
...
p=98286595, 254.8K p/sec, 943 terms left, 98.3% done
Thread 0 completed
Waiting for threads to exit
Wrote 943 terms to output file `_NoF'
Sieve complete: 3 <= p < 100000000
Found factors for 19057 terms, 943 remain
count=5761454,sum=0x0000fdf0985fb44a
Elapsed time: 427.01 sec. (0.01 init + 427.00 sieve) at 234195 p/sec.
Processor time: 378.15 sec. (0.02 init + 378.13 sieve) at 264461 p/sec.
Average processor utilization: 2.23 (init), 0.89 (sieve)

t:\test>dir _*
28.05.2016  10:56        43.249.631 _fac
28.05.2016  11:03             6.095 _idx
28.05.2016  11:03         9.635.005 _NoF

t:\test>pixs2 -sPi1M.txt -S10 -i_idx -R_NoF -f_fac -L20000 -P1e8 -m1e9 -r20 -N -t4
pixsieve version 1.1 (testing)
Compiled May 27 2016 with GCC 4.9.2
Starting with 20000 terms
5285 terms remaining after removing ones divisible by 2, 3, and 5
Sieve started: 3 <= p < 100000000
Thread 3 starting
Thread 2 starting
Thread 1 starting
Thread 0 starting
p=6845443, 342.2K p/sec, 946 terms left, 6.8% done
p=24364035, 875.9K p/sec, 945 terms left, 24.4% done
p=43248643, 944.2K p/sec, 945 terms left, 43.2% done
p=63548419, 1.015M p/sec, 945 terms left, 63.5% done
p=84314115, 1.038M p/sec, 945 terms left, 84.3% done
Thread 3 completed
Thread 0 completed
Waiting for threads to exit
Thread 2 completed
Thread 1 completed
Wrote 945 terms to output file `_NoF'
Sieve complete: 3 <= p < 100000000
Found factors for 19055 terms, 945 remain
count=5761454,sum=0x0000fdf0985fb44a
Elapsed time: 114.96 sec. (0.01 init + 114.95 sieve) at 869931 p/sec.
Processor time: 397.16 sec. (0.02 init + 397.15 sieve) at 251798 p/sec.
Average processor utilization: 1.73 (init), 3.45 (sieve)

t:\test>dir _*
28.05.2016  11:16        43.273.849 _fac
28.05.2016  11:17             6.108 _idx
28.05.2016  11:17         9.611.857 _NoF

t:\test>pixs2 -sPi1M.txt -S10 -i_idx -R_NoF -f_fac -L20000 -P1e8 -m1e9 -r20 -N -t4
pixsieve version 1.1 (testing)
Compiled May 27 2016 with GCC 4.9.2
Starting with 20000 terms
5285 terms remaining after removing ones divisible by 2, 3, and 5
Sieve started: 3 <= p < 100000000
Thread 1 starting
Thread 0 starting
Thread 3 starting
Thread 2 starting
p=5359619, 267.7K p/sec, 943 terms left, 5.4% done
p=22938627, 878.7K p/sec, 943 terms left, 22.9% done
p=41423875, 923.2K p/sec, 943 terms left, 41.4% done
p=60315651, 944.6K p/sec, 943 terms left, 60.3% done
p=79875075, 977.9K p/sec, 943 terms left, 79.9% done
p=99307523, 971.6K p/sec, 943 terms left, 99.3% done
Thread 0 completed
Thread 3 completed
Thread 2 completed
Waiting for threads to exit
Thread 1 completed
Wrote 943 terms to output file `_NoF'
Sieve complete: 3 <= p < 100000000
Found factors for 19057 terms, 943 remain
count=5761454,sum=0x0000fdf0985fb44a
Elapsed time: 120.86 sec. (0.02 init + 120.84 sieve) at 827534 p/sec.
Processor time: 397.05 sec. (0.00 init + 397.05 sieve) at 251857 p/sec.
Average processor utilization: 0.00 (init), 3.29 (sieve)

t:\test>dir _*
28.05.2016  11:46        43.301.860 _fac
28.05.2016  11:48             6.093 _idx
28.05.2016  11:48         9.583.830 _NoF

[rogue]

Very odd. I don't know how it could be testing p that are not prime, but I see that the original version did as well. I am uncertain how it could be missing factors. Maybe the old one was removing terms incorrectly. I'll have to do some runs. I'm also surprised that it is slower. It should be much faster. It was in the runs I did.

[J F]

Originally Posted by rogue

... I'm also surprised that it is slower. It should be much faster. It was in the runs I did.

If it is missing factors, and as it seems not the same factors in repeated
runs, I'm not suprised that speed differs.
Also, I guess changing background load (which I had) would mess with timings
to some degree too. (I admit, I don't know how the runtime measurement
works exactly, whether it's counting only that cpu cycles when the threads are
really doing something, or to what extent it includes things like wait cycles
for data from higher lvl cache/RAM etc.)

[rogue]

In doing some testing I found that the older version also misses factors. For that range you tested, there should only be 627 remaining terms. I remember yesterday fixing a bug with the original code that caused that, but the prime sieve issues might be just as big. Is it possible that some primes aren't being tested at all? Probably not, but I wonder how many numbers are being tested as divisors that aren't truly prime.

When I have some time I'm going to replace the prime number sieve with one that I know works. The one in this program originated years ago and was used by the original fpsieve.

That leaves a bug in the new code that was intended to speed up testing of ranges when using the new -l option. That code is likely responsible for the issues on the OS X build. When testing on Windows I ran into a very weird bug with gcc that I was able to work around, but maybe it doesn't work in all cases. Fortunately I have enough good data that I should be able to squash that bug when I have some time.

[rogue]

This is odd. I was reviewing the asm code and found that it was making some unnecessary comparisons. On the plus side, removing that code improved the performance of the application. In fact, it seems to be finding all of the factors on OS X right now, although I still have more testing to do. On the minus side, that same code does not behave in the same way on Windows and I don't know why, so it misses factors. Also on the minus side the OS X code crashes when it finishes the run, although I think that I figured that one out.

[Batalov]

Incidentally, an interesting entry was added to PRPtop last month.
PIPrime(613373) (613373 digits, ...obviously) -- Adrian Bondrescu 05/2016