mersenneforum.org  

Go Back   mersenneforum.org > Factoring Projects > Factoring

Reply
 
Thread Tools
Old 2022-09-26, 18:36   #12
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5,101 Posts
Default

I haven't incorporated the stage1 adjustment yet to try to keep more in line with Gimarel's process. Unfortunately, my "good" GPU machine is not well and my weaker one only has two threads. So I'm currently running everything on a 24 thread CPU only machine. But it isn't multi-threading at all. With -np1 -nps top shows 100 for the Msieve process and 3.2 for the machine CPU use. Even for a 1M through 1.2M limited range, it ran for over a day until I broke in so I could work on other portions of the script.
EdH is offline   Reply With Quote
Old 2022-09-26, 19:33   #13
RichD
 
RichD's Avatar
 
Sep 2008
Kansas

2×1,879 Posts
Default

Here is a post by jasonp and the way I read it, the multi-threading is only for feeding the GPU in stage1 - but I could be wrong.
RichD is offline   Reply With Quote
Old 2022-09-27, 04:51   #14
Gimarel
 
Apr 2010

22·61 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
If I were going this route, I think I'd want to feed CADO sopt thousands of hits but not tens of thousands. The stage1 norm is still a useful filter to keep only the best GPU stage 1 hits.

The advice I gave in that linked post was intended to feed the CPU a stream of GPU hits such that size-opt on CPU took about the same time as stage 1 on GPU. You might want more hits than that, but I'd still reduce the default stage1 norm by a factor of 5 to start, and then tune as desired to balance the GPU time spent vs the CADO-sopt time spent on CPU. I personally lean toward making the GPU work "harder" by setting the stage1 norm lower.
The stage 1 of CADO has two parameters, the number of special-q and the [P,2P] interval. msieve translates the stage1_norm to something similar, a special-q range and "other". If you increase stage1_norm, the special-q range gets larger and "other" decreases.
I try to set stage1_norm so the special-q range is near 1 to 2^32 for the current leading coefficient and modify msieve to use a bigger "other".
I let CADOs sopt tune hundreds of thousands of stage 1 hits for numbers in the C20x range. This still takes less CPU wall clock time than GPU wall clock time on my system.
Gimarel is offline   Reply With Quote
Old 2022-09-27, 05:02   #15
Gimarel
 
Apr 2010

22×61 Posts
Default

Quote:
Originally Posted by EdH View Post
Thanks! I've gotten quite a ways past the single next step.
- I convert the msieve.dat.ms file into a poly file for CADO-NFS sopt.
- - I've made this portion work across varying degrees by incorporating the degree value found earlier.
- - This file is tens for thousands of polynomials.
- - - Should I use the scores to trim this yet?
I wouldn't trim the file.

Quote:
Originally Posted by EdH View Post
- I run CADO-NFS sopt on the new file.
- - You mention using exp_E to determine value.
- - - IIRC, the lower exp_E, the better (or am I backwards again?).
This is correct.

Quote:
Originally Posted by EdH View Post
- - - - Would it be of value to only keep the polynomials with the lowest exp_E?
Sure. The real question is how many ore up to what exp_E. But I can't answer this as I'm still experimenting.

Quote:
Originally Posted by EdH View Post
- - Should I make more than one pass with varying values for sopt or is there a particular value I should use?
I think that anything above -sopteffort 2 has very little effect. More than one pass is most likely a waste of time.
Gimarel is offline   Reply With Quote
Old 2022-09-27, 12:22   #16
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5,101 Posts
Default

Thanks!

I wrote a routine yesterday to cull the output from CADO-NFS sopt, based on the exp_E scores. I started with 6478 polynomials being fed to sopt, which returned its size optimized versions of all of them. I then pulled out all the lowest scoring exp_E ones and found I only had two (56.26). I added the five second lowest (56.38) and then the three third lowest (56.60). This gave me a total of ten. That's where I'm "playing" now.

From your earlier posts, I'm expecting to run these ten through Msieve's root optimizing routine, using various stage2_norm values, but what should I look for in choosing the values? I'd like to script this as well.
EdH is offline   Reply With Quote
Old 2022-09-27, 16:26   #17
chris2be8
 
chris2be8's Avatar
 
Sep 2009

45508 Posts
Default

I've managed to make msieve polyselect work quite well, but I've not used CADO at all. I hope my notes help.

For non-GPU work I just run several msieve tasks in parallel, each doing the whole job over a different range. Then I read each output file and find the poly with the highest score.

With a GPU I run:
Code:
msieve -np1 -nps -t $NP1threads -g 0 -s $PREFIX.msieve.dat ...
sort -g -u -k $sortkey $PREFIX.msieve.dat.ms | head -200 >$PREFIX.msieve.dat.ms.cut
split -nr/$NUM_THREADS $PREFIX.msieve.dat.ms.cut $PREFIX.msieve.dat.ms # Creates $PREFIX.msieve.dat.msaa, $PREFIX.msieve.dat.msab, ...
Then run 1 msieve -npr task against each $PREFIX.msieve.dat.msa*
And finally search output from -npr to find the best poly.

If I understand this thread correctly then you are planning to run CADO sopt against the $PREFIX.msieve.dat.ms file, then run the output from than through msieve -npr. So that would be just another step between msieve -np1 -nps and sort. Or possibly after sort to limit how many records you pass to CADO sopt.

Am I correct? And would splitting the file to pass to several CADO sopt tasks be useful?

Although getting it to work single threaded would be a good start before multi-threading it (BTDTGTTS).
chris2be8 is offline   Reply With Quote
Old 2022-09-27, 16:46   #18
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5,101 Posts
Default

Some good points to consider. Yes, I plan to follow the process of generating polynomials via Msieve, modifying them via Msieve, further converting them to sopt readable, running sopt and then finally, Msieve ropt. Part of this was already implemented in my spin script elsewhere, but Gimarel's rarely if ever, spun effectively. I'm hoping for a script that can be somewhat generic and produce polys that are the best they can be. Creating a script with multiple threads may be a good addition. I will consider that as I progress. Thanks.
EdH is offline   Reply With Quote
Old 2022-09-27, 20:22   #19
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

555210 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
If I understand this thread correctly then you are planning to run CADO sopt against the $PREFIX.msieve.dat.ms file, then run the output from than through msieve -npr. So that would be just another step between msieve -np1 -nps and sort. Or possibly after sort to limit how many records you pass to CADO sopt.

Am I correct? And would splitting the file to pass to several CADO sopt tasks be useful?

Although getting it to work single threaded would be a good start before multi-threading it (BTDTGTTS).
I believe Ed's plan is to use cado sopt *instead* of msieve -nps. That is, run -np1, take that output and convert to CADO format, sopt, then back to msieve for -npr.
VBCurtis is offline   Reply With Quote
Old 2022-09-27, 20:33   #20
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5,101 Posts
Default

I believed I would be running -np1 only, but msieve.dat.m does not include enough info for me to convert to the polynomials needed to supply sopt. Therefore, -nps is currently necessary for that task, but with a high enough stage2_norm to prevent losing polynomials. I hope to eventually know enough to remove the -nps stage altogether.
EdH is offline   Reply With Quote
Old 2022-09-28, 04:54   #21
Gimarel
 
Apr 2010

111101002 Posts
Default

Quote:
Originally Posted by EdH View Post
From your earlier posts, I'm expecting to run these ten through Msieve's root optimizing routine, using various stage2_norm values, but what should I look for in choosing the values? I'd like to script this as well.
I use a starting value relative to the msieve computed stage2_norm of the poly. To do this I modified msieve .
I don't know how to do this without a modified msieve in an efficiant way. My modification to msieve:
Code:
Index: gnfs/poly/stage2/stage2.c
===================================================================
--- gnfs/poly/stage2/stage2.c    (Revision 1035)
+++ gnfs/poly/stage2/stage2.c    (Arbeitskopie)
@@ -298,6 +298,7 @@
     curr_poly_t *c = &s->curr_poly;
     dd_precision_t precision = 0;
     uint32 precision_changed = 0;
+    double max_sizeopt_norm_backup = data->max_sizeopt_norm;
 
     if (!dd_precision_is_ieee()) {
         precision_changed = 1;
@@ -329,7 +330,14 @@
     }
 
     if (sizeopt_norm * exp(projective_alpha) <= data->max_sizeopt_norm)
-        root_sieve_run(data, sizeopt_norm, projective_alpha);
+    {
+        data->max_sizeopt_norm = sizeopt_norm * exp(projective_alpha) * 1.5;
+        for (i = 0; i < 5; i++, data->max_sizeopt_norm *= 1.5)
+        {
+            root_sieve_run(data, sizeopt_norm, projective_alpha);
+        }
+        data->max_sizeopt_norm = max_sizeopt_norm_backup;
+    }
 
 finished:
     if (precision_changed)
Additionally I run msieve again on the best polys after rootsieve with a constant 1.0327 for 100 times.
Gimarel is offline   Reply With Quote
Old 2022-09-28, 12:07   #22
EdH
 
EdH's Avatar
 
"Ed Hall"
Dec 2009
Adirondack Mtns

5,101 Posts
Default

I already do a short run of Msieve -np1, terminate it, and read the degree (for the later conversion) and stage2_norm . I can modify it as I wish and make the multiple runs.
EdH is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Calculator that can factor and find exact roots of polynomials alpertron Programming 39 2022-06-02 12:21
Improving Polynomials With CADO-NFS and Msieve Tools EdH Factoring 4 2021-10-18 14:29
Combining Msieve with CADO NFS mfeltz Msieve 10 2016-03-16 21:12
How to find values of polynomials with nice factorization? Drdmitry Computer Science & Computational Number Theory 18 2015-09-10 12:23
how to run msieve or cado-nfs on mpi-cluster? ravlyuchenko Msieve 1 2011-08-16 12:12

All times are UTC. The time now is 12:54.


Sun Dec 4 12:54:09 UTC 2022 up 108 days, 10:22, 0 users, load averages: 0.87, 1.02, 1.08

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.

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