mersenneforum.org Msieve 1.41 Feedback
 Register FAQ Search Today's Posts Mark Forums Read

 2009-04-04, 05:27 #1 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 100100110111002 Posts 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 ...
 2009-04-04, 07:00 #2 Andi47     Oct 2004 Austria 2×17×73 Posts Which lower composite size limit for GNFS poly selection does v.1.41 have?
2009-04-04, 07:22   #3
10metreh

Nov 2008

2×33×43 Posts

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

 2009-04-04, 07:41 #4 Joshua2     Sep 2004 10258 Posts I looked at the code and it is 2^300. I suppose its too soon for windows x64 binaries.
2009-04-04, 14:11   #5
bsquared

"Ben"
Feb 2007

1101011011102 Posts

Quote:
 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?

2009-04-04, 14:22   #6
jasonp
Tribal Bullet

Oct 2004

67228 Posts

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

Last fiddled with by jasonp on 2009-04-04 at 14:41

 2009-04-04, 15:56 #7 Batalov     "Serge" Mar 2008 Phi(4,2^7658614+1)/2 22·7·337 Posts 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.
 2009-04-04, 16:34 #8 akruppa     "Nancy" Aug 2002 Alexandria 2,467 Posts 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
 2009-04-04, 19:07 #9 FactorEyes     Oct 2006 vomit_frame_pointer 23×32×5 Posts 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
2009-04-04, 19:23   #10
Jeff Gilchrist

Jun 2003

3×17×23 Posts

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

 2009-04-04, 19:38 #11 Joshua2     Sep 2004 13·41 Posts Yes, it will meet my needs, assumming qs is faster at 2^300, which is quite likely for now. Thanks for your work!

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

All times are UTC. The time now is 00:42.

Wed May 19 00:42:17 UTC 2021 up 40 days, 19:23, 0 users, load averages: 2.26, 2.14, 2.05