Msieve 1.41 Feedback

[Batalov]

> diff ../msieve-1.40/include/mp.h include/mp.h
504,507c504,505
< if (a >= b)
< return a - b;
< else
< return a - b + p;
---
> uint32 t = a - b;
> return t += ((t >> 31) * p);

...and subsequently (64-bit linux)...

multiply complete, coefficients have about 2.64 million bits
error: relation product is incorrect
algebraic square root failed
reading relations for dependency 5
read 37937 cycles
cycles contain 140259 unique relations
read 140259 relations
multiplying 109340 relations
multiply complete, coefficients have about 2.63 million bits
error: relation product is incorrect
algebraic square root failed
...

[Andi47]

Which lower composite size limit for GNFS poly selection does v.1.41 have?

[10metreh]

Originally Posted by Andi47

Which lower composite size limit for GNFS poly selection does v.1.41 have?

It appears to be 2^300 (about 91 digits).

[Joshua2]

I looked at the code and it is 2^300. I suppose its too soon for windows x64 binaries.

[bsquared]

Originally Posted by Batalov

---
> uint32 t = a - b;
> return t += ((t >> 31) * p);

...

Arrrgh, this too can fail when the inputs are 32 bits because (a-b) can overflow past the point at which the high bit is set in t.

Looks like you need to replace with

< if (a >= b)
< return a - b;
< else
< return a - b + p;


Why is the CMOV code not running, I wonder? What system is this on?

[jasonp]

Originally Posted by bsquared

Why is the CMOV code not running, I wonder? What system is this on?

64-bit systems do not turn on the CMOV code (good thing too :)

Early in the QS days I could have sworn that gcc emitted CMOVs in 64-bit code anyway, so I didn't bother. But it apparently is pretty selective about doing so, because it does not insert CMOVs in the code emitted for mp_mod{add|sub}_1 a lot of the time.

PS: Yes, you can generate NFS polynomials for inputs as small as 300 bits. Degree 5 is definitely suboptimal at this size, and QS on 90 digit inputs takes less than 90 minutes on a fast CPU, so you'll definitely find a crossover point somewhere in that range. If we had good degree-4 polynomials (i.e. a lot better than what GGNFS polyselect finds), then perhaps with a 64-bit lattice siever you can push the crossover point lower.

[Batalov]

It was a Phenom940 with openSUSE. Of course, as soon as I switched to the 1.39 defs in the hybrid 1.40 and now in 1.41, the sqrt worked as well as always. It's ok, it's minimal.

[akruppa]

I, too, noticed that gcc often doesn't put a CMOV where I would have. But often, when I added some inline assembly to force a CMOV, I found it not to be any faster... I think short forward jumps are probably not such a great performance problem, the CPU might just cancel the instructions that got jumped over. But these jumps probably still get their entry in the branch predictor so it might not be wise to have them all over the code.

Code that should be correct and may lure gcc into issuing a CMOV might be

unsigned long submod (const unsigned long a, const unsigned long b, const unsigned long m)
{
  unsigned long t = 0, r;
  if ((r = a - b) > a)
    t = m;
  r += t;
  return r;
}

This function, compiled by itself, produces

submod:
.LFB2:
        xorl    %eax, %eax      # tmp65
        subq    %rsi, %rdi      # b, r
        cmovb   %rdx, %rax      # m,, tmp65
        addq    %rdi, %rax      # r, tmp64
        ret

which looks about right. Since everything is plain C, gcc gets some scheduling freedom when inlining, like moving the xor further ahead, or putting other stuff between the cmov and the add.

Alex

[FactorEyes]

(This is really an observation about v. 1.40, but I'll post here with the assumption that this feature is the same for 1.41. I started these 4.5 days ago, when 1.40 was the latest and greatest. )

I am 110 hours into two polynomial searches, on for a C148, and the other for a C154:

9661238722345689010630695805381314354326302931463660867557848239569163056314130303253566711209106136015278104495960724308980934671618212504467824067414937
4999528981920039977105928887012630536149642830387837444118606677005916883919115505757408444772548420175203885179819335136297859682704476680388304121

The C148 has a time limit of 156.25 hours, so with two days left to run, I have these 6 candidates:

save 1.849295e-14 -7.706762 4463134.747651 6.003133e-12
save 1.978885e-14 -7.667151 4754630.164191 6.222547e-12
save 1.853135e-14 -7.483809 4591571.198680 5.985121e-12
save 1.902571e-14 -7.444414 4827192.155067 5.996877e-12
save 1.842315e-14 -7.354144 4071249.338413 5.909207e-12
save 1.915950e-14 -7.845139 4231063.399774 6.094013e-12

These are all wonderful choices -- the alphas so are good that I'm tempted to pick one at random and start sieving -- but 6 in 4.5 days suggests the polynomial-selection parameters are tight enough to run the risk of finding nothing.

(I think of alpha < -7 as a luxury, let alone -7.7 and -7.8. Most of my gnfs polynomials have had alpha values in the -6s.)

As for the C154, it has around a week remaining, but with 4.5 days down, no candidates as yet.

After the time limit is up, I can always continue manually from where the selector timed out -- 2.5 weeks searching for a C154 does not seem excessive. Still, things look a little lean. For a C158 I did a few weeks ago, I spent 3 core-weeks trying to improve on the great polynomial that popped up after two days.

OTOH, if it always finds me a candidate with alpha below -7.5, I'll never complain.

[Jeff Gilchrist]

Originally Posted by Joshua2

I looked at the code and it is 2^300. I suppose its too soon for windows x64 binaries.

It is 2^300 you were looking for right, so the new 1.41 release will meet your needs?

I will hopefully have time to produce some Windows 64bit binaries tonight after the kids go to bed.

Jeff.

[Joshua2]

Yes, it will meet my needs, assumming qs is faster at 2^300, which is quite likely for now. Thanks for your work!