Yafu

[bsquared]

There should be a fix for this in 1.17e - can you try that version?

[detailed_section]
I am using the strtok function to parse out tokens after rearranging them into postfix notation. The delimiter was a ' ' (space), but wasn't null terminated. Making the delimiter a null terminated space fixed this problem in at least one other test case, so hopefully the fix works for you as well.
[/detailed_section]

[rekcahx]

Yeah, this seems to be fixed in 1.17. Thanks.

Edit:
Btw, precompiled 64k-linux64 benchmarks (factored number was 19^100+2 and processor is Phenom 9950):

SIQS elapsed time = 1311.0710 seconds.
Total factoring time = 1806.2232 seconds

[bsquared]

Thanks rekcahx, and everyone else that supplied benchmarks. It seems the adaptive cutoff code is working good; on rare occasions tests ran slightly slower (by 1 or 2%), but much more often it gives an improvement (over 10% in some cases).

1.17 will be out soon.

[bsquared]

... in the usual place

The adaptive cutoff output (optfile.csv) is available as a compile time option. If anyone sees any funny behavior, let me know. Otherwise, happy factoring!

- ben.

[VolMike]

Originally Posted by bsquared

... in the usual place

The adaptive cutoff output (optfile.csv) is available as a compile time option. If anyone sees any funny behavior, let me know. Otherwise, happy factoring!

- ben.

There is an exception occurs while typing some unexpected input data i.e.

sieve(1234)

at win32 vc.9 build yafu.

Some of other incorrectness evaluated correctly:

unrecognized token:...

[bsquared]

Thanks VolMike, I've fixed that in my development source. The fix will appear in the next release.

I've also updated the webpage with a 1.17 package that includes 64 bit windows binaries. If you need pre-compiled 64 bit windows binaries then re-download the 1.17 zip file. Thanks to Jeff Gilchrist for providing them.

As a sneak peak: Version 1.18 changes the implementation of threading in SIQS to use a threadpool environment instead of spawn and join. This appears to be much more efficient on Nehalem architectures. I noticed in benchmarks of a nehalem based xeon system that smaller inputs were unexpectedly very slow. I traced this back to the introduction of threading in YAFU. The spawn and join threading I am using in 1.17 (and below) must not play nicely with Nehalems somehow; the threadpool fixes this. 1.18 should be released soon.

- ben.

[bsquared]

... in the usual place.

New in version 1.18
+ more efficient threading in SIQS using a threadpool. this also fixes some slowdown issues I was seeing on Intel Nehalem chips. Thanks again to jasonp and msieve for providing an example threadpool implementation.
+ fixed bug reported by VolMike where an incorrect number of arguments to a function caused a crash.
+ much more advanced sieve of Eratosthenes. Faster, threaded, and capable of finding/counting primes in arbitrary intervals up to around 1e14.

I took a diversion in the sieve of Eratosthenes implementation for this latest version. I have measured it to be the fastest such available*, beating out ecprime and primegen.

- ben.

*Caveat: only on modern 64 bit processors, and only for large intervals (greater than a few billion or so).

[jasonp]

You're welcome. I now know that the thread pool code can be better; if you want a thread pool interface that uses less locking, I'm rather fond of Emmanuel Thome's code here in worker_threads.[ch], although you'd have to provide windows equivalents to some of the pthreads calls.

[bsquared]

Originally Posted by jasonp

You're welcome. I now know that the thread pool code can better; you want a thread pool interface that uses less locking, I'm rather fond Emmanuel Thome's code here worker_threads.[ch], although you'd have provide windows equivalents some the pthreads calls.

Thanks for the reference, I'll check that out.

Also, other news, I updated the 1.18 package the website include win64 binaries. I'm now able produce these myself, thanks the beta 2 release visual studio 2010. I think they are up a RC version now, and are past beta, but the beta 2 versions seems work ok.

[Batalov]

I have multiple cases where yafu (both v.1.17 and 1.18) hangs on 42-digit composites. Is it an Easter egg? (you know that 42 is the Ultimate Answer to Everything)

Here are a few collected debug cases (all c42s!!):

917947111981150361998314676252219465199479
732566077883908909845195639793682175206731
446329425249256901981632476072664593912499

(This is on 64-bit Linux, the zipped binary yafu-64k-linux64, on a AMD k8/fam10.)
They start dumping lines:
...
rejecting duplicate poly_a, new target = 15576
rejecting duplicate poly_a, new target = 15577
rejecting duplicate poly_a, new target = 15578
rejecting duplicate poly_a, new target = 15579
rejecting duplicate poly_a, new target = 15580
...
___
P.S. I get them in the downdriver runs. Unfortunately, after unclogging a stuck process by msieve/qs, they all soon hit a driver.

[bsquared]

Originally Posted by Batalov

I have multiple cases where yafu (both v.1.17 and 1.18) hangs on 42-digit composites. Is it an Easter egg? (you know that 42 is the Ultimate Answer to Everything)

Who knew that the ultimate question to the ultimate answer was "what size composite integer places excessive stress on yafu's hack of a random number generator?"? Only for 64 bit systems is this a problem, where I put some garbage together to try to extend rand() to produce a 64 bit random number rather than the 16 bit default.

I guess its good news that bugs only seem to be popping up in increasingly obscure places of the code.

Patched binaries for linux will be on my website soon (1.18.1). These also contain a minor fix in factor() which handles overflow conditions in the number of estimated ECM curves for large inputs (brought to my attention by several people, most recently by Dennis P.)