mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > YAFU

Reply
 
Thread Tools
Old 2010-02-21, 22:21   #342
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

1101110101012 Posts
Default

Quote:
Originally Posted by bsquared View Post
That warning message isn't part of YAFU, is it aliquiet? But that factorization is also not right... it looks like the input was not parsed correctly. That's something I've not seen in years, so I'm guessing it's a build issue on your older pc. Having you been using YAFU for a while on this pc and this is the first time you've seen this problem, or are you just now trying it out again?
I noticed awhile ago. I think it was this machine, but not not sure if I've seen it elsewhere. This is the one machine that gave us all the trouble before, so it's the only one using an earlier source. I've been using it to run aliquot sequences since then with a preference to yafu and it's been clocking along, but I don't keep an eye on it all the time. It really seems that it is a rare occurrence, though.

Unfortunately, this is also the machine I'm using to work on my bootable USB/CD project, so my live-OS is currently using it. Once I get things settled well for my project, I suppose I'll need to use a different machine to generate the final version, so I can have all the most current programs running. It will actually be interesting to see what a live usb from a different machine would do in this one...

This isn't really a big issue for me, and it is an earlier version, so maybe we shouldn't put any effort into figuring it out. It was just a curiosity, really.

Thanks,
Ed

Last fiddled with by EdH on 2010-02-21 at 22:23 Reason: grammar...
EdH is offline   Reply With Quote
Old 2010-02-22, 15:43   #343
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,361 Posts
Default

Perhaps there is a bug which introduces rare parsing errors in older source. I haven't heard of anything similar with current source... so I don't think I'll look into this further. Feel free to let me know if it happens again, though; maybe a debug clue will surface.
bsquared is offline   Reply With Quote
Old 2010-03-05, 21:01   #344
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,361 Posts
Default version 1.16 available

Version 1.16 of YAFU is now available here

changes include:
+ slightly faster SIQS (ranging from none to 5%, depending on the input size and your OS/platform).
+ very much faster Sieve of Erathostenes, on 64 bit systems: ~ 25%. probably just slightly faster on 32 bit systems (1 - 2%)
+ cosmetic changes and bugfixes
+ others

It is getting increasingly hard to squeeze any more performance out of the SIQS routine. I tried dozens of things and all failed except one which resulted in only a minor improvement. I still have a few ideas, but further development of siqs will likely stop soon.

The next logical step is to try to get ggnfs into yafu. While I would love to dig into the nuts and bolts of the algorithm and the math behind it, and in the process see if any of the sieving tricks I learned with yafu could improve the sieving step somewhere, it is simply not realistic for me to do right now.

Instead I could try integrating ggnfs and msieve binary calls into some sort of C version of factmsieve.py or .pl within yafu, but I see little point to doing that with those tools around.

Or I could stay where I've had some success and keep plugging away at siqs. Maybe get to 3LP like I've been talking about for years now :)

Whatever the direction, I know i'll keep fiddling with the code in one way or another - it's just too addicting a habit to do otherwise...

- ben.

Last fiddled with by bsquared on 2010-03-05 at 21:05 Reason: misleading wording of 32 bit SOE performance...
bsquared is offline   Reply With Quote
Old 2010-03-05, 21:49   #345
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,361 Posts
Default

If you downloaded 1.16 prior to now, you may want to do so again. I forgot to turn off one debug setting which forces picking the same random seed... It is fixed now.

[edit]
Also, the zip package now includes Win64 binaries.

Last fiddled with by bsquared on 2010-03-05 at 22:29
bsquared is offline   Reply With Quote
Old 2010-03-06, 14:25   #346
Andi_HB
 
Andi_HB's Avatar
 
Mar 2007
Germany

4108 Posts
Default

Quote:
Originally Posted by bsquared View Post
The next logical step is to try to get ggnfs into yafu.

Instead I could try integrating ggnfs and msieve binary calls into some sort of C version of factmsieve.py or .pl within yafu, but I see little point to doing that with those tools around.

- ben.
It`s time to say thank you for all the good work you have done!
Yafu is really a nice programm and its grown up and a alternative to msieve.
Hope Yafu1.16 is not the last version and you find the time to integrate ggnfs in the future.

Regards Andi_HB
Andi_HB is offline   Reply With Quote
Old 2010-03-06, 16:56   #347
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

2×3×19×31 Posts
Default

Ditto, your tool has grown up quite a bit and now represents the state of the art in production-quality SIQS.

At the risk of sounding greedy, I could give you ownership of msieve's SIQS directory, and the YAFU interpreter could call msieve as a library for ECM or QS (and eventually GNFS). You'd have access to the latest LA and filtering building blocks (like you already do now :)

We can achieve seamless integration of business synergy, and push the YAFU (C-with-a-circle-thingy) brand to its next level :)

Last fiddled with by jasonp on 2010-03-06 at 17:05
jasonp is offline   Reply With Quote
Old 2010-03-08, 05:15   #348
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

1101001000012 Posts
Default

Quote:
Originally Posted by jasonp View Post
Ditto, your tool has grown up quite a bit and now represents the state of the art in production-quality SIQS.
Not without quite a few growing pains ;) Thanks Jason, Andi_HB, and everyone else who has helped YAFU become what it is today.


Quote:
Originally Posted by jasonp View Post
At the risk of sounding greedy, I could give you ownership of msieve's SIQS directory, and the YAFU interpreter could call msieve as a library for ECM or QS (and eventually GNFS). You'd have access to the latest LA and filtering building blocks (like you already do now :)

We can achieve seamless integration of business synergy, and push the YAFU (C-with-a-circle-thingy) brand to its next level :)
Are you trying to incentivize me? That was an awful lot of managerspeak ;)

1.16 is definately not the last version of YAFU - there are several other things I'd like to do and I've started on some already. We'll have to talk more about the things you mentioned.
bsquared is offline   Reply With Quote
Old 2010-03-11, 21:50   #349
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

3,361 Posts
Default experimental version 1.17 available

Now available in the usual spot

Experimental version 1.17
+ Added an adaptive routine for optimization of the small trial division cutoff
constant in siqs. The initial guess for this value is usually pretty close, but
sometimes not. This results in a speedup of from 0 to 7% or so in siqs, depending on
the OS/platform and input number size.
+ fixed a bug in mpqs - relation storage was overflowing for 64k blocksizes. Thanks
Will Fay!


The reason I'm calling this experimental is that while I've observed speedups in siqs during tests on a range of OS and cpu types, the "optimization" being performed may very well degrade performance slightly instead, depending on the input number. On average it seems to be a win, but wanted to get input from other machines if people are willing.

Running siqs with these binaries will append to a file called optfile.csv, which records the state of the variable being optimized as well as the measure of performance (rels/sec/poly). What's neat is when I see stuff like the attached .jpg. Those curves resulted in a 7% improvement in the speed of a C82. That won't happen all the time - just when the old code makes a bad guess of the small trial division cutoff constant.

Optimization of that constant is easy to do, as it directly effects the relation discovery rate while not changing things like the rate at which partials combine to fulls (as would happen if the large prime bound were optimized) or the total number of relations needed (as would happen if the factor base bound were optimized), making it a 1 dimensional problem.

The optimization occurs in the top level SIQS.c file, in the main loop. This file is available on the webpage as well, if anyone is interested. Any feedback (comparison to previous versions, neat .csv files, etc; as a post, PM, or email) would be appreciated!


- ben.
Attached Thumbnails
Click image for larger version

Name:	example_opt_behavior.jpg
Views:	84
Size:	80.9 KB
ID:	4837  

Last fiddled with by bsquared on 2010-03-11 at 22:19 Reason: made file available
bsquared is offline   Reply With Quote
Old 2010-03-12, 00:34   #350
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

33·73 Posts
Default

Quote:
Originally Posted by bsquared View Post
+ fixed a bug in mpqs - relation storage was overflowing for 64k blocksizes. Thanks Will Fay!
Ah, good, I was wondering why the number of "failed to find factor" (prominent on smaller composites) increased... This is probably it. thx
Batalov is offline   Reply With Quote
Old 2010-03-12, 02:14   #351
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

336110 Posts
Default

Quote:
Originally Posted by Batalov View Post
Ah, good, I was wondering why the number of "failed to find factor" (prominent on smaller composites) increased... This is probably it. thx
Yes, it would have affected mostly smaller composites (20ish digits). I'd expect "failed to find factor" to go away after this (and another minor) fix.
bsquared is offline   Reply With Quote
Old 2010-03-13, 11:52   #352
rekcahx
 
Oct 2009
Oulu, Finland

1E16 Posts
Default Problem?

I think that there is a problem in parser.

In first case, all went OK
Quote:
rekcahx@oah:~/yafu16$ ./yafu "factor(19^30+2)"


factoring 230466617897195215045509519405933293403

div: primes less than 10000
Total factoring time = 0.2354 seconds


***factors found***

P1 = 3
P3 = 353
PRP27 = 724964934182772877121233939
PRP9 = 300189203

ans = 1
but in second case, miserably failure:
Quote:
rekcahx@oah:~/yafu16$ ./yafu "factor(19^100+2)"


factoring 21

div: primes less than 10000
Total factoring time = 0.0237 seconds


***factors found***

P1 = 3
P1 = 7

ans = 1
In third case, all is now OK
Quote:
rekcahx@oah:~/yafu16$ ./yafu "factor(19^101+2)"


factoring 1425980859766787704425682807208175939241834849263281218168324604747928137034983072984148399494933080177249316461614210197167182021

div: primes less than 10000
pp1: doing B1 = 20K, B2 = 1M on C105, processed < 20011
Total factoring time = 0.1660 seconds


***factors found***

P1 = 3
P2 = 17
P2 = 17
P3 = 239
P4 = 1583
PRP6 = 246247
PRP5 = 13399
PRP7 = 2111167
PRP9 = 255947387
PRP97 = 2438367486231245010722152955866826161014086435374215736100356486651965462667746819431738363843627

ans = 1
rekcahx is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Running YAFU via Aliqueit doesn't find yafu.ini EdH YAFU 8 2018-03-14 17:22
YAFU-1.34 bsquared YAFU 119 2015-11-05 16:24
Yafu bug. storflyt32 YAFU 2 2015-06-29 05:19
yafu-1.33 bsquared YAFU 12 2012-11-08 04:12
yafu-1.32.1 bsquared YAFU 21 2012-09-04 19:44

All times are UTC. The time now is 21:15.

Thu Jan 21 21:15:27 UTC 2021 up 49 days, 17:26, 0 users, load averages: 2.93, 2.66, 2.43

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.