mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2010-09-10, 23:32   #34
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

1D4816 Posts
Default

Quote:
Originally Posted by jrk View Post
It would probably be faster to hash the LPs to look for matches rather than sort them.



The ggnfs code uses a 128-bucket hashatble (taking the least significant 8 bits of the LP for the hash) and each bucket holds up to 15 LPs.
I will try both a quicksort and a hash table......
R.D. Silverman is offline   Reply With Quote
Old 2010-09-13, 16:48   #35
FactorEyes
 
FactorEyes's Avatar
 
Oct 2006
vomit_frame_pointer

36010 Posts
Default Duplication data: 3LP vs. 2LP

I should have computed this a couple of weeks ago - moving will do that to a guy.

This was for 6^353+1 C178 GNFS. See earlier in the thread for parameters and filtering log.

I included on the relations 52M < Q < 164M, as these were the ones sieved with the 3LP approach.

Among the 2LP subset, the duplication rate was 14.6%:
Code:
Found 102240374 unique, 17440243 duplicate, and 0 bad relations.
Among all relations, the duplication rate was 18.9%:
Code:
Found 150125345 unique, 34802799 duplicate, and 0 bad relations.
One other effect of 3LP is more memory consumption at the beginning of linear algebra: 6800 MB at the first stage of building the matrix, just after filtering.

I'm running a C179 (5^418+1) as a 3LP job. I will have the duplication rates for the whole set vs. those for the 2LP subset this time. Should be available just before November 1st.
FactorEyes is offline   Reply With Quote
Old 2010-09-20, 22:11   #36
R.D. Silverman
 
R.D. Silverman's Avatar
 
"Bob Silverman"
Nov 2003
North of Boston

11101010010002 Posts
Default

Quote:
Originally Posted by R.D. Silverman View Post
I have modified my QS code to handle composites larger than 60 bits.

It was earlier asserted that the (single) LP version was worthwhile,
even for numbers of this size. I would have guessed that the overhead
associated with handling a relatively large number of partial relations
would have negated the savings, but I am going to try it. Do you have
any kind of feel for how many LP relations get collected? This is not
an idle question.


<snip>
I have added a 1-large-prime variation to my "small" QS implementation
that I use inside NFS.

Surprisingly, for 60 to 64 bit composites, the LP variation runs at
almost exactly the same speed as without the LP.

For one test value, using a factor base of 60 large primes, the LP
matrix had 54 full relations and 14 LP relations. The Non-LP
variation had 68 full relations. While the LP variation did do less
sieving, it was offset by the slightly denser matrix (14 rows were
double density), [solved by Gaussian elim) and by the slightly larger amount
of arithmetic needed for both combining the LP rows together, and
multiplying the relations in a solution set together.

I have only tried a small number of examples, but the LP variation
seems to run at about the same speed.

I have tried varying the sieve line length, varying the factor base size,
varying the LP bound. When optimally chosen, both versions of the code
run at about the same speed.
R.D. Silverman is offline   Reply With Quote
Old 2010-10-04, 20:29   #37
jrk
 
jrk's Avatar
 
May 2008

3×5×73 Posts
Default

If using 3LP on the algebraic side with the ggnfs sievers, add the -M 1 parameter to get a little more speed.

This controls which side gets mpqs treatment first. 0 for algebraic and 1 for rational, with 0 being the default. If the first side does not factor nicely, then the other side is skipped. So if you are doing 3LP on the algebraic side, trying mpqs on the rational side first will save the most work if it fails.
jrk is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Kaby Lake Memory Speed airsquirrels Hardware 12 2017-06-22 14:48
"Hybrid Memory Cube" offers 1 Tb/s memory bandwith at just 1.4 mW/Gb/s ixfd64 Hardware 4 2011-12-14 21:24
Different Speed in different OS's Dubslow Software 11 2011-08-02 00:04
Line sieving vs. lattice sieving JHansen NFSNET Discussion 9 2010-06-09 19:25
Combined Sieving speed Joe O Prime Sierpinski Project 7 2006-09-22 09:34

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


Fri Dec 2 03:47:41 UTC 2022 up 106 days, 1:16, 0 users, load averages: 0.84, 1.12, 1.15

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

≠ ± ∓ ÷ × · − √ ‰ ⊗ ⊕ ⊖ ⊘ ⊙ ≤ ≥ ≦ ≧ ≨ ≩ ≺ ≻ ≼ ≽ ⊏ ⊐ ⊑ ⊒ ² ³ °
∠ ∟ ° ≅ ~ ‖ ⟂ ⫛
≡ ≜ ≈ ∝ ∞ ≪ ≫ ⌊⌋ ⌈⌉ ∘ ∏ ∐ ∑ ∧ ∨ ∩ ∪ ⨀ ⊕ ⊗ 𝖕 𝖖 𝖗 ⊲ ⊳
∅ ∖ ∁ ↦ ↣ ∩ ∪ ⊆ ⊂ ⊄ ⊊ ⊇ ⊃ ⊅ ⊋ ⊖ ∈ ∉ ∋ ∌ ℕ ℤ ℚ ℝ ℂ ℵ ℶ ℷ ℸ 𝓟
¬ ∨ ∧ ⊕ → ← ⇒ ⇐ ⇔ ∀ ∃ ∄ ∴ ∵ ⊤ ⊥ ⊢ ⊨ ⫤ ⊣ … ⋯ ⋮ ⋰ ⋱
∫ ∬ ∭ ∮ ∯ ∰ ∇ ∆ δ ∂ ℱ ℒ ℓ
𝛢𝛼 𝛣𝛽 𝛤𝛾 𝛥𝛿 𝛦𝜀𝜖 𝛧𝜁 𝛨𝜂 𝛩𝜃𝜗 𝛪𝜄 𝛫𝜅 𝛬𝜆 𝛭𝜇 𝛮𝜈 𝛯𝜉 𝛰𝜊 𝛱𝜋 𝛲𝜌 𝛴𝜎𝜍 𝛵𝜏 𝛶𝜐 𝛷𝜙𝜑 𝛸𝜒 𝛹𝜓 𝛺𝜔