Yafu

[EdH]

Originally Posted by bsquared

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

[bsquared]

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]

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.

[bsquared]

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.

[Andi_HB]

Originally Posted by bsquared

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

[jasonp]

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 :)

[bsquared]

Originally Posted by jasonp

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.

Originally Posted by jasonp

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]

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.

[Batalov]

Originally Posted by bsquared

+ 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

[bsquared]

Originally Posted by Batalov

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.

[rekcahx]

I think that there is a problem in parser.

In first case, all went OK

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:

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

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