mersenneforum.org 3LP sieving: memory and speed savings!
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2010-09-10, 23:32   #34
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

1D4816 Posts

Quote:
 Originally Posted by jrk 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......

 2010-09-13, 16:48 #35 FactorEyes     Oct 2006 vomit_frame_pointer 36010 Posts 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.
2010-09-20, 22:11   #36
R.D. Silverman

"Bob Silverman"
Nov 2003
North of Boston

11101010010002 Posts

Quote:
 Originally Posted by R.D. Silverman 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.
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.

 2010-10-04, 20:29 #37 jrk     May 2008 3×5×73 Posts 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.

 Similar Threads Thread Thread Starter Forum Replies Last Post airsquirrels Hardware 12 2017-06-22 14:48 ixfd64 Hardware 4 2011-12-14 21:24 Dubslow Software 11 2011-08-02 00:04 JHansen NFSNET Discussion 9 2010-06-09 19:25 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

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.

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