mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Cunningham Tables

Reply
 
Thread Tools
Old 2007-12-17, 09:27   #34
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

Did 10240 curves at B1=110M on 3,589- and 10239 curves on 3,523-.

I simply do ~10000 on each 3,n- composite, except those that are ready for sieving already.

Alex
akruppa is offline   Reply With Quote
Old 2007-12-24, 23:12   #35
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

I'd like to reserve 3,533- for NFS.

Alex
akruppa is offline   Reply With Quote
Old 2008-01-03, 20:59   #36
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

1001101000112 Posts
Default

What would you say, is 3,527- c160 difficulty 252 an SNFS or GNFS number? What about 3,565- c160 difficulty 215.6 but with a quartic?

Alex
akruppa is offline   Reply With Quote
Old 2008-01-04, 00:50   #37
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by akruppa View Post
What would you say, is 3,527- c160 difficulty 252 an SNFS or GNFS number? What about 3,565- c160 difficulty 215.6 but with a quartic?

Alex

GNFS for both.
R.D. Silverman is offline   Reply With Quote
Old 2008-01-20, 09:33   #38
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default 3,533-

Code:
Wed Dec 26 13:23:54 2007  Msieve v. 1.32
Wed Dec 26 13:23:54 2007  random seeds: 7e744583 2bd2b85b
Wed Dec 26 13:23:54 2007  factoring 1190326221869543821572917966325809978702570962145981006882469554080512479946881241200223254954445291863827088943611095445819657747251273129779679878747749184725240225632855343166865881812906551356242819 (202 digits)
Wed Dec 26 13:23:56 2007  no P-1/P+1/ECM available, skipping
Wed Dec 26 13:23:56 2007  commencing number field sieve (201-digit input)
Wed Dec 26 13:23:56 2007  R0:  1330279464729113309844748891857449678410
Wed Dec 26 13:23:56 2007  R1: -36472996377170786403
Wed Dec 26 13:23:56 2007  A0: -1
Wed Dec 26 13:23:56 2007  A1:  3
Wed Dec 26 13:23:56 2007  A2:  6
Wed Dec 26 13:23:56 2007  A3: -4
Wed Dec 26 13:23:56 2007  A4: -5
Wed Dec 26 13:23:56 2007  A5:  1
Wed Dec 26 13:23:56 2007  A6:  1
Wed Dec 26 13:23:56 2007  size score = 4.295996e-11, Murphy alpha = 3.082719, combined = 1.780522e-11
Wed Dec 26 13:27:59 2007  restarting with 97518313 relations
Wed Dec 26 13:27:59 2007  
Wed Dec 26 13:27:59 2007  commencing relation filtering
Wed Dec 26 13:27:59 2007  commencing duplicate removal, pass 1
Wed Dec 26 13:30:59 2007  error -11 reading relation 23489158
Wed Dec 26 13:33:00 2007  error -11 reading relation 39352198
Wed Dec 26 13:33:30 2007  error -6 reading relation 43330678
Wed Dec 26 13:34:30 2007  error -6 reading relation 51077186
Wed Dec 26 13:35:00 2007  error -11 reading relation 55025904
Wed Dec 26 13:36:28 2007  error -6 reading relation 66508705
Wed Dec 26 13:37:10 2007  error -6 reading relation 71907697
Wed Dec 26 13:37:48 2007  error -6 reading relation 76943586
Wed Dec 26 13:38:31 2007  error -11 reading relation 82437229
Wed Dec 26 13:39:04 2007  error -11 reading relation 86711100
Wed Dec 26 13:39:05 2007  error -11 reading relation 86922471
Wed Dec 26 13:39:39 2007  error -11 reading relation 91225739
Wed Dec 26 13:40:10 2007  error -11 reading relation 95314957
Wed Dec 26 13:40:18 2007  error -11 reading relation 96294221
Wed Dec 26 13:40:30 2007  found 26802289 hash collisions in 97518299 relations
Wed Dec 26 13:40:30 2007  commencing duplicate removal, pass 2
Wed Dec 26 13:45:26 2007  found 15446223 duplicates and 82072076 unique relations
Wed Dec 26 13:45:26 2007  memory use: 504.8 MB
Wed Dec 26 13:46:04 2007  ignoring smallest 3692540 rational and 3692185 algebraic ideals
Wed Dec 26 13:46:04 2007  filtering ideals above 62338726
Wed Dec 26 13:46:04 2007  need 12554032 more relations than ideals
Wed Dec 26 13:46:04 2007  commencing singleton removal, pass 1
Wed Dec 26 13:57:32 2007  relations with 0 large ideals: 969350
Wed Dec 26 13:57:32 2007  relations with 1 large ideals: 6057841
Wed Dec 26 13:57:32 2007  relations with 2 large ideals: 17772352
Wed Dec 26 13:57:32 2007  relations with 3 large ideals: 27370042
Wed Dec 26 13:57:32 2007  relations with 4 large ideals: 22187240
Wed Dec 26 13:57:32 2007  relations with 5 large ideals: 7715251
Wed Dec 26 13:57:32 2007  relations with 6 large ideals: 0
Wed Dec 26 13:57:32 2007  relations with 7+ large ideals: 0
Wed Dec 26 13:57:32 2007  82072076 relations and about 59667367 large ideals
Wed Dec 26 13:57:32 2007  commencing singleton removal, pass 2
Wed Dec 26 14:09:13 2007  found 16408833 singletons
Wed Dec 26 14:09:13 2007  current dataset: 65663243 relations and about 41828732 large ideals
Wed Dec 26 14:09:13 2007  commencing singleton removal, pass 3
Wed Dec 26 14:18:40 2007  relations with 0 large ideals: 969350
Wed Dec 26 14:18:40 2007  relations with 1 large ideals: 5656217
Wed Dec 26 14:18:40 2007  relations with 2 large ideals: 15416786
Wed Dec 26 14:18:40 2007  relations with 3 large ideals: 21972200
Wed Dec 26 14:18:40 2007  relations with 4 large ideals: 16413003
Wed Dec 26 14:18:40 2007  relations with 5 large ideals: 5235687
Wed Dec 26 14:18:40 2007  relations with 6 large ideals: 0
Wed Dec 26 14:18:40 2007  relations with 7+ large ideals: 0
Wed Dec 26 14:18:40 2007  65663243 relations and about 52741943 large ideals
Wed Dec 26 14:18:40 2007  commencing singleton removal, pass 4
Wed Dec 26 14:28:17 2007  found 13294930 singletons
Wed Dec 26 14:28:17 2007  current dataset: 52368313 relations and about 38275780 large ideals
Wed Dec 26 14:28:17 2007  commencing singleton removal, pass 5
Wed Dec 26 14:38:11 2007  found 3403473 singletons
Wed Dec 26 14:38:11 2007  current dataset: 48964840 relations and about 34780175 large ideals
Wed Dec 26 14:38:11 2007  commencing singleton removal, pass 6
Wed Dec 26 14:49:50 2007  found 852512 singletons
Wed Dec 26 14:49:50 2007  current dataset: 48112328 relations and about 33921533 large ideals
Wed Dec 26 14:49:50 2007  commencing singleton removal, pass 7
Wed Dec 26 14:58:55 2007  found 208366 singletons
Wed Dec 26 14:58:55 2007  current dataset: 47903962 relations and about 33712770 large ideals
Wed Dec 26 14:58:55 2007  commencing singleton removal, final pass
Wed Dec 26 15:09:33 2007  memory use: 1647.4 MB
Wed Dec 26 15:09:33 2007  commencing in-memory singleton removal
Wed Dec 26 15:09:39 2007  begin with 47903962 relations and 38813836 unique ideals
Wed Dec 26 15:11:17 2007  reduce to 40403351 relations and 31099438 ideals in 17 passes
Wed Dec 26 15:11:17 2007  max relations containing the same ideal: 34
Wed Dec 26 15:11:22 2007  dataset has 26.0% excess relations
Wed Dec 26 15:11:56 2007  ignoring smallest 3344241 rational and 3343753 algebraic ideals
Wed Dec 26 15:11:56 2007  filtering ideals above 56104853
Wed Dec 26 15:11:56 2007  need 8373521 more relations than ideals
Wed Dec 26 15:11:56 2007  commencing singleton removal, final pass
Wed Dec 26 15:23:04 2007  memory use: 1639.4 MB
Wed Dec 26 15:23:04 2007  commencing in-memory singleton removal
Wed Dec 26 15:23:10 2007  begin with 47903962 relations and 39510132 unique ideals
Wed Dec 26 15:24:51 2007  reduce to 40389102 relations and 31780941 ideals in 17 passes
Wed Dec 26 15:24:51 2007  max relations containing the same ideal: 34
Wed Dec 26 15:25:23 2007  removing 1494545 relations and 1377225 ideals in 117320 cliques
Wed Dec 26 15:25:24 2007  commencing in-memory singleton removal
Wed Dec 26 15:25:29 2007  begin with 38894557 relations and 31780941 unique ideals
Wed Dec 26 15:26:11 2007  reduce to 38859831 relations and 30368839 ideals in 8 passes
Wed Dec 26 15:26:11 2007  max relations containing the same ideal: 33
Wed Dec 26 15:26:40 2007  removing 1089635 relations and 972315 ideals in 117320 cliques
Wed Dec 26 15:26:42 2007  commencing in-memory singleton removal
Wed Dec 26 15:26:46 2007  begin with 37770196 relations and 30368839 unique ideals
Wed Dec 26 15:27:27 2007  reduce to 37750521 relations and 29376795 ideals in 8 passes
Wed Dec 26 15:27:27 2007  max relations containing the same ideal: 33
Wed Dec 26 15:27:55 2007  removing 3350 relations and 3146 ideals in 204 cliques
Wed Dec 26 15:27:56 2007  commencing in-memory singleton removal
Wed Dec 26 15:28:00 2007  begin with 37747171 relations and 29376795 unique ideals
Wed Dec 26 15:28:05 2007  reduce to 37747171 relations and 29373649 ideals in 1 passes
Wed Dec 26 15:28:05 2007  max relations containing the same ideal: 33
Wed Dec 26 15:28:14 2007  dataset has 13.4% excess relations
Wed Dec 26 15:28:45 2007  ignoring smallest 2993835 rational and 2993431 algebraic ideals
Wed Dec 26 15:28:45 2007  filtering ideals above 49870980
Wed Dec 26 15:28:45 2007  need 7975503 more relations than ideals
Wed Dec 26 15:28:45 2007  commencing singleton removal, final pass
Wed Dec 26 15:36:30 2007  memory use: 1307.2 MB
Wed Dec 26 15:36:30 2007  commencing in-memory singleton removal
Wed Dec 26 15:36:35 2007  begin with 37747171 relations and 30073665 unique ideals
Wed Dec 26 15:37:11 2007  reduce to 37737579 relations and 30064073 ideals in 7 passes
Wed Dec 26 15:37:11 2007  max relations containing the same ideal: 34
Wed Dec 26 15:37:15 2007  dataset has 3.9% excess relations
Wed Dec 26 15:37:20 2007  relations with 0 large ideals: 498253
Wed Dec 26 15:37:20 2007  relations with 1 large ideals: 2882463
Wed Dec 26 15:37:20 2007  relations with 2 large ideals: 8349764
Wed Dec 26 15:37:20 2007  relations with 3 large ideals: 12643079
Wed Dec 26 15:37:20 2007  relations with 4 large ideals: 9927326
Wed Dec 26 15:37:20 2007  relations with 5 large ideals: 3428953
Wed Dec 26 15:37:20 2007  relations with 6 large ideals: 7733
Wed Dec 26 15:37:20 2007  relations with 7+ large ideals: 8
Wed Dec 26 15:37:20 2007  commencing 2-way merge
Wed Dec 26 15:38:00 2007  reduce to 23599193 relation sets and 15925687 unique ideals
Wed Dec 26 15:38:00 2007  commencing full merge
Wed Dec 26 15:45:27 2007  found 11879540 cycles, need 10239887
Wed Dec 26 15:45:36 2007  weight of 10239887 cycles is about 665758135 (65.02/cycle)
Wed Dec 26 15:45:36 2007  distribution of cycle lengths:
Wed Dec 26 15:45:36 2007  1 relations: 1545245
Wed Dec 26 15:45:36 2007  2 relations: 1411653
Wed Dec 26 15:45:36 2007  3 relations: 1373060
Wed Dec 26 15:45:36 2007  4 relations: 1196897
Wed Dec 26 15:45:36 2007  5 relations: 1044265
Wed Dec 26 15:45:36 2007  6 relations: 878262
Wed Dec 26 15:45:36 2007  7 relations: 741534
Wed Dec 26 15:45:36 2007  8 relations: 614041
Wed Dec 26 15:45:36 2007  9 relations: 516853
Wed Dec 26 15:45:36 2007  10+ relations: 918077
Wed Dec 26 15:45:36 2007  heaviest cycle: 13 relations
Wed Dec 26 15:45:38 2007  commencing cycle optimization
Wed Dec 26 15:46:06 2007  start with 48343832 relations
Wed Dec 26 15:48:03 2007  pruned 894931 relations
Wed Dec 26 15:48:03 2007  distribution of cycle lengths:
Wed Dec 26 15:48:03 2007  1 relations: 1545245
Wed Dec 26 15:48:03 2007  2 relations: 1437173
Wed Dec 26 15:48:03 2007  3 relations: 1416723
Wed Dec 26 15:48:03 2007  4 relations: 1217414
Wed Dec 26 15:48:03 2007  5 relations: 1065472
Wed Dec 26 15:48:03 2007  6 relations: 886793
Wed Dec 26 15:48:03 2007  7 relations: 746261
Wed Dec 26 15:48:03 2007  8 relations: 610710
Wed Dec 26 15:48:03 2007  9 relations: 507201
Wed Dec 26 15:48:03 2007  10+ relations: 806895
Wed Dec 26 15:48:03 2007  heaviest cycle: 13 relations
Wed Dec 26 15:48:38 2007  
Wed Dec 26 15:48:38 2007  commencing linear algebra
Wed Dec 26 15:48:48 2007  read 10239887 cycles
Wed Dec 26 15:50:27 2007  cycles contain 28618783 unique relations
Wed Dec 26 15:54:48 2007  read 28618783 relations
Wed Dec 26 15:56:17 2007  using 32 quadratic characters above 1073741372
Wed Dec 26 16:18:00 2007  read 10239887 cycles
Wed Dec 26 16:18:10 2007  matrix is 10219468 x 10239887 with weight 876288057 (avg 85.58/col)
Wed Dec 26 16:28:25 2007  filtering completed in 3 passes
Wed Dec 26 16:28:28 2007  matrix is 10048690 x 10048879 with weight 860420525 (avg 85.62/col)
Wed Dec 26 16:30:44 2007  read 10048879 cycles
Wed Dec 26 16:30:54 2007  matrix is 10048690 x 10048879 with weight 860420525 (avg 85.62/col)
Wed Dec 26 16:30:55 2007  saving the first 48 matrix rows for later
Wed Dec 26 16:31:03 2007  matrix is 10048642 x 10048879 with weight 656121657 (avg 65.29/col)
Wed Dec 26 16:31:03 2007  matrix includes 64 packed rows
Wed Dec 26 16:31:03 2007  using block size 43690 for processor cache size 1024 kB
Wed Dec 26 16:32:13 2007  commencing Lanczos iteration (2 threads)
Sat Jan 19 17:48:26 2008  lanczos halted after 158909 iterations (dim = 10048626)
Sat Jan 19 17:48:58 2008  recovered 39 nontrivial dependencies
Sat Jan 19 17:48:59 2008  
Sat Jan 19 17:48:59 2008  commencing square root phase
Sat Jan 19 17:48:59 2008  reading relations for dependency 1
Sat Jan 19 17:49:04 2008  read 5021608 cycles
Sat Jan 19 17:49:36 2008  cycles contain 16903515 unique relations
Sat Jan 19 17:53:47 2008  read 16903515 relations
Sat Jan 19 17:58:41 2008  multiplying 23309294 relations
Sat Jan 19 20:07:53 2008  multiply complete, coefficients have about 576.55 million bits
Sat Jan 19 20:08:24 2008  initial square root is modulo 148817
Sat Jan 19 22:56:52 2008  reading relations for dependency 2
Sat Jan 19 22:57:08 2008  read 5024236 cycles
Sat Jan 19 22:57:42 2008  cycles contain 16911873 unique relations
Sat Jan 19 23:01:51 2008  read 16911873 relations
Sat Jan 19 23:06:16 2008  multiplying 23333068 relations
Sun Jan 20 01:15:05 2008  multiply complete, coefficients have about 577.15 million bits
Sun Jan 20 01:15:36 2008  initial square root is modulo 150659
Sun Jan 20 04:01:17 2008  prp63 factor: 150998319124240638554051708078408319882230731449000713669057713
Sun Jan 20 04:01:17 2008  prp139 factor: 7883042862815906861504265211756982516171688170555130221678853379827026522092040013662664709093256898291428386732137962884501006558180661363
Sun Jan 20 04:01:17 2008  elapsed time 590:37:23
Sieved with Franke/Kleinjung lattice siever, let msieve do everything else. Doing the post-processing with msieve is very convenient, once you got the file formats right it's a fire-and-forget job.

Alex
akruppa is offline   Reply With Quote
Old 2008-01-20, 15:04   #39
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,527 Posts
Default

Quote:
Originally Posted by akruppa View Post
Sieved with Franke/Kleinjung lattice siever, let msieve do everything else. Doing the post-processing with msieve is very convenient, once you got the file formats right it's a fire-and-forget job.
24.5 days for the postprocessing but 2.5 days for the sieving? And I thought my code was fast

I'm going to regret asking this, but is it time to consider adding parallel code using MPI or OpenMP to the linear algebra? I have no way of testing it locally, and I think only Alex, Greg and Tom have the resources to run cluster-scale linear algebra, so this may be moot.

Last fiddled with by jasonp on 2008-01-20 at 15:07
jasonp is online now   Reply With Quote
Old 2008-01-20, 16:58   #40
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

2.5 days of sieving on 200 or so cpus, and 24.5 days postprocessing on 2 cpus, so I think your code is holding up pretty well!

For the linear algebra, I think having good multi-threading for multi-cpu/multi-core machines will be ok for a quite while. I imagine distributed BL or BW will be a lot of work to write, and few people will be able to get a large chunk on continuous time on a cluster to solve a large matrix - I know I won't, at least not easily. I don't mind letting a single box crunch away for a couple of weeks or a few months at worst. I mean, we don't have a deadline to meet with these factorizations or anything...

If you'd like to play with distributed matrix solving code, by all means go ahead! But I think at this time there's no dire need to have it for Cunningham factorizations.

Alex

Last fiddled with by akruppa on 2008-01-20 at 17:47 Reason: In fact, I don't know what the exact sieving time and number of cores was. Maybe ~100 cpu days?
akruppa is offline   Reply With Quote
Old 2008-01-20, 18:13   #41
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

22·3·7·112 Posts
Default

Quote:
Originally Posted by akruppa View Post
For the linear algebra, I think having good multi-threading for multi-cpu/multi-core machines will be ok for a quite while. I imagine distributed BL or BW will be a lot of work to write, and few people will be able to get a large chunk on continuous time on a cluster to solve a large matrix - I know I won't, at least not easily. I don't mind letting a single box crunch away for a couple of weeks or a few months at worst. I mean, we don't have a deadline to meet with these factorizations or anything...

If you'd like to play with distributed matrix solving code, by all means go ahead! But I think at this time there's no dire need to have it for Cunningham factorizations.

Alex
FWIW, the mpich distribution of MPI uses threads if more than one MPI-enabled process is running on the same machine. So, for instance, a dual quadcore machine can run 8 MPI programs on the same box without any network traffic. Actually, it will run more than 8 processes but two or more will be scheduled on the same core. Strangely enough, I have idle-time access to just such a machine though I have not yet used it for linear algebra. It's running P-1 with B1=1e9 on the generalized Cullen & Woodall numbers right now. Nothing too impressive has appeared yet --- the best is a P46.

But I digress --- back to the point: a case could be made that it is worth wrting MPI-enabled code even if a cluster isn't available right now. It will run multi-threaded at a reasonable speed on a single machine and it will be ready at a moment's notice if a cluster is available.

Paul
xilman is offline   Reply With Quote
Old 2008-01-20, 18:34   #42
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

112268 Posts
Default

Quote:
Originally Posted by xilman View Post
But I digress --- back to the point: a case could be made that it is worth wrting MPI-enabled code even if a cluster isn't available right now. It will run multi-threaded at a reasonable speed on a single machine and it will be ready at a moment's notice if a cluster is available.

Paul
Would you mind pointing me to tests explaining in-deep use of parallel resources to write numerical analysis code? All I got is the following:

Kenneth A. Berman & Jerome L. Paul, "Algorithms: Sequential, Parallel and Distributed" (Thomson Course technology).

Donald Knuth: "TAOCP" & "Concrete Mathematics".

MPI : The complete reference (from http://www.netlib.org/utk/papers/mpi-book/mpi-book.html)

MPI : A message-passing standard architecture (from http://www.mpi-forum.org/docs/mpi-11...pi-report.html)

I know I could check Amazon as well, but if I had a pointer in the right direction from someone who has the right knowledge, I would spare some time in choosing the right one...

Thank you in advance

Luigi
ET_ is offline   Reply With Quote
Old 2008-01-20, 22:39   #43
xilman
Bamboozled!
 
xilman's Avatar
 
May 2003
Down not across

22×3×7×112 Posts
Default

Quote:
Originally Posted by ET_ View Post
Would you mind pointing me to tests explaining in-deep use of parallel resources to write numerical analysis code?
...
I know I could check Amazon as well, but if I had a pointer in the right direction from someone who has the right knowledge, I would spare some time in choosing the right one...
To be honest, I can't help much. I don't have very much experience in the field myself.

My guess is that you may be able to pick up pointers if you investigate the HPC (High Performance Computing) area, though be prepared to come across a fair amount of Fortran...

On a more theoretical level, find out more about Tony Hoare and his research groups (that's CAR Hoare to those who don't know him --- Tony and I worked together at MS research and our paths had crossed at Oxford before that, but I digress) and "Communication Sequential Processes", or CSP.

If any more books or resources come to mind I'll post more. It's possible that Ernst may be able to help too.


Paul
xilman is offline   Reply With Quote
Old 2008-03-09, 20:08   #44
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

I'll do 3,553- c163.

Alex
akruppa is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
7+ table garo Cunningham Tables 85 2020-04-15 21:12
5- table garo Cunningham Tables 82 2020-03-15 21:47
5+ table garo Cunningham Tables 99 2020-01-10 06:29
6+ table garo Cunningham Tables 79 2020-01-01 15:26
6- table garo Cunningham Tables 41 2016-08-04 04:24

All times are UTC. The time now is 11:53.

Fri Aug 7 11:53:23 UTC 2020 up 21 days, 7:40, 1 user, load averages: 2.90, 2.68, 2.51

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.