mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Msieve

Reply
 
Thread Tools
Old 2009-04-04, 05:27   #1
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

2·33·132 Posts
Default Msieve 1.41 Feedback

> 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
...
Batalov is offline   Reply With Quote
Old 2009-04-04, 07:00   #2
Andi47
 
Andi47's Avatar
 
Oct 2004
Austria

2·17·73 Posts
Default

Which lower composite size limit for GNFS poly selection does v.1.41 have?
Andi47 is offline   Reply With Quote
Old 2009-04-04, 07:22   #3
10metreh
 
10metreh's Avatar
 
Nov 2008

2·33·43 Posts
Default

Quote:
Originally Posted by Andi47 View Post
Which lower composite size limit for GNFS poly selection does v.1.41 have?
It appears to be 2^300 (about 91 digits).
10metreh is offline   Reply With Quote
Old 2009-04-04, 07:41   #4
Joshua2
 
Joshua2's Avatar
 
Sep 2004

21516 Posts
Default

I looked at the code and it is 2^300. I suppose its too soon for windows x64 binaries.
Joshua2 is offline   Reply With Quote
Old 2009-04-04, 14:11   #5
bsquared
 
bsquared's Avatar
 
"Ben"
Feb 2007

2·5·7·47 Posts
Default

Quote:
Originally Posted by Batalov View Post
---
> 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?
bsquared is offline   Reply With Quote
Old 2009-04-04, 14:22   #6
jasonp
Tribal Bullet
 
jasonp's Avatar
 
Oct 2004

3,529 Posts
Default

Quote:
Originally Posted by bsquared View Post
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.

Last fiddled with by jasonp on 2009-04-04 at 14:41
jasonp is offline   Reply With Quote
Old 2009-04-04, 15:56   #7
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

100011101001102 Posts
Default

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.
Batalov is offline   Reply With Quote
Old 2009-04-04, 16:34   #8
akruppa
 
akruppa's Avatar
 
"Nancy"
Aug 2002
Alexandria

2,467 Posts
Default

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

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

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

Last fiddled with by akruppa on 2009-04-04 at 16:40
akruppa is offline   Reply With Quote
Old 2009-04-04, 19:07   #9
FactorEyes
 
FactorEyes's Avatar
 
Oct 2006
vomit_frame_pointer

23×32×5 Posts
Default Polynomial search selectivity

(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:
Code:
9661238722345689010630695805381314354326302931463660867557848239569163056314130303253566711209106136015278104495960724308980934671618212504467824067414937
4999528981920039977105928887012630536149642830387837444118606677005916883919115505757408444772548420175203885179819335136297859682704476680388304121
The C148 has a time limit of 156.25 hours, so with two days left to run, I have these 6 candidates:

Code:
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.

Last fiddled with by FactorEyes on 2009-04-04 at 19:22
FactorEyes is offline   Reply With Quote
Old 2009-04-04, 19:23   #10
Jeff Gilchrist
 
Jeff Gilchrist's Avatar
 
Jun 2003
Ottawa, Canada

7·167 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
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.
Jeff Gilchrist is offline   Reply With Quote
Old 2009-04-04, 19:38   #11
Joshua2
 
Joshua2's Avatar
 
Sep 2004

53310 Posts
Default

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

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Msieve 1.53 feedback xilman Msieve 149 2018-11-12 06:37
Msieve 1.50 feedback firejuggler Msieve 99 2013-02-17 11:53
Msieve v1.48 feedback Jeff Gilchrist Msieve 48 2011-06-10 18:18
Msieve 1.43 feedback Jeff Gilchrist Msieve 47 2009-11-24 15:53
Msieve 1.42 feedback Andi47 Msieve 167 2009-10-18 19:37

All times are UTC. The time now is 03:17.

Mon Sep 28 03:17:52 UTC 2020 up 18 days, 28 mins, 0 users, load averages: 1.33, 1.36, 1.43

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, 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.