1 //==============================================================================================
2 //
3 // This file is part of LiDIA --- a library for computational number theory
4 //
5 // Copyright (c) 1994--2001 the LiDIA Group. All rights reserved.
6 //
7 // See http://www.informatik.tu-darmstadt.de/TI/LiDIA/
8 //
9 //----------------------------------------------------------------------------------------------
10 //
11 // $Id$
12 //
13 // Author : Victor Shoup (VS), Thomas Pfahler (TPf)
14 // Changes : See CVS log
15 //
16 //==============================================================================================
17
18
19 #ifdef HAVE_CONFIG_H
20 # include "config.h"
21 #endif
22 #include "LiDIA/finite_fields/Fp_polynomial_util.h"
23 #include "LiDIA/udigit.h"
24
25
26
27 #ifdef LIDIA_NAMESPACE
28 namespace LiDIA {
29 #endif
30
31
32
next_power_of_two(lidia_size_t m)33 lidia_size_t next_power_of_two(lidia_size_t m)
34 {
35 debug_handler("tools.c", "next_power_of_two (lidia_size_t)");
36 lidia_size_t k, n;
37 n = 1;
38 k = 0;
39 while (n < m) {
40 n = n << 1;
41 k++;
42 }
43 return k;
44 }
45
46
47
square_root(lidia_size_t n)48 lidia_size_t square_root(lidia_size_t n)
49 {
50 debug_handler("tools.c", "square_root (lidia_size_t)");
51 if (n <= 0)
52 return 0;
53 else if (n == 1)
54 return 1;
55 else
56 return static_cast<lidia_size_t>(std::sqrt(static_cast<double>(n)));
57 }
58
59
60
61 //*************************************************************************
62 // my_timer
63 //*************************************************************************
64
my_timer()65 my_timer::my_timer() :
66 msg(0)
67 {
68 debug_handler("my_timer", "my_timer()");
69 t.set_print_mode(HMS_MODE);
70 }
71
72
73
~my_timer()74 my_timer::~my_timer()
75 {
76 debug_handler("my_timer", "~my_timer()");
77 delete[] msg;
78 }
79
80
81
start(const char * message)82 void my_timer::start(const char* message)
83 {
84 debug_handler("my_timer", "start(char*)");
85 delete[] msg;
86 msg = new char[strlen(message)+1];
87 memory_handler(msg, "my_timer",
88 "start(char*)::Error in memory allocation");
89 strcpy(msg, message);
90 t.start_timer();
91 }
92
93
94
stop()95 void my_timer::stop()
96 {
97 debug_handler("my_timer", "stop()");
98 if (msg == 0)
99 return;
100 t.stop_timer();
101 std::cerr << msg << " ";
102 t.print(std::cerr);
103 std::cerr << std::endl;
104 delete[] msg;
105 msg = 0;
106 }
107
108
109
110 //*************************************************************************
111 // int_factor/fac_vec
112 //*************************************************************************
113
114
swap(int_factor & i1,int_factor & i2)115 void swap(int_factor& i1, int_factor& i2)
116 {
117 debug_handler("int_factor", "swap (int_factor&, int_factor&)");
118
119 lidia_size_t t_lidia_size_t;
120 int t_int;
121 double t_double;
122
123 t_lidia_size_t = i1.q;
124 i1.q = i2.q;
125 i2.q = t_lidia_size_t;
126
127 t_int = i1.a;
128 i1.a = i2.a;
129 i2.a = t_int;
130
131 t_int = i1.b;
132 i1.b = i2.b;
133 i2.b = t_int;
134
135 t_double = i1.len;
136 i1.len = i2.len;
137 i2.len = t_double;
138 }
139
140
141
fac_vec(lidia_size_t n)142 fac_vec::fac_vec(lidia_size_t n) :
143 fvec(0),
144 num_factors(0)
145 {
146 debug_handler("fac_vec", "fac_vec(lidia_size_t)");
147
148 compute_factorization(n);
149 }
150
151
152
compute_factorization(lidia_size_t n)153 void fac_vec::compute_factorization(lidia_size_t n)
154 {
155 debug_handler("fac_vec", "compute_factorization (lidia_size_t)");
156 lidia_size_t q;
157
158 delete[] fvec;
159 lidia_size_t m = next_power_of_two(n);
160 fvec = new int_factor[m];
161 memory_handler(fvec, "fac_vec", "compute_factorization(lidia_size_t)::"
162 "Error in memory allocation");
163
164 num_factors = 0;
165 q = 2;
166
167 // compute factorization of n
168 while (n != 1) {
169 if (n%q == 0) {
170 fvec[num_factors].q = q;
171 n = n/q;
172 fvec[num_factors].a = 1;
173 while (n%q == 0) {
174 n = n/q;
175 (fvec[num_factors].a)++;
176 }
177
178 num_factors++;
179 }
180
181 q++;
182 }
183
184 // set 'len'
185 lidia_size_t i;
186 for (i = 0; i < num_factors; i++)
187 fvec[i].len = fvec[i].a * std::log(static_cast<double>(fvec[i].q));
188
189 sort();
190 }
191
192
193
sort()194 void fac_vec::sort()
195 {
196 debug_handler("fac_vec", "sort (void)");
197 int i, j;
198
199 for (i = 1; i <= num_factors - 1; i++)
200 for (j = 0; j <= num_factors - i - 1; j++)
201 if (fvec[j].len > fvec[j+1].len)
202 swap(fvec[j], fvec[j+1]);
203 }
204
205
206
clear(int lo,int hi)207 void fac_vec::clear(int lo, int hi)
208 {
209 debug_handler("fac_vec", "assign_zero_to_b(int, int)");
210 int i;
211 for (i = lo; i <= hi; i++)
212 fvec[i].b = 0;
213 }
214
215
216
prod(int lo,int hi) const217 lidia_size_t fac_vec::prod(int lo, int hi) const
218 {
219 debug_handler("fac_vec", "prod(int, int)");
220
221 lidia_size_t i, res;
222
223 res = 1;
224 for (i = lo; i <= hi; i++)
225 res = res * power(static_cast<unsigned int>(fvec[i].q), static_cast<unsigned int>(fvec[i].a));
226
227 return res;
228 }
229
230
231
232 #ifdef LIDIA_NAMESPACE
233 } // end of namespace LiDIA
234 #endif
235