[QUOTE=frmky;118958]Such as 2,779+. :smile: Here's the full log:
[/QUOTE]
This has made my morning quite a bit brighter.

I started the NFS part of msieve at about this time two years ago. It certainly has come a long way :) I think I'm going to take some time off from working on it, since the current version seems to meet everyone's needs and scales nicely.

Happy Thanksgiving to readers in the US.

jasonp

[QUOTE=jasonp;118973]This has made my morning quite a bit brighter.

I started the NFS part of msieve at about this time two years ago. It certainly has come a long way :) I think I'm going to take some time off from working on it, since the current version seems to meet everyone's needs and scales nicely.

Happy Thanksgiving to readers in the US.

jasonp[/QUOTE]

Do you still plan to improve poly selection or to introduce a lattice siever (after your time off)?

[QUOTE=Andi47;118974]Do you still plan to improve poly selection or to introduce a lattice siever (after your time off)?[/QUOTE]
Yes, although putting off working on it will not reduce the amount of work needed to improve on the current state of the art. We have GGNFS, and the poly selection and lattice sieving there sets a rather fearsome standard for effectiveness.

[QUOTE=jasonp;118976]Yes, although putting off working on it will not reduce the amount of work needed to improve on the current state of the art. We have GGNFS, and the poly selection and lattice sieving there sets a rather fearsome standard for effectiveness.[/QUOTE]

I know, but I am a windows user, and due to lack of linux knowledge (and currently also of time to try harder) I don't get ggnfs to work in msys/minGW - that's why I was asking.

I think I migtht have time to try again in my christmas holidays to get ggnfs to run on my PC.

[QUOTE=jasonp;118976]We have GGNFS, and the poly selection and lattice sieving there sets a rather fearsome standard for effectiveness.[/QUOTE]

Given your past track record, I'd be surprised if you couldn't make huge speed improvements.

Andi - I use the Pentium 4 Windows binaries from the ggnfs sourceforge site to start. That package has a lattice siever (Franke's) and gnfs polynomial selection tools. Once I think I have enough relations from the siever, I feed them to msieve for postprocessing.

Jason - Thanks for all the work you've done on msieve so far. Making the leap from running P-1/ECM to running NFS has always seemed a little daunting to a non-programmer. Msieve's ability to quickly and reliably finish a factorization helped get me across that gap.

[QUOTE=jasonp;117235]Now available. Highlights include:

- (if time allows) optimize/multithread the FFTs used in the NFS square root. I would love to use FFTW but it's not worth changing the license
[/QUOTE]

It doesn't support multiple threads, but would djbfft be faster? djb recently announced that he is putting it into the public domain, so there would be no license issues.

Greg

alpertron has programed apr-cle for his applet he might help uwrite it for msieve

jbristow: my pleasure; the user community has been very nice about the quirks in the library ever since I started it, and this is great motivation to keep improving it. [url="http://math-atlas.sourceforge.net/faq.html#utone"]Some projects aren't so lucky[/url]

frmky: I hadn't thought of that. djbfft has some quirks that make it more work to deal with. It doesn't support large transform sizes (though it can be used as the base case of a recursion), it permutes the input order in a weird bit reversal pattern that my calling code does not expect, etc. It's on the back burner, I'll take a look when I have time

henryzz: I'm currently exploring many NFS ideas, there's no time left for primality proving. Maybe someday...

[QUOTE=jasonp;119604] It's on the back burner, I'll take a look when I have time[/QUOTE]

Of course it's low priority.

For your reading pleasure, here's the log of the filtering for the NFSNet factorization of 10,239-. The computer had only 3 GB of memory, but msieve wanted 3.6 GB to build the matrix. I just let it run, hard drive thrashing, so build_matrix_core took 16 hours rather than 16 minutes to complete. But it was successful, and the matrix fits comfortably in memory for the BL. The BL will take about 18.5 days to complete on this 2.4GHz single core Opteron.

Greg

[CODE]Thu Nov 29 19:09:58 2007 Msieve v. 1.30
Thu Nov 29 19:09:58 2007 random seeds: a96709a9 c873f4b7
Thu Nov 29 19:09:58 2007 factoring 162385812809900583261295597372983559948698484946321658540735656202018003505845104737134070357362269119992033891923896707742660065148483572244656969761256208962241824944638737217461295395400432531624931235045560966776497496089919 (228 digits)
Thu Nov 29 19:09:59 2007 commencing number field sieve (227-digit input)
Thu Nov 29 19:09:59 2007 R0: -10000000000000000000000000000000000000000
Thu Nov 29 19:09:59 2007 R1: 1
Thu Nov 29 19:09:59 2007 A0: -10
Thu Nov 29 19:09:59 2007 A1: 0
Thu Nov 29 19:09:59 2007 A2: 0
Thu Nov 29 19:09:59 2007 A3: 0
Thu Nov 29 19:09:59 2007 A4: 0
Thu Nov 29 19:09:59 2007 A5: 0
Thu Nov 29 19:09:59 2007 A6: 1
Thu Nov 29 19:09:59 2007 size score = 1.465344e-11, Murphy alpha = 1.334581, combined = 1.000782e-11
Thu Nov 29 19:16:23 2007 restarting with 102731357 relations
Thu Nov 29 19:16:23 2007
Thu Nov 29 19:16:23 2007 commencing relation filtering
Thu Nov 29 19:16:23 2007 commencing duplicate removal, pass 1
Thu Nov 29 19:16:45 2007 error -4 reading relation 1295254
Thu Nov 29 19:31:29 2007 error -10 reading relation 100896689
Thu Nov 29 19:31:45 2007 found 24048635 hash collisions in 102731302 relations
Thu Nov 29 19:31:45 2007 commencing duplicate removal, pass 2
Thu Nov 29 19:40:53 2007 found 9611827 duplicates and 93119475 unique relations
Thu Nov 29 19:40:53 2007 memory use: 504.8 MB
Thu Nov 29 19:41:26 2007 ignoring smallest 3388380 rational and 3387534 algebraic ideals
Thu Nov 29 19:41:26 2007 filtering ideals above 56891993
Thu Nov 29 19:41:26 2007 need 11519053 more relations than ideals
Thu Nov 29 19:41:26 2007 commencing singleton removal, pass 1
Thu Nov 29 19:56:44 2007 relations with 0 large ideals: 1265518
Thu Nov 29 19:56:44 2007 relations with 1 large ideals: 6989594
Thu Nov 29 19:56:44 2007 relations with 2 large ideals: 20618077
Thu Nov 29 19:56:44 2007 relations with 3 large ideals: 31485241
Thu Nov 29 19:56:44 2007 relations with 4 large ideals: 24825785
Thu Nov 29 19:56:44 2007 relations with 5 large ideals: 7935260
Thu Nov 29 19:56:44 2007 relations with 6 large ideals: 0
Thu Nov 29 19:56:44 2007 relations with 7+ large ideals: 0
Thu Nov 29 19:56:44 2007 93119475 relations and about 62171073 large ideals
Thu Nov 29 19:56:44 2007 commencing singleton removal, pass 2
Thu Nov 29 20:12:37 2007 found 14608773 singletons
Thu Nov 29 20:12:37 2007 current dataset: 78510702 relations and about 46601262 large ideals
Thu Nov 29 20:12:38 2007 commencing singleton removal, pass 3
Thu Nov 29 20:26:28 2007 relations with 0 large ideals: 1265518
Thu Nov 29 20:26:28 2007 relations with 1 large ideals: 6588634
Thu Nov 29 20:26:28 2007 relations with 2 large ideals: 18333981
Thu Nov 29 20:26:28 2007 relations with 3 large ideals: 26473285
Thu Nov 29 20:26:28 2007 relations with 4 large ideals: 19799592
Thu Nov 29 20:26:28 2007 relations with 5 large ideals: 6049692
Thu Nov 29 20:26:28 2007 relations with 6 large ideals: 0
Thu Nov 29 20:26:28 2007 relations with 7+ large ideals: 0
Thu Nov 29 20:26:28 2007 78510702 relations and about 58600419 large ideals
Thu Nov 29 20:26:28 2007 commencing singleton removal, pass 4
Thu Nov 29 20:40:45 2007 found 12127433 singletons
Thu Nov 29 20:40:45 2007 current dataset: 66383269 relations and about 45688156 large ideals
Thu Nov 29 20:40:45 2007 commencing singleton removal, pass 5
Thu Nov 29 20:54:05 2007 found 2556776 singletons
Thu Nov 29 20:54:05 2007 current dataset: 63826493 relations and about 43090361 large ideals
Thu Nov 29 20:54:05 2007 commencing singleton removal, pass 6
Thu Nov 29 21:07:06 2007 found 497209 singletons
Thu Nov 29 21:07:06 2007 current dataset: 63329284 relations and about 42591391 large ideals
Thu Nov 29 21:07:07 2007 commencing singleton removal, final pass
Thu Nov 29 21:21:07 2007 memory use: 2581.2 MB
Thu Nov 29 21:21:08 2007 commencing in-memory singleton removal
Thu Nov 29 21:21:16 2007 begin with 63329284 relations and 49423177 unique ideals
Thu Nov 29 21:23:12 2007 reduce to 56463162 relations and 42401285 ideals in 14 passes
Thu Nov 29 21:23:12 2007 max relations containing the same ideal: 38
Thu Nov 29 21:23:51 2007 removing 3196553 relations and 2796553 ideals in 400000 cliques
Thu Nov 29 21:23:53 2007 commencing in-memory singleton removal
Thu Nov 29 21:24:00 2007 begin with 53266609 relations and 42401285 unique ideals
Thu Nov 29 21:25:00 2007 reduce to 53165066 relations and 39502284 ideals in 8 passes
Thu Nov 29 21:25:00 2007 max relations containing the same ideal: 38
Thu Nov 29 21:25:36 2007 removing 2377955 relations and 1977955 ideals in 400000 cliques
Thu Nov 29 21:25:38 2007 commencing in-memory singleton removal
Thu Nov 29 21:25:44 2007 begin with 50787111 relations and 39502284 unique ideals
Thu Nov 29 21:26:33 2007 reduce to 50723623 relations and 37460379 ideals in 7 passes
Thu Nov 29 21:26:33 2007 max relations containing the same ideal: 38
Thu Nov 29 21:27:06 2007 removing 2113841 relations and 1713841 ideals in 400000 cliques
Thu Nov 29 21:27:08 2007 commencing in-memory singleton removal
Thu Nov 29 21:27:14 2007 begin with 48609782 relations and 37460379 unique ideals
Thu Nov 29 21:27:53 2007 reduce to 48556064 relations and 35692437 ideals in 6 passes
Thu Nov 29 21:27:53 2007 max relations containing the same ideal: 38
Thu Nov 29 21:28:25 2007 removing 1965759 relations and 1565759 ideals in 400000 cliques
Thu Nov 29 21:28:26 2007 commencing in-memory singleton removal
Thu Nov 29 21:28:32 2007 begin with 46590305 relations and 35692437 unique ideals
Thu Nov 29 21:29:16 2007 reduce to 46540875 relations and 34076924 ideals in 7 passes
Thu Nov 29 21:29:16 2007 max relations containing the same ideal: 38
Thu Nov 29 21:29:45 2007 removing 1862269 relations and 1462269 ideals in 400000 cliques
Thu Nov 29 21:29:47 2007 commencing in-memory singleton removal
Thu Nov 29 21:29:52 2007 begin with 44678606 relations and 34076924 unique ideals
Thu Nov 29 21:30:27 2007 reduce to 44631173 relations and 32566856 ideals in 6 passes
Thu Nov 29 21:30:27 2007 max relations containing the same ideal: 37
Thu Nov 29 21:30:56 2007 removing 1788110 relations and 1388110 ideals in 400000 cliques
Thu Nov 29 21:30:58 2007 commencing in-memory singleton removal
Thu Nov 29 21:31:03 2007 begin with 42843063 relations and 32566856 unique ideals
Thu Nov 29 21:31:36 2007 reduce to 42798269 relations and 31133606 ideals in 6 passes
Thu Nov 29 21:31:36 2007 max relations containing the same ideal: 37
Thu Nov 29 21:32:03 2007 removing 734799 relations and 589190 ideals in 145609 cliques
Thu Nov 29 21:32:04 2007 commencing in-memory singleton removal
Thu Nov 29 21:32:09 2007 begin with 42063470 relations and 31133606 unique ideals
Thu Nov 29 21:32:36 2007 reduce to 42056252 relations and 30537174 ideals in 5 passes
Thu Nov 29 21:32:36 2007 max relations containing the same ideal: 37
Thu Nov 29 21:32:43 2007 dataset has 70.0% excess relations
Thu Nov 29 21:33:13 2007 ignoring smallest 3068865 rational and 3067258 algebraic ideals
Thu Nov 29 21:33:13 2007 filtering ideals above 51202793
Thu Nov 29 21:33:13 2007 need 10367170 more relations than ideals
Thu Nov 29 21:33:13 2007 commencing singleton removal, final pass
Thu Nov 29 21:44:58 2007 memory use: 1307.2 MB
Thu Nov 29 21:44:58 2007 commencing in-memory singleton removal
Thu Nov 29 21:45:02 2007 begin with 42056252 relations and 31176949 unique ideals
Thu Nov 29 21:45:24 2007 reduce to 42055869 relations and 31176566 ideals in 4 passes
Thu Nov 29 21:45:24 2007 max relations containing the same ideal: 37
Thu Nov 29 21:45:49 2007 removing 1076842 relations and 820776 ideals in 256066 cliques
Thu Nov 29 21:45:50 2007 commencing in-memory singleton removal
Thu Nov 29 21:45:55 2007 begin with 40979027 relations and 31176566 unique ideals
Thu Nov 29 21:46:26 2007 reduce to 40959127 relations and 30335771 ideals in 6 passes
Thu Nov 29 21:46:26 2007 max relations containing the same ideal: 35
Thu Nov 29 21:46:51 2007 removing 1102304 relations and 846238 ideals in 256066 cliques
Thu Nov 29 21:46:52 2007 commencing in-memory singleton removal
Thu Nov 29 21:46:57 2007 begin with 39856823 relations and 30335771 unique ideals
Thu Nov 29 21:47:22 2007 reduce to 39838690 relations and 29471301 ideals in 5 passes
Thu Nov 29 21:47:22 2007 max relations containing the same ideal: 35
Thu Nov 29 21:47:46 2007 removing 1937 relations and 1719 ideals in 218 cliques
Thu Nov 29 21:47:47 2007 commencing in-memory singleton removal
Thu Nov 29 21:47:51 2007 begin with 39836753 relations and 29471301 unique ideals
Thu Nov 29 21:47:56 2007 reduce to 39836753 relations and 29469582 ideals in 1 passes
Thu Nov 29 21:47:56 2007 max relations containing the same ideal: 35
Thu Nov 29 21:48:02 2007 dataset has 53.0% excess relations
Thu Nov 29 21:48:29 2007 ignoring smallest 2747456 rational and 2746456 algebraic ideals
Thu Nov 29 21:48:29 2007 filtering ideals above 45513594
Thu Nov 29 21:48:29 2007 need 8293736 more relations than ideals
Thu Nov 29 21:48:29 2007 commencing singleton removal, final pass
Thu Nov 29 22:00:13 2007 memory use: 1307.2 MB
Thu Nov 29 22:00:13 2007 commencing in-memory singleton removal
Thu Nov 29 22:00:17 2007 begin with 39836753 relations and 30111789 unique ideals
Thu Nov 29 22:00:43 2007 reduce to 39836664 relations and 30111700 ideals in 5 passes
Thu Nov 29 22:00:43 2007 max relations containing the same ideal: 35
Thu Nov 29 22:01:08 2007 removing 1607342 relations and 1207342 ideals in 400000 cliques
Thu Nov 29 22:01:10 2007 commencing in-memory singleton removal
Thu Nov 29 22:01:15 2007 begin with 38229322 relations and 30111700 unique ideals
Thu Nov 29 22:01:50 2007 reduce to 38186826 relations and 28861520 ideals in 7 passes
Thu Nov 29 22:01:50 2007 max relations containing the same ideal: 35
Thu Nov 29 22:02:14 2007 removing 1627524 relations and 1227524 ideals in 400000 cliques
Thu Nov 29 22:02:15 2007 commencing in-memory singleton removal
Thu Nov 29 22:02:20 2007 begin with 36559302 relations and 28861520 unique ideals
Thu Nov 29 22:02:48 2007 reduce to 36516313 relations and 27590616 ideals in 6 passes
Thu Nov 29 22:02:48 2007 max relations containing the same ideal: 35
Thu Nov 29 22:03:11 2007 removing 1593449 relations and 1193449 ideals in 400000 cliques
Thu Nov 29 22:03:12 2007 commencing in-memory singleton removal
Thu Nov 29 22:03:16 2007 begin with 34922864 relations and 27590616 unique ideals
Thu Nov 29 22:03:47 2007 reduce to 34875821 relations and 26349694 ideals in 7 passes
Thu Nov 29 22:03:47 2007 max relations containing the same ideal: 35
Thu Nov 29 22:04:09 2007 removing 1003590 relations and 771200 ideals in 232390 cliques
Thu Nov 29 22:04:10 2007 commencing in-memory singleton removal
Thu Nov 29 22:04:14 2007 begin with 33872231 relations and 26349694 unique ideals
Thu Nov 29 22:04:36 2007 reduce to 33854151 relations and 25560311 ideals in 5 passes
Thu Nov 29 22:04:36 2007 max relations containing the same ideal: 35
Thu Nov 29 22:04:57 2007 removing 929 relations and 826 ideals in 103 cliques
Thu Nov 29 22:04:57 2007 commencing in-memory singleton removal
Thu Nov 29 22:05:01 2007 begin with 33853222 relations and 25560311 unique ideals
Thu Nov 29 22:05:05 2007 reduce to 33853222 relations and 25559485 ideals in 1 passes
Thu Nov 29 22:05:05 2007 max relations containing the same ideal: 35
Thu Nov 29 22:05:11 2007 dataset has 22.4% excess relations
Thu Nov 29 22:05:34 2007 ignoring smallest 2423663 rational and 2422018 algebraic ideals
Thu Nov 29 22:05:34 2007 filtering ideals above 39824395
Thu Nov 29 22:05:34 2007 need 7317987 more relations than ideals
Thu Nov 29 22:05:34 2007 commencing singleton removal, final pass
Thu Nov 29 22:16:20 2007 memory use: 1307.2 MB
Thu Nov 29 22:16:21 2007 commencing in-memory singleton removal
Thu Nov 29 22:16:24 2007 begin with 33853222 relations and 26207707 unique ideals
Thu Nov 29 22:16:42 2007 reduce to 33853079 relations and 26207564 ideals in 4 passes
Thu Nov 29 22:16:42 2007 max relations containing the same ideal: 35
Thu Nov 29 22:17:03 2007 removing 692391 relations and 528627 ideals in 163764 cliques
Thu Nov 29 22:17:04 2007 commencing in-memory singleton removal
Thu Nov 29 22:17:08 2007 begin with 33160688 relations and 26207564 unique ideals
Thu Nov 29 22:17:30 2007 reduce to 33151521 relations and 25669736 ideals in 5 passes
Thu Nov 29 22:17:30 2007 max relations containing the same ideal: 34
Thu Nov 29 22:17:50 2007 removing 655387 relations and 491623 ideals in 163764 cliques
Thu Nov 29 22:17:51 2007 commencing in-memory singleton removal
Thu Nov 29 22:17:55 2007 begin with 32496134 relations and 25669736 unique ideals
Thu Nov 29 22:18:16 2007 reduce to 32486954 relations and 25168897 ideals in 5 passes
Thu Nov 29 22:18:16 2007 max relations containing the same ideal: 34
Thu Nov 29 22:18:21 2007 dataset has 8.0% excess relations
Thu Nov 29 22:18:26 2007 relations with 0 large ideals: 586795
Thu Nov 29 22:18:26 2007 relations with 1 large ideals: 2571938
Thu Nov 29 22:18:26 2007 relations with 2 large ideals: 7047808
Thu Nov 29 22:18:26 2007 relations with 3 large ideals: 10174750
Thu Nov 29 22:18:26 2007 relations with 4 large ideals: 8093550
Thu Nov 29 22:18:26 2007 relations with 5 large ideals: 3404119
Thu Nov 29 22:18:26 2007 relations with 6 large ideals: 519728
Thu Nov 29 22:18:26 2007 relations with 7+ large ideals: 88266
Thu Nov 29 22:18:26 2007 commencing 2-way merge
Thu Nov 29 22:18:55 2007 reduce to 22572540 relation sets and 15254483 unique ideals
Thu Nov 29 22:18:55 2007 commencing full merge
Thu Nov 29 22:24:25 2007 found 11228139 cycles, need 8760683
Thu Nov 29 22:24:31 2007 weight of 8760683 cycles is about 569584972 (65.02/cycle)
Thu Nov 29 22:24:32 2007 distribution of cycle lengths:
Thu Nov 29 22:24:32 2007 1 relations: 1156515
Thu Nov 29 22:24:32 2007 2 relations: 1003893
Thu Nov 29 22:24:32 2007 3 relations: 1074594
Thu Nov 29 22:24:32 2007 4 relations: 1056241
Thu Nov 29 22:24:32 2007 5 relations: 1023854
Thu Nov 29 22:24:32 2007 6 relations: 950828
Thu Nov 29 22:24:32 2007 7 relations: 857326
Thu Nov 29 22:24:32 2007 8 relations: 751170
Thu Nov 29 22:24:32 2007 9 relations: 608532
Thu Nov 29 22:24:32 2007 10+ relations: 277730
Thu Nov 29 22:24:32 2007 heaviest cycle: 12 relations
Thu Nov 29 22:24:33 2007 commencing cycle optimization
Thu Nov 29 22:24:53 2007 start with 41707139 relations
Thu Nov 29 22:29:23 2007 pruned 754535 relations
Thu Nov 29 22:29:23 2007 distribution of cycle lengths:
Thu Nov 29 22:29:24 2007 1 relations: 1156515
Thu Nov 29 22:29:24 2007 2 relations: 1022003
Thu Nov 29 22:29:24 2007 3 relations: 1109903
Thu Nov 29 22:29:24 2007 4 relations: 1084137
Thu Nov 29 22:29:24 2007 5 relations: 1058355
Thu Nov 29 22:29:24 2007 6 relations: 973975
Thu Nov 29 22:29:24 2007 7 relations: 870111
Thu Nov 29 22:29:24 2007 8 relations: 731319
Thu Nov 29 22:29:24 2007 9 relations: 538565
Thu Nov 29 22:29:24 2007 10+ relations: 215800
Thu Nov 29 22:29:24 2007 heaviest cycle: 12 relations
Thu Nov 29 22:29:41 2007
Thu Nov 29 22:29:46 2007 commencing linear algebra
Thu Nov 29 22:29:48 2007 read 8760683 cycles
Thu Nov 29 22:30:53 2007 cycles contain 24183251 unique relations
Thu Nov 29 22:40:09 2007 read 24183251 relations
Thu Nov 29 22:49:22 2007 using 32 quadratic characters above 1073740440
Fri Nov 30 14:55:39 2007 read 8760683 cycles
Fri Nov 30 14:57:37 2007 matrix is 8752464 x 8760683 with weight 776243489 (avg 88.61/col)
Fri Nov 30 15:07:37 2007 filtering completed in 3 passes
Fri Nov 30 15:07:40 2007 matrix is 8638835 x 8639035 with weight 768104215 (avg 88.91/col)
Fri Nov 30 15:39:45 2007 read 8639035 cycles
Fri Nov 30 15:41:35 2007 matrix is 8638835 x 8639035 with weight 768104215 (avg 88.91/col)
Fri Nov 30 15:41:36 2007 saving the first 48 matrix rows for later
Fri Nov 30 15:41:42 2007 matrix is 8638787 x 8639035 with weight 581239234 (avg 67.28/col)
Fri Nov 30 15:41:42 2007 matrix includes 64 packed rows
Fri Nov 30 15:41:42 2007 using block size 43690 for processor cache size 1024 kB
Fri Nov 30 15:43:10 2007 commencing Lanczos iteration
[/CODE]

The matrix is both larger and heavier than the one from 3,499+, but takes only 18.5 days to solve? I'll have to learn how to use msieve for the linear algebra! Is there a way to feed readily merged relations into msieve for matrix building and solving?

Alex