[quote=bsquared;190700]
On second thought on every spawn/join/merge phase the other threads are always waiting on the slowest thread, so maybe the OS fiddles with them enough to cause significant stalling.
[/quote]
is it possible to make the threads even more separate by removing the waiting on the slowest thread?

[quote=henryzz;190704]is it possible to make the threads even more separate by removing the waiting on the slowest thread?[/quote]

probably, yes. but the ways I've thought of to do that are more complex than I wanted to really deal with for what might end up being only a small improvement.

For instance I could remove the join/merge step and let all worker threads run wild. This method would need another separate thread which gathers the relations from the free running threads into a merged cycle list and kills the workers when enough have been gathered. But now there are 5 threads utilizing cache/memory on a 4 cpu system. Can the 5th thread share resources better than the join/merge phase wastes them? I don't know. Or maybe there is no syncronization entirely and instead a heuristic which decides based on the output of one thread when we've likely accumulated enough cycles in all threads to stop, then runs post-processing to see and restarts the process if it guessed wrong. This is no better than a perl script. All these options take time to code, time which I mostly don't have. I think the route I took is good enough and don't plan to fool with it any more.

Windows Bug?
 

Hello, I downloaded the YAFU 1.11 Windows 32-bit binary from the YAFU homepage.

I am running Windows XP SP3 32-bit. I am running yafu-win32-32k.exe.

The yafu application crashes after factoring the same number twice. I can reproduce this problem using 1 thread, 2, 3, or 4 threads. My CPU is a Intel Core 2 Quad Q6600.

Note that I started yafu with no session.log, factor.log, or siqs.dat file in my directory. Also the number below was generated using rsa(225).

Here is my screen output:

C:\yafu-1.11>yafu-win32-32k.exe


09/22/09 13:36:02 v1.11 @ MYCOMP,
Initializing with Tom's Fast Math (x86-32 asm)...
cached 664581 primes. pmax = 10000079
detected cpu 6, with L1 = 32768 bytes, L2 = 4194304 bytes

======= Welcome to YAFU (Yet Another Factoring Utility) =======
======= Type help at any time, or quit to quit =======

>> factor(51025317846401360417501175108628082808603471259775615022804767179027)


factoring 51025317846401360417501175108628082808603471259775615022804767179027

div: primes less than 10000
rho: x^2 + 1, doing 1000 iterations on C68
rho: x^2 + 3, doing 1000 iterations on C68
rho: x^2 + 2, doing 1000 iterations on C68
pp1: base 391524015, doing B1 = 20K, B2 = 1M on C68, processed < 1000003
pp1: base 1940449107, doing B1 = 20K, B2 = 1M on C68, processed < 1000003
pp1: base 997619439, doing B1 = 20K, B2 = 1M on C68, processed < 1000003
pm1: base 2359630155, doing B1 = 100K, B2 = 5M on C68, processed < 5000011
ecm: curve 25, sigma = 3625693239, C68 input, B1 = 2K, B2 = 200K, processed < 199999
ecm: curve 90, sigma = 3474300460, C68 input, B1 = 11K, B2 = 1100K, processed < 1099997

starting SIQS on c68: 51025317846401360417501175108628082808603471259775615022804767179027

==== sieve params ====
n = 68 digits, 225 bits
factor base: 9755 primes (max prime = 218453)
single large prime cutoff: 14199445 (65 * pmax)
using 9 large prime slices of factor base
buckets hold 1024 elements
sieve interval: 6 blocks of size 32768
polynomial A has ~ 8 factors
using multiplier of 1
using small prime variation correction of 20 bits
using SSE2 for trial division and x64 sieve scanning
trial factoring cutoff at 78 bits

==== sieving in progress (1 thread): 9819 relations needed ====
==== Press ctrl-c to abort and save state ====
8700 rels found: 4327 full + 4373 from 44819 partial, (1381.28 rels/sec)
sieve time = 14.9535, relation time = 7.3127, poly_time = 15.3285
trial division touched 699118 sieve locations out of 1729754431488
QS elapsed time = 38.5635 seconds.

==== post processing stage (msieve-1.38) ====
begin with 53255 relations
reduce to 14349 relations in 2 passes
attempting to read 14349 relations
recovered 14349 relations
recovered 11078 polynomials
attempting to build 9845 cycles
found 9845 cycles in 1 passes
distribution of cycle lengths:
length 1 : 4681
length 2 : 5164
largest cycle: 2 relations
seed1 = 2984731976, seed2 = 1440427768
matrix is 9755 x 9845 (1.2 MB) with weight 266167 (27.04/col)
sparse part has weight 266167 (27.04/col)
filtering completed in 3 passes
matrix is 8761 x 8825 (1.0 MB) with weight 235473 (26.68/col)
sparse part has weight 235473 (26.68/col)
commencing Lanczos iteration
memory use: 1.4 MB
lanczos halted after 140 iterations (dim = 8756)
recovered 63 nontrivial dependencies
Lanczos elapsed time = 1.0940 seconds.
Sqrt elapsed time = 0.2030 seconds.
SIQS elapsed time = 39.8760 seconds.

Total factoring time = 94.1590 seconds


***factors found***

PRP34 = 1542729584432810472568652832727019
PRP35 = 33074699779716082747899089739104633

ans = 1

>> factor(51025317846401360417501175108628082808603471259775615022804767179027)


factoring 51025317846401360417501175108628082808603471259775615022804767179027

div: primes less than 10000

*** CRASH HERE *****

C:\MSieve\yafu-1.11>



I suspect it may have to do with cleanup from the SIQS part, or reading the siqs.dat file?

This is the same bug Jeff found, that I mentioned [url=http://www.mersenneforum.org/showpost.php?p=190676&postcount=231]a few posts ago[/url]. I've since found and fixed it in my development source, but I hesitate to perform another full release to get this fix out there because I felt that not many people try to factor the same number twice, back to back! If you like, I can email you a patched binary. Use my gmail account to send me your contact info if you want.

- ben.

Actually, I can repro the problem when factoring a different number the next time.

I'll try the patched binary.

[quote=timbit;190727]Actually, I can repro the problem when factoring a different number the next time.
[/quote]

You mean you factor number A completely, then try number B and it crashes? That is behaviour I haven't seen... let me know some more specifics (what numbers, for starters) and maybe I can help.

Yafu 1.11 allways crash on my Core 2 Duo T8100 with WinVista 32bit System if i try to factorize this c76 Number.
I have no idea why it only crash with this number.
It crash with 1 and 2 threads.
3675041894739039405533259197211548846143110109152323761665377505538520830273

Yep, sure 'nuff. Thanks for the report, I'll look into it.

- ben.

[quote=Andi_HB;190977]Yafu 1.11 allways crash on my Core 2 Duo T8100 with WinVista 32bit System if i try to factorize this c76 Number.
I have no idea why it only crash with this number.
It crash with 1 and 2 threads.
3675041894739039405533259197211548846143110109152323761665377505538520830273[/quote]
I'm getting the exact same thing, no matter if it's the 32k or 64k .exe. Yafu 1.11 on Athlon 64 X2 4800+ on WinXP 32-bit. Happens immediately with either siqs() or factor() (with factor() it prints "div: primes less than 10000" then crashes, with siqs() it prints nothing, or maybe a couple blank lines, and crashes). SIQS can do other basic work on the number without crashing, like trial(), adding 1 to it, or setting it to x.
Edit: Looks like ben already knows it's reproducible...oh well..

[quote=Andi_HB;190977]Yafu 1.11 allways crash on my Core 2 Duo T8100 with WinVista 32bit System if i try to factorize this c76 Number.
I have no idea why it only crash with this number.
It crash with 1 and 2 threads.
3675041894739039405533259197211548846143110109152323761665377505538520830273[/quote]

Wow, great test case! Turns out something in my arbitrary precision arithmatic was broken! A silly little oversight in right shifting, to be precise. I'm shocked this bug hasn't caused problems before now. 1.12 is almost out the door... the fix will be in there along with fixes for everything else that's been reported since 1.11 (and a few new features too...).

Thanks again!

[QUOTE=bsquared;191015]Wow, great test case! Turns out something in my arbitrary precision arithmatic was broken![/QUOTE]
Wait until you have to fix a bug in a long division routine :)