mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2008-12-06, 20:54   #1
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default Msieve NFS minimum size

Why does msieve's NFS require the number to be at least 97 digits? SNFS is much faster than QS for lower levels than that. Even just postprocessing will switch to the quadratic sieve instead.
10metreh is offline   Reply With Quote
Old 2008-12-07, 02:26   #2
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·29·61 Posts
Default

Reports from users (admittedly old now) put the crossover point between msieve's QS and the GGNFS tools at 94-100 digits. Admittedly this sucks if you are completing a <97 digit job started by GGNFS. I can make the limit smaller, but I've already had a case of a public project try to use msieve for 20-digit NFS for instructional purposes.

I'll put in logic that uses NFS for postprocessing even if the input is smaller than the bound.

Last fiddled with by jasonp on 2008-12-07 at 02:28
jasonp is offline   Reply With Quote
Old 2008-12-07, 09:34   #3
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by jasonp View Post
I've already had a case of a public project try to use msieve for 20-digit NFS for instructional purposes.
LOL

Just out of interest, how much slower is NFS than QS at 20 digits?

Quote:
Originally Posted by jasonp View Post
I'll put in logic that uses NFS for postprocessing even if the input is smaller than the bound.
Do you mean in version 1.40?

BTW, I assume the crossover point you mentioned is for GNFS numbers. It's SNFS numbers that I posted this thread about.

Last fiddled with by 10metreh on 2008-12-07 at 09:37
10metreh is offline   Reply With Quote
Old 2008-12-07, 14:32   #4
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×29×61 Posts
Default

Yes, the crossover point assumes GNFS. A 100-digit SNFS job with a correctly sized polynomial is around 10x faster than using QS.

At the 20-digit size, the NFS code is all overhead. The 40-digit sample test in the GGNFS source takes something like 30 seconds, whereas QS finishes in milliseconds.
jasonp is offline   Reply With Quote
Old 2008-12-07, 17:47   #5
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by jasonp View Post
Yes, the crossover point assumes GNFS. A 100-digit SNFS job with a correctly sized polynomial is around 10x faster than using QS.
I was testing GGNFS's speed on googol+13's C94 when I found that msieve switched to QS. I thought msieve would have a lower minimum on the postprocessing.

Will you update in the next version?
10metreh is offline   Reply With Quote
Old 2008-12-14, 11:23   #6
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

My question has still not had an answer...
10metreh is offline   Reply With Quote
Old 2008-12-14, 15:53   #7
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2·29·61 Posts
Default

The answer is yes, this change is trivial to make.

The next version could be out several months from now, though, which is why I wasn't in a hurry to answer.
jasonp is offline   Reply With Quote
Old 2008-12-14, 16:23   #8
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by jasonp View Post
The answer is yes, this change is trivial to make.

The next version could be out several months from now, though, which is why I wasn't in a hurry to answer.
Argh, it looks like it'll be a long wait...

However, it's such an easy change to make that you should easily be able to do it now and then wait those few months for version 1.41.
10metreh is offline   Reply With Quote
Old 2008-12-14, 17:43   #9
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

587010 Posts
Default

Quote:
Originally Posted by 10metreh View Post
Argh, it looks like it'll be a long wait...

However, it's such an easy change to make that you should easily be able to do it now and then wait those few months for version 1.41.
i have attached a modified version of msieve 1.36 that doesnt reject lower number sizes which i compiled a while back on my athlon 64
Attached Files
File Type: zip msieve.zip (161.9 KB, 115 views)
henryzz is online now   Reply With Quote
Old 2008-12-14, 17:48   #10
10metreh
 
10metreh's Avatar
 
Nov 2008

2×33×43 Posts
Default

Quote:
Originally Posted by henryzz View Post
msieve 1.36
Could we have a similar one for 1.39? The poly selection has changed, if I want to do a C96 GNFS, for example (that will probably crop up in my aliquot sequence).

Ther is also a cygwin dll needed.

Last fiddled with by 10metreh on 2008-12-14 at 17:50
10metreh is offline   Reply With Quote
Old 2008-12-14, 18:00   #11
henryzz
Just call me Henry
 
henryzz's Avatar
 
"David"
Sep 2007
Cambridge (GMT/BST)

2·5·587 Posts
Default

Quote:
Originally Posted by 10metreh View Post
Could we have a similar one for 1.39? The poly selection has changed, if I want to do a C96 GNFS, for example (that will probably crop up in my aliquot sequence).

Ther is also a cygwin dll needed.
i forgot about that
i will have a go at compiling it
i havent compiled anything like that on my newish pc so it might not be set up properly yet

i cant do anything about needing a couple of cygwin dlls to run it
you should be able to download them easily though
henryzz is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Estimating minimum relations bchaffin Factoring 24 2012-03-24 18:37
What is minimum RAM needed for 6 Core CPU for P-1? odin Hardware 15 2010-04-18 14:22
Minimum/desired CPU specs for ECM factoring Kaboom PrimeNet 10 2009-04-17 14:58
Minimum primes of various forms database? jasong Information & Answers 1 2007-11-01 01:58
Minimum delay between server connections vaughan ElevenSmooth 5 2005-09-08 17:17

All times are UTC. The time now is 17:25.

Sat May 15 17:25:30 UTC 2021 up 37 days, 12:06, 0 users, load averages: 1.60, 1.88, 1.92

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.