mersenneforum.org > YAFU YAFU-1.34
 Register FAQ Search Today's Posts Mark Forums Read

2013-02-26, 17:38   #12
bsquared

"Ben"
Feb 2007

1101001000002 Posts

Quote:
 Originally Posted by Dubslow Fun fact: Somewhere between 2500-3000 lines of new NFS code were added, written almost entirely by Ben
A good C programmer would probably have only needed half that much to accomplish the same thing .

Also, thanks for your own contributions. I appreciate your willingness to dive in anywhere in the codebase and help out.

Along those lines, thanks again to all developers, beta testers, and bug reporters. YAFU is getting way too big for me to handle on my own.

 2013-02-27, 03:16 #13 Mr. Odd   Mar 2010 5×11 Posts Factoring the C128 from 10^154+19 using 1.34: GNFS elapsed time: 41060 SNFS elapsed time: 7196 Woooo! Thanks so much for making this happen!
 2013-02-27, 20:05 #14 bsquared     "Ben" Feb 2007 1101001000002 Posts I just updated sourceforge with 1.34.3 binaries (and related source) that contains a bugfix. Hopefully this is the last one TL;DR section: One of the recent changes involved me updating all of the related factorization packages that are linked into yafu (GMP, MPIR, msieve, and GMP-ECM). This I did with varying degrees of clumsiness, the result being the bug referenced above. Now all of the associated libraries and headers should be consistent, and as a bonus, yafu now uses MPIR 2.6.0, GMP 5.1.1, and GMP-ECM 6.4.2. Happy factoring!
2013-02-28, 13:17   #15
WraithX

Mar 2006

23·59 Posts

Quote:
 Originally Posted by bsquared There is a lot of new stuff in this version, highlights include: Next, WraithX contributed his port of APRCL to YAFU, so now every factor found will be automatically proved prime. A couple new options control when it is run and how verbose the output is: -aprcl_p and -aprcl_d . The defaults are: below 500 digits are automatically proved (the upper end of that range can take a minute or two) and above 200 digits extra verbosity is enabled.
Also of note, you can manually run APR-CL (prime proving) or BPSW (probable prime test) on individual numbers.

All you have to do is type:
aprcl(10^199+153)
And you can prove this 200 digit number prime in just a few seconds! Just so you can get an idea of how long it will take to prove the primality of various sized numbers, here is a short list of times on my computer:
Code:
 100 digits : 5^143+2                 :     0.3125s
150 digits : 3^313*4+5               :     1.1719s
200 digits : 7^235*9+2               :     3.0469s
250 digits : 5^356*8-1               :     6.4844s
300 digits : 424^114+3               :    12.7344s
350 digits : 1160^114+7              :    23.6563s
400 digits : (291^163-1)/290         :    39.3281s
450 digits : 232^190+7               :    58.0313s
500 digits : 1014^166+7              :    88.1406s
550 digits : 10^549*9-7              :   147.4688s
600 digits : 1432^190+7              :   210.3281s
650 digits : 2^2159+375              :   265.9844s
700 digits : (157^319+319^157)/28    :   403.0781s
750 digits : 10^749*2+89             :   519.9531s
800 digits : (10^799*61-7)/9         :   709.7500s
850 digits : 2^2821-183              :   974.4688s
900 digits : (24^653-1)/23           :  1063.8125s
950 digits : 10^949*4-9              :  1422.8125s
1000 digits : 10^999+7                :  1588.3125s
The APR-CL code can handle numbers up to 6021 digits in length, but those numbers take a VERY long time to prove. I recently tested it on a 6002 digit input and it was proven prime in 1.56e6 seconds! Also, around those sizes you should probably switch to Primo since it will generate a primality certificate which is easy, and quick, to verify. With APR-CL there is no certificate so to verify primality, someone else would have to run APR-CL again, or some other prime proving code like Primo.

Happy factoring and/or prime proving!

 2013-02-28, 14:02 #16 Mr. Odd   Mar 2010 678 Posts I just factored a C148 with SNFS in 26 hours (vs. ~120 with GNFS). I must say it would appear SNFS is a better bet than long ECM runs. The C128 that took 2 hours with SNFS - I figure ECM for no more than 30 minutes should be fine before sending it to SNFS. I think the crossover point from ECM to SNFS is somewhere between 125 and 135 digits on my system.
2013-02-28, 14:40   #17
bsquared

"Ben"
Feb 2007

25×3×5×7 Posts

Quote:
 Originally Posted by Mr. Odd I just factored a C148 with SNFS in 26 hours (vs. ~120 with GNFS). I must say it would appear SNFS is a better bet than long ECM runs. The C128 that took 2 hours with SNFS - I figure ECM for no more than 30 minutes should be fine before sending it to SNFS.
That sounds about right. The commonly used rule of thumb is 2/9 of the snfs difficulty in ecm. So if the difficulty of your c128 is also 128 (they need not be the same!) then ecm to t28.4 (or, if you know the c128 will take 2 hours to snfs, then ecm for 26.7 minutes).

Last fiddled with by bsquared on 2013-02-28 at 15:00 Reason: 'y'

 2013-03-01, 03:42 #18 swellman     Jun 2012 B7916 Posts I feel dumb asking this question, but how do I force GNFS poly search even on a special form composite? There are situations where GNFS is prefered over SNFS. When I run yafu 1.34 it only does SNFS poly search on my xyyx type composite. The -np flag does not change this behavior. Still playing with 1.34, and so far the new functionality rocks. The additional primality tests are impressive. I'm not very familiar with them, but it's nice to be able to run several rigorous tests that identify a number as being "almost certainly" prime in a short time.
 2013-03-01, 05:02 #19 bsquared     "Ben" Feb 2007 D2016 Posts That... is not a dumb question at all. In fact it seems I've overlooked that possibility At least, nothing is occurring to me as to a way to force it to use gnfs. I guess we'll have at least one more patch to 1.34 at some point. I'll try to get it done tomorrow.
 2013-03-01, 06:22 #20 LaurV Romulan Interpreter     Jun 2011 Thailand 3·17·179 Posts I know! I know! Pick me! Pick me! You have to find a factor using ECM, first. Then, as B2 said before, it will not detect that the remaining composite comes from a SNFS-able form, and it will do GNFS...
2013-03-01, 08:22   #21
ET_
Banned

"Luigi"
Aug 2002
Team Italia

2×5×479 Posts

Quote:
 Originally Posted by LaurV I know! I know! Pick me! Pick me! You have to find a factor using ECM, first. Then, as B2 said before, it will not detect that the remaining composite comes from a SNFS-able form, and it will do GNFS...
...even if the initial number was a repdigit?

Luigi

2013-03-01, 11:21   #22
swellman

Jun 2012

3·11·89 Posts

Quote:
 Originally Posted by LaurV I know! I know! Pick me! Pick me! You have to find a factor using ECM, first. Then, as B2 said before, it will not detect that the remaining composite comes from a SNFS-able form, and it will do GNFS...
Yafu is too smart for that! With one exception, all the xyyx numbers being factored have had smaller factors stripped out but Yafu still recognizes the special form.

[begin obligatory xyyx pitch]Come on over and try it for yourself! Lots of composites needing to be factored.[/pitch]

 Similar Threads Thread Thread Starter Forum Replies Last Post bsquared YAFU 1276 2019-01-12 04:46 EdH YAFU 8 2018-03-14 17:22 storflyt32 YAFU 2 2015-06-29 05:19 bsquared YAFU 12 2012-11-08 04:12 bsquared YAFU 21 2012-09-04 19:44

All times are UTC. The time now is 14:45.

Fri Jan 15 14:45:02 UTC 2021 up 43 days, 10:56, 0 users, load averages: 1.84, 1.72, 1.71