1 #include "cado.h" // IWYU pragma: keep
2 #include <algorithm> // for max
3 #include <cmath> // for isfinite, INFINITY
4 #include <memory> // for allocator_traits<>::value_type
5 #include <utility> // for pair, make_pair
6 #include <vector> // for vector
7 #include <cstdio> // IWYU pragma: keep
8 #include <cstdarg> // IWYU pragma: keep
9 #include <gmp.h> // for mpz_srcptr, gmp_vfprintf, mpz_sizei...
10 #include "cxx_mpz.hpp"
11 #include "las-descent.hpp"
12 #include "las-descent-trees.hpp" // for descent_tree::candidate_relation
13 #include "las-dlog-base.hpp" // for las_dlog_base
14 #include "las-globals.hpp" // for general_grace_time_ratio, recursive...
15 #include "las-report-stats.hpp" // for TIMER_CATEGORY
16 #include "las-siever-config.hpp" // for siever_config_pool, siever_config_p...
17 #include "las-todo-entry.hpp" // for las_todo_entry
18 #include "las-todo-list.hpp" // for las_todo_list
19 #include "relation.hpp" // for relation::pr, relation
20 #include "typedefs.h" // p_r_values_t
21 #include "verbose.h"
22
23 /* This returns true only if this descent node is now done, either based
24 * on the new relation we have registered, or because the previous
25 * relation is better anyway */
register_contending_relation(las_info const & las,las_todo_entry const & doing,relation & rel)26 bool register_contending_relation(las_info const & las, las_todo_entry const & doing, relation & rel)/*{{{*/
27 {
28 if (las.tree.must_avoid(rel)) {
29 verbose_output_vfprint(0, 1, gmp_vfprintf, "# [descent] Warning: we have already used this relation, avoiding\n");
30 return true;
31 }
32
33 /* compute rho for all primes, even on the rational side */
34 rel.fixup_r(true);
35
36 descent_tree::candidate_relation contender;
37 contender.rel = rel;
38 double time_left = 0;
39
40 for(int side = 0 ; side < 2 ; side++) {
41 for(unsigned int i = 0 ; i < rel.sides[side].size() ; i++) {
42 relation::pr const & v(rel.sides[side][i]);
43 if (mpz_cmp(doing.p, v.p) == 0)
44 continue;
45 p_r_values_t p = mpz_get_ui(v.p);
46 if (mpz_fits_ulong_p(v.p)) {
47 p_r_values_t r = mpz_get_ui(v.r);
48 if (las.dlog_base.is_known(side, p, r))
49 continue;
50 }
51
52 unsigned int n = mpz_sizeinbase(v.p, 2);
53 siever_config_pool::key_type K(side, n);
54 double e = las.config_pool.hint_expected_time(K);
55 if (e < 0) {
56 /* This is not worrysome per se. We just do
57 * not have the info in the descent hint table,
58 * period.
59 */
60 verbose_output_vfprint(0, 1, gmp_vfprintf, "# [descent] Warning: cannot estimate refactoring time for relation involving %d@%d (%Zd,%Zd)\n", n, side, (mpz_srcptr) v.p, (mpz_srcptr) v.r);
61 time_left = INFINITY;
62 } else {
63 if (std::isfinite(time_left))
64 time_left += e;
65 }
66 contender.outstanding.push_back(std::make_pair(side, v));
67 }
68 }
69 verbose_output_print(0, 1, "# [descent] This relation entails an additional time of %.2f for the smoothing process (%zu children)\n",
70 time_left, contender.outstanding.size());
71
72 /* when we're re-examining this special-q because of a previous
73 * failure, there's absolutely no reason to hurry up on a relation */
74 contender.set_time_left(time_left, doing.iteration ? INFINITY : general_grace_time_ratio);
75
76 return las.tree.new_candidate_relation(contender);
77 }/*}}}*/
78
postprocess_specialq_descent(las_info & las,las_todo_list & todo,las_todo_entry const & doing,timetree_t & timer_special_q)79 void postprocess_specialq_descent(las_info & las, las_todo_list & todo, las_todo_entry const & doing, timetree_t & timer_special_q)/*{{{*/
80 {
81 SIBLING_TIMER(timer_special_q, "descent");
82 TIMER_CATEGORY(timer_special_q, bookkeeping());
83
84 descent_tree::candidate_relation const & winner(las.tree.current_best_candidate());
85 if (winner) {
86 /* Even if not going for recursion, store this as being a
87 * winning relation. This is useful for preparing the hint
88 * file, and also for the initialization of the descent.
89 */
90 las.tree.take_decision();
91 verbose_output_start_batch();
92 FILE * output;
93 for (size_t i = 0;
94 (output = verbose_output_get(0, 0, i)) != NULL;
95 i++) {
96 winner.rel.print(output, "Taken: ");
97 }
98 verbose_output_end_batch();
99 {
100 unsigned int n = mpz_sizeinbase(doing.p, 2);
101 verbose_output_start_batch();
102 verbose_output_print (0, 1, "# taking path: ");
103 for(int i = 0 ; i < doing.depth ; i++) {
104 verbose_output_print (0, 1, " ");
105 }
106 verbose_output_print (0, 1, "%d@%d ->", n, doing.side);
107 for(unsigned int i = 0 ; i < winner.outstanding.size() ; i++) {
108 int side = winner.outstanding[i].first;
109 relation::pr const & v(winner.outstanding[i].second);
110 unsigned int n = mpz_sizeinbase(v.p, 2);
111 verbose_output_print (0, 1, " %d@%d", n, side);
112 }
113 if (winner.outstanding.empty()) {
114 verbose_output_print (0, 1, " done");
115 }
116 verbose_output_vfprint (0, 1, gmp_vfprintf, " \t%d %Zd %Zd\n", doing.side,
117 (mpz_srcptr) doing.p,
118 (mpz_srcptr) doing.r);
119 verbose_output_end_batch();
120 }
121 if (recursive_descent) {
122 /* reschedule the possibly still missing large primes in the
123 * todo list */
124 for(unsigned int i = 0 ; i < winner.outstanding.size() ; i++) {
125 int side = winner.outstanding[i].first;
126 relation::pr const & v(winner.outstanding[i].second);
127 unsigned int n = mpz_sizeinbase(v.p, 2);
128 verbose_output_vfprint(0, 1, gmp_vfprintf, "# [descent] " HILIGHT_START "pushing side-%d (%Zd,%Zd) [%d@%d]" HILIGHT_END " to todo list (now size %zu)\n", side, (mpz_srcptr) v.p, (mpz_srcptr) v.r, n, side, todo.size() + 1);
129 todo.push_withdepth(v.p, v.r, side, doing.depth + 1);
130 }
131 }
132 } else {
133 las.tree.mark_try_again(doing.iteration + 1);
134 unsigned int n = mpz_sizeinbase(doing.p, 2);
135 verbose_output_print (0, 1, "# taking path: %d@%d -> loop (#%d)", n, doing.side, doing.iteration + 1);
136 verbose_output_vfprint (0, 1, gmp_vfprintf, " \t%d %Zd %Zd\n", doing.side,
137 (mpz_srcptr) doing.p,
138 (mpz_srcptr) doing.r);
139 verbose_output_vfprint(0, 1, gmp_vfprintf, "# [descent] Failed to find a relation for " HILIGHT_START "side-%d (%Zd,%Zd) [%d@%d]" HILIGHT_END " (iteration %d). Putting back to todo list.\n", doing.side,
140 (mpz_srcptr) doing.p,
141 (mpz_srcptr) doing.r, n, doing.side, doing.iteration);
142 todo.push_withdepth(doing.p, doing.r, doing.side, doing.depth + 1, doing.iteration + 1);
143 }
144 }/*}}}*/
145