mtsieve enhancements - Page 13

ryanp · 2022-06-13, 20:57

Compilation fixed after the latest "svn up", but I'm now seeing this weirdness:

Code:

$ ./srsieve2 -W 48 -o ferm7_20M_30M_sv1e14.txt -P 1e14  -n 20e6 -N 30e6 -s "7*2^n+1"
srsieve2 v1.6.2, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Sieving with generic logic for p >= 3
Sieve started: 3 < p < 1e14 with 10000001 terms (20000000 < n < 30000000, k*2^n+1) (expecting 9659200 factors)
  p=3, 0.331 p/sec, 5000000 factors found at 54.83K f/sec (last 1 min), 0.0% done
  p=3, 0.362 p/sec, 5000000 factors found at 27.53K f/sec (last 2 min), 0.0% done
  p=3, 0.351 p/sec, 5000000 factors found at 18.36K f/sec (last 3 min), 0.0% done.

Doesn't seem to be making any progress.

rogue · 2022-06-13, 21:35

Quote:

Originally Posted by ryanp

Compilation fixed after the latest "svn up", but I'm now seeing this weirdness:

Code:

$ ./srsieve2 -W 48 -o ferm7_20M_30M_sv1e14.txt -P 1e14  -n 20e6 -N 30e6 -s "7*2^n+1"
srsieve2 v1.6.2, a program to find factors of k*b^n+c numbers for fixed b and variable k and n
Sieving with generic logic for p >= 3
Sieve started: 3 < p < 1e14 with 10000001 terms (20000000 < n < 30000000, k*2^n+1) (expecting 9659200 factors)
  p=3, 0.331 p/sec, 5000000 factors found at 54.83K f/sec (last 1 min), 0.0% done
  p=3, 0.362 p/sec, 5000000 factors found at 27.53K f/sec (last 2 min), 0.0% done
  p=3, 0.351 p/sec, 5000000 factors found at 18.36K f/sec (last 3 min), 0.0% done.

Doesn't seem to be making any progress.

That is because the updated code wasn't incrementing an index variable. I committed a change.

rogue · 2022-12-02, 19:36

I am looking to add -q and -Q as command line parameters.

-q will output possible Q for the discrete log. For each Q it will list the number of subsequences, baby steps, and giant steps that would be used for that Q in addition to the estimated work for those values based upon the number of mulmods, hash table inserts, and hash table lookups. Right now I'm looking at fine tuning the formula because changes in the algorithms might lead to srsieve2 using a sub-optimal Q. srsieve2 chooses the Q with the lowest estimated work. This is often very close to the best Q, but not always (based upon some testing I have done). My recommendation is to use -q to find the distinct values of Q that it can use, then run ranges of 1e9 for various Q to determine which one can do the range faster than the rest.

-Q will allow you to specify which Q to use at runtime.

In my testing this is only done for the generic sieve and not for the others. I will eventually add to all of them.

With the change in formula I am seeing a 3% gain in the GPU for one sequence, but seeing a similar loss in the CPU for another.

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
mtsieve	rogue	Software	1343	2023-07-06 16:41
srsieve/sr2sieve enhancements	rogue	Software	304	2021-11-06 13:51
LLRnet enhancements	kar_bon	No Prime Left Behind	10	2008-03-28 11:21
TODO list and suggestions/comments/enhancements	Greenbank	Octoproth Search	2	2006-12-03 17:28
Suggestions for future enhancements	Reboot It	Software	16	2003-10-17 01:31

2022-12-02, 19:36	#135
rogue "Mark" Apr 2003 Between here and the 3×2,447 Posts	I am looking to add -q and -Q as command line parameters. -q will output possible Q for the discrete log. For each Q it will list the number of subsequences, baby steps, and giant steps that would be used for that Q in addition to the estimated work for those values based upon the number of mulmods, hash table inserts, and hash table lookups. Right now I'm looking at fine tuning the formula because changes in the algorithms might lead to srsieve2 using a sub-optimal Q. srsieve2 chooses the Q with the lowest estimated work. This is often very close to the best Q, but not always (based upon some testing I have done). My recommendation is to use -q to find the distinct values of Q that it can use, then run ranges of 1e9 for various Q to determine which one can do the range faster than the rest. -Q will allow you to specify which Q to use at runtime. In my testing this is only done for the generic sieve and not for the others. I will eventually add to all of them. With the change in formula I am seeing a 3% gain in the GPU for one sequence, but seeing a similar loss in the CPU for another.