Msieve QS estimates
 

i have been collecting data from msieve logs and i think that i should be able to predict how many full, combined and partial relations the factorization will use and thus how far a factorization is complete as full and partial relations are produced at a linear rate
estimates for my own factorizations have been quite accurate but i would like to test this a few more times
could a couple of people post a number of digits and the leading digit and i will try an estimate
after i have made the estimate could you post the msieve.log so we can see how accurate i have been

I've done a rough estimate for YAFU as well, valid for numbers big enough to use the double large prime variation only. In that case you should need roughly 328.813402*EXP(0.084148*num_digits) partial relations.

As for your msieve test, here is the largest job I've done using msieve:

number of digits: 100
leading 2 digits: 18...

[quote=bsquared;156986]I've done a rough estimate for YAFU as well, valid for numbers big enough to use the double large prime variation only. In that case you should need roughly 328.813402*EXP(0.084148*num_digits) partial relations.

As for your msieve test, here is the largest job I've done using msieve:

number of digits: 100
leading 2 digits: 18...[/quote]
i should have mentioned my data becomes much more sparse for higher digits
i have data for a 99 digit and a 102 digit
based on these
23000 full relations
76000 combined relations
1.5M partial relations
edit:
i will also have a matrix of size 93000^2 with weight ~52/col although the weight is a bit unpredictable

in future could i have the number of needed relations

[quote=henryzz;156995]i should have mentioned my data becomes much more sparse for higher digits
i have data for a 99 digit and a 102 digit
based on these
23000 full relations
76000 combined relations
1.5M partial relations
edit:
i will also have a matrix of size 93000^2 with weight ~52/col although the weight is a bit unpredictable

in future could i have the number of needed relations[/quote]

Pretty close!

[CODE][SIZE=2]
Mon Dec 1 20:50:35 2008 Msieve v. 1.38
Mon Dec 1 20:50:35 2008 random seeds: 8e9dc914 9bc0df64
Mon Dec 1 20:50:35 2008 factoring 1802716097522165018257858828415111497060066282677325501816640492782221110851604465066510547671104729 (100 digits)
Mon Dec 1 20:50:36 2008 no P-1/P+1/ECM available, skipping
Mon Dec 1 20:50:36 2008 commencing quadratic sieve (100-digit input)
Mon Dec 1 20:50:36 2008 using multiplier of 1
Mon Dec 1 20:50:36 2008 using 32kb Intel Core sieve core
Mon Dec 1 20:50:36 2008 sieve interval: 36 blocks of size 32768
Mon Dec 1 20:50:36 2008 processing polynomials in batches of 6
Mon Dec 1 20:50:36 2008 using a sieve bound of 2681729 (97602 primes)
Mon Dec 1 20:50:36 2008 using large prime bound of 402259350 (28 bits)
Mon Dec 1 20:50:36 2008 using double large prime bound of 3076883377187400 (43-52 bits)
Mon Dec 1 20:50:36 2008 using trial factoring cutoff of 52 bits
Mon Dec 1 20:50:36 2008 polynomial 'A' values have 13 factors
Tue Dec 2 03:53:25 2008 97944 relations (23379 full + 74565 combined from 1470172 partial), need 97698
Tue Dec 2 03:53:29 2008 begin with 1493551 relations
Tue Dec 2 03:53:29 2008 reduce to 258579 relations in 11 passes
Tue Dec 2 03:53:29 2008 attempting to read 258579 relations
Tue Dec 2 03:53:31 2008 recovered 258579 relations
Tue Dec 2 03:53:31 2008 recovered 247905 polynomials
Tue Dec 2 03:53:32 2008 attempting to build 97944 cycles
Tue Dec 2 03:53:32 2008 found 97944 cycles in 6 passes
Tue Dec 2 03:53:32 2008 distribution of cycle lengths:
Tue Dec 2 03:53:32 2008 length 1 : 23379
Tue Dec 2 03:53:32 2008 length 2 : 16651
Tue Dec 2 03:53:32 2008 length 3 : 16413
Tue Dec 2 03:53:32 2008 length 4 : 13382
Tue Dec 2 03:53:32 2008 length 5 : 10169
Tue Dec 2 03:53:32 2008 length 6 : 6933
Tue Dec 2 03:53:32 2008 length 7 : 4669
Tue Dec 2 03:53:32 2008 length 9+: 6348
Tue Dec 2 03:53:32 2008 largest cycle: 21 relations
Tue Dec 2 03:53:32 2008 matrix is 97602 x 97944 (26.9 MB) with weight 6276535 (64.08/col)
Tue Dec 2 03:53:32 2008 sparse part has weight 6276535 (64.08/col)
Tue Dec 2 03:53:33 2008 filtering completed in 3 passes
Tue Dec 2 03:53:33 2008 matrix is 93704 x 93768 (25.9 MB) with weight 6028303 (64.29/col)
Tue Dec 2 03:53:33 2008 sparse part has weight 6028303 (64.29/col)
Tue Dec 2 03:53:34 2008 saving the first 48 matrix rows for later
Tue Dec 2 03:53:34 2008 matrix is 93656 x 93768 (14.9 MB) with weight 4544268 (48.46/col)
Tue Dec 2 03:53:34 2008 sparse part has weight 2976114 (31.74/col)
Tue Dec 2 03:53:34 2008 matrix includes 64 packed rows
Tue Dec 2 03:53:34 2008 using block size 37507 for processor cache size 4096 kB
Tue Dec 2 03:53:35 2008 commencing Lanczos iteration
Tue Dec 2 03:53:35 2008 memory use: 14.2 MB
Tue Dec 2 03:54:08 2008 lanczos halted after 1482 iterations (dim = 93655)
Tue Dec 2 03:54:08 2008 recovered 16 nontrivial dependencies
Tue Dec 2 03:54:08 2008 prp50 factor: 38589340584901213653958931179714585367490014795273
Tue Dec 2 03:54:08 2008 prp50 factor: 46715390058453362424711065024780497160328505582673
Tue Dec 2 03:54:08 2008 elapsed time 07:03:33
[/SIZE][/CODE]

If all continues to go well, do you plan on posting your estimate method?

I have datas for 108 digits (7), 110(1), 111(2) and 112(2 numbers), if you like.
Best.

[quote=bsquared;156998]Pretty close!

[code][SIZE=2]
Mon Dec 1 20:50:35 2008 Msieve v. 1.38
Mon Dec 1 20:50:35 2008 random seeds: 8e9dc914 9bc0df64
Mon Dec 1 20:50:35 2008 factoring 1802716097522165018257858828415111497060066282677325501816640492782221110851604465066510547671104729 (100 digits)
Mon Dec 1 20:50:36 2008 no P-1/P+1/ECM available, skipping
Mon Dec 1 20:50:36 2008 commencing quadratic sieve (100-digit input)
Mon Dec 1 20:50:36 2008 using multiplier of 1
Mon Dec 1 20:50:36 2008 using 32kb Intel Core sieve core
Mon Dec 1 20:50:36 2008 sieve interval: 36 blocks of size 32768
Mon Dec 1 20:50:36 2008 processing polynomials in batches of 6
Mon Dec 1 20:50:36 2008 using a sieve bound of 2681729 (97602 primes)
Mon Dec 1 20:50:36 2008 using large prime bound of 402259350 (28 bits)
Mon Dec 1 20:50:36 2008 using double large prime bound of 3076883377187400 (43-52 bits)
Mon Dec 1 20:50:36 2008 using trial factoring cutoff of 52 bits
Mon Dec 1 20:50:36 2008 polynomial 'A' values have 13 factors
Tue Dec 2 03:53:25 2008 97944 relations (23379 full + 74565 combined from 1470172 partial), need 97698
Tue Dec 2 03:53:29 2008 begin with 1493551 relations
Tue Dec 2 03:53:29 2008 reduce to 258579 relations in 11 passes
Tue Dec 2 03:53:29 2008 attempting to read 258579 relations
Tue Dec 2 03:53:31 2008 recovered 258579 relations
Tue Dec 2 03:53:31 2008 recovered 247905 polynomials
Tue Dec 2 03:53:32 2008 attempting to build 97944 cycles
Tue Dec 2 03:53:32 2008 found 97944 cycles in 6 passes
Tue Dec 2 03:53:32 2008 distribution of cycle lengths:
Tue Dec 2 03:53:32 2008 length 1 : 23379
Tue Dec 2 03:53:32 2008 length 2 : 16651
Tue Dec 2 03:53:32 2008 length 3 : 16413
Tue Dec 2 03:53:32 2008 length 4 : 13382
Tue Dec 2 03:53:32 2008 length 5 : 10169
Tue Dec 2 03:53:32 2008 length 6 : 6933
Tue Dec 2 03:53:32 2008 length 7 : 4669
Tue Dec 2 03:53:32 2008 length 9+: 6348
Tue Dec 2 03:53:32 2008 largest cycle: 21 relations
Tue Dec 2 03:53:32 2008 matrix is 97602 x 97944 (26.9 MB) with weight 6276535 (64.08/col)
Tue Dec 2 03:53:32 2008 sparse part has weight 6276535 (64.08/col)
Tue Dec 2 03:53:33 2008 filtering completed in 3 passes
Tue Dec 2 03:53:33 2008 matrix is 93704 x 93768 (25.9 MB) with weight 6028303 (64.29/col)
Tue Dec 2 03:53:33 2008 sparse part has weight 6028303 (64.29/col)
Tue Dec 2 03:53:34 2008 saving the first 48 matrix rows for later
Tue Dec 2 03:53:34 2008 matrix is 93656 x 93768 (14.9 MB) with weight 4544268 (48.46/col)
Tue Dec 2 03:53:34 2008 sparse part has weight 2976114 (31.74/col)
Tue Dec 2 03:53:34 2008 matrix includes 64 packed rows
Tue Dec 2 03:53:34 2008 using block size 37507 for processor cache size 4096 kB
Tue Dec 2 03:53:35 2008 commencing Lanczos iteration
Tue Dec 2 03:53:35 2008 memory use: 14.2 MB
Tue Dec 2 03:54:08 2008 lanczos halted after 1482 iterations (dim = 93655)
Tue Dec 2 03:54:08 2008 recovered 16 nontrivial dependencies
Tue Dec 2 03:54:08 2008 prp50 factor: 38589340584901213653958931179714585367490014795273
Tue Dec 2 03:54:08 2008 prp50 factor: 46715390058453362424711065024780497160328505582673
Tue Dec 2 03:54:08 2008 elapsed time 07:03:33
[/SIZE][/code]If all continues to go well, do you plan on posting your estimate method?[/quote]
my method is simply make a guess based on previous factorizations that i have the log for
in future my guess for 100 digits will be based on what you posted
qs factorizations of the same size seem to have similar proportions of combined to full
the only downside to this method is you have to collect quite a bit of data
once i have finished combining my data into one file i will post it here

[quote=henryzz;157014]my method is simply make a guess based on previous factorizations that i have the log for
in future my guess for 100 digits will be based on what you posted
qs factorizations of the same size seem to have similar proportions of combined to full
the only downside to this method is you have to collect quite a bit of data
once i have finished combining my data into one file i will post it here[/quote]

Once you have a bunch of data, it should fit fairly well to an exp function as well.

[quote=bsquared;157018]Once you have a bunch of data, it should fit fairly well to an exp function as well.[/quote]
i have loads of data for up to 60 digits but i need more for higher digits
what program did you use to generate your formula

[quote=mataje;157001]I have datas for 108 digits (7), 110(1), 111(2) and 112(2 numbers), if you like.
Best.[/quote]
brilliant could you attach them in a zip here

[quote=henryzz;157031]i have loads of data for up to 60 digits but i need more for higher digits
what program did you use to generate your formula[/quote]

Excel.

Create a chart, from chart menu select add trendline, create a new exponential fit, and don't forget to select "display equation on chart" under the options tab. I have some more data for C60 < N < C100. I'll post later tonight.

It might not work well if you mix all the data though, because msieve only turns on DLP at 85 digits in size, and the relation accumlation rate (and final full/partial ratio) changes quite a bit at that point.

- ben.

[quote=henryzz;157032]brilliant could you attach them in a zip here[/quote]Done.