mersenneforum.org Msieve QS estimates
 Register FAQ Search Today's Posts Mark Forums Read

 2009-01-05, 15:58 #1 henryzz Just call me Henry     "David" Sep 2007 Liverpool (GMT/BST) 27×47 Posts 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
 2009-01-05, 16:05 #2 bsquared     "Ben" Feb 2007 3×17×73 Posts 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...
2009-01-05, 16:31   #3
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

27×47 Posts

Quote:
 Originally Posted by bsquared 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...
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

Last fiddled with by henryzz on 2009-01-05 at 16:38

2009-01-05, 16:50   #4
bsquared

"Ben"
Feb 2007

E8B16 Posts

Quote:
 Originally Posted by henryzz 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
Pretty close!

Code:

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

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

 2009-01-05, 17:11 #5 mataje     Jan 2009 Bilbao, Spain 28310 Posts I have datas for 108 digits (7), 110(1), 111(2) and 112(2 numbers), if you like. Best.
2009-01-05, 18:46   #6
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

27·47 Posts

Quote:
 Originally Posted by bsquared Pretty close! Code:  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  If all continues to go well, do you plan on posting your estimate method?
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

2009-01-05, 19:06   #7
bsquared

"Ben"
Feb 2007

72138 Posts

Quote:
 Originally Posted by henryzz 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
Once you have a bunch of data, it should fit fairly well to an exp function as well.

2009-01-05, 20:39   #8
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

27×47 Posts

Quote:
 Originally Posted by bsquared Once you have a bunch of data, it should fit fairly well to an exp function as well.
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

2009-01-05, 20:42   #9
henryzz
Just call me Henry

"David"
Sep 2007
Liverpool (GMT/BST)

601610 Posts

Quote:
 Originally Posted by mataje I have datas for 108 digits (7), 110(1), 111(2) and 112(2 numbers), if you like. Best.
brilliant could you attach them in a zip here

2009-01-05, 21:06   #10
bsquared

"Ben"
Feb 2007

3×17×73 Posts

Quote:
 Originally Posted by henryzz 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
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.

2009-01-05, 22:46   #11
mataje

Jan 2009
Bilbao, Spain

283 Posts

Quote:
 Originally Posted by henryzz brilliant could you attach them in a zip here
Done.
Attached Files
 Partition factors.zip (14.8 KB, 144 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post burrobert Msieve 9 2012-10-26 22:46 henryzz GMP-ECM 8 2009-12-31 17:51 10metreh Factoring 48 2009-04-08 01:54 brownkenny Math 2 2009-01-22 17:21 kdq Software 4 2008-10-04 05:02

All times are UTC. The time now is 10:35.

Thu Dec 8 10:35:56 UTC 2022 up 112 days, 8:04, 0 users, load averages: 0.71, 0.70, 0.72