001 /*
002 * $Id: Power.java 3737 2011-08-14 19:46:26Z kredel $
003 */
004
005 package edu.jas.structure;
006
007
008 import java.util.List;
009
010 import org.apache.log4j.Logger;
011
012 import edu.jas.structure.RingElem;
013 import edu.jas.structure.RingFactory;
014 import edu.jas.structure.MonoidElem;
015 import edu.jas.structure.MonoidFactory;
016
017
018 /**
019 * Power class to compute powers of RingElem.
020 * @author Heinz Kredel
021 */
022 public class Power<C extends RingElem<C> > {
023
024 private static final Logger logger = Logger.getLogger(Power.class);
025 private static boolean debug = logger.isDebugEnabled();
026
027
028 private final RingFactory<C> fac;
029
030
031 /** The constructor creates a Power object.
032 */
033 public Power() {
034 this(null);
035 }
036
037
038 /** The constructor creates a Power object.
039 * @param fac ring factory
040 */
041 public Power(RingFactory<C> fac) {
042 this.fac = fac;
043 }
044
045
046 /** power of a to the n-th, n positive.
047 * @param a element.
048 * @param n integer exponent > 0.
049 * @return a^n.
050 */
051 public static <C extends RingElem<C>> C positivePower(C a, long n) {
052 if ( n <= 0 ) {
053 throw new IllegalArgumentException("only positive n allowed");
054 }
055 if ( a.isZERO() || a.isONE() ) {
056 return a;
057 }
058 C b = a;
059 long i = n-1;
060 C p = b;
061 do {
062 if ( i % 2 == 1 ) {
063 p = p.multiply( b );
064 }
065 i = i / 2;
066 if ( i > 0 ) {
067 b = b.multiply( b );
068 }
069 } while ( i > 0 );
070 return p;
071 }
072
073
074 /** power of a to the n-th, n positive.
075 * @param a element.
076 * @param n java.math.BigInteger exponent > 0.
077 * @return a^n.
078 */
079 public static <C extends RingElem<C>> C positivePower(C a, java.math.BigInteger n) {
080 if ( n.signum() <= 0 ) {
081 throw new IllegalArgumentException("only positive n allowed");
082 }
083 if ( a.isZERO() || a.isONE() ) {
084 return a;
085 }
086 C b = a;
087 if ( n.compareTo(java.math.BigInteger.ONE) == 0 ) {
088 return b;
089 }
090 C p = a;
091 java.math.BigInteger i = n.subtract(java.math.BigInteger.ONE);
092 do {
093 if ( i.testBit(0) ) {
094 p = p.multiply( b );
095 }
096 i = i.shiftRight(1);
097 if ( i.signum() > 0 ) {
098 b = b.multiply( b );
099 }
100 } while ( i.signum() > 0 );
101 return p;
102 }
103
104
105 /** power of a to the n-th, n positive, modulo m.
106 * @param a element.
107 * @param n integer exponent > 0.
108 * @param m modulus.
109 * @return a^n mod m.
110 */
111 public static <C extends RingElem<C>> C modPositivePower(C a, long n, C m) {
112 if ( n <= 0 ) {
113 throw new IllegalArgumentException("only positive n allowed");
114 }
115 if ( a.isZERO() || a.isONE() ) {
116 return a;
117 }
118
119 C b = a.remainder(m);
120 long i = n-1;
121 C p = b;
122 do {
123 if ( i % 2 == 1 ) {
124 p = p.multiply( b ).remainder(m);
125 }
126 i = i / 2;
127 if ( i > 0 ) {
128 b = b.multiply( b ).remainder(m);
129 }
130 } while ( i > 0 );
131 return p;
132 }
133
134
135 /**
136 * power of a to the n-th.
137 * @param a element.
138 * @param n integer exponent.
139 * @param fac ring factory.
140 * @return a^n, with 0^0 = 0 and a^{-n} = {1/a}^n.
141 */
142 @SuppressWarnings("unchecked")
143 public static <C extends RingElem<C>> C power( RingFactory<C> fac, C a, long n ) {
144 if ( a == null || a.isZERO() ) {
145 return a;
146 }
147 //return a;
148 return (C) Power.<MonoidElem>power( (MonoidFactory)fac, a, n);
149 }
150
151
152 /**
153 * power of a to the n-th.
154 * @param a element.
155 * @param n integer exponent.
156 * @param fac monoid factory.
157 * @return a^n, with a^{-n} = {1/a}^n.
158 */
159 public static <C extends MonoidElem<C>> C power( MonoidFactory<C> fac, C a, long n ) {
160 if ( n == 0 ) {
161 if ( fac == null ) {
162 throw new IllegalArgumentException("fac may not be null for a^0");
163 }
164 return fac.getONE();
165 }
166 if ( a.isONE() ) {
167 return a;
168 }
169 C b = a;
170 if ( n < 0 ) {
171 b = a.inverse();
172 n = -n;
173 }
174 if ( n == 1 ) {
175 return b;
176 }
177 C p = fac.getONE();
178 long i = n;
179 do {
180 if ( i % 2 == 1 ) {
181 p = p.multiply( b );
182 }
183 i = i / 2;
184 if ( i > 0 ) {
185 b = b.multiply( b );
186 }
187 } while ( i > 0 );
188 if ( n > 11 && debug ) {
189 logger.info("n = " + n + ", p = " + p);
190 }
191 return p;
192 }
193
194
195 /**
196 * power of a to the n-th modulo m.
197 * @param a element.
198 * @param n integer exponent.
199 * @param m modulus.
200 * @param fac monoid factory.
201 * @return a^n mod m, with a^{-n} = {1/a}^n.
202 */
203 public static <C extends MonoidElem<C>> C modPower( MonoidFactory<C> fac, C a, long n, C m) {
204 if ( n == 0 ) {
205 if ( fac == null ) {
206 throw new IllegalArgumentException("fac may not be null for a^0");
207 }
208 return fac.getONE();
209 }
210 if ( a.isONE() ) {
211 return a;
212 }
213 C b = a.remainder(m);
214 if ( n < 0 ) {
215 b = a.inverse().remainder(m);
216 n = -n;
217 }
218 if ( n == 1 ) {
219 return b;
220 }
221 C p = fac.getONE();
222 long i = n;
223 do {
224 if ( i % 2 == 1 ) {
225 p = p.multiply( b ).remainder(m);
226 }
227 i = i / 2;
228 if ( i > 0 ) {
229 b = b.multiply( b ).remainder(m);
230 }
231 } while ( i > 0 );
232 if ( n > 11 && debug ) {
233 logger.info("n = " + n + ", p = " + p);
234 }
235 return p;
236 }
237
238
239 /**
240 * power of a to the n-th modulo m.
241 * @param a element.
242 * @param n integer exponent.
243 * @param m modulus.
244 * @param fac monoid factory.
245 * @return a^n mod m, with a^{-n} = {1/a}^n.
246 */
247 public static <C extends MonoidElem<C>> C modPower( MonoidFactory<C> fac, C a,
248 java.math.BigInteger n, C m) {
249 if ( n.signum() == 0 ) {
250 if ( fac == null ) {
251 throw new IllegalArgumentException("fac may not be null for a^0");
252 }
253 return fac.getONE();
254 }
255 if ( a.isONE() ) {
256 return a;
257 }
258 C b = a.remainder(m);
259 if ( n.signum() < 0 ) {
260 b = a.inverse().remainder(m);
261 n = n.negate();
262 }
263 if ( n.compareTo(java.math.BigInteger.ONE) == 0 ) {
264 return b;
265 }
266 C p = fac.getONE();
267 java.math.BigInteger i = n;
268 do {
269 if ( i.testBit(0) ) {
270 p = p.multiply( b ).remainder(m);
271 }
272 i = i.shiftRight(1);
273 if ( i.signum() > 0 ) {
274 b = b.multiply( b ).remainder(m);
275 }
276 } while ( i.signum() > 0 );
277 if ( debug ) {
278 logger.info("n = " + n + ", p = " + p);
279 }
280 return p;
281 }
282
283
284 /** power of a to the n-th.
285 * @param a element.
286 * @param n integer exponent.
287 * @return a^n, with 0^0 = 0.
288 */
289 public C power(C a, long n) {
290 return power( fac, a, n );
291 }
292
293
294 /** power of a to the n-th mod m.
295 * @param a element.
296 * @param n integer exponent.
297 * @param m modulus.
298 * @return a^n mod m, with 0^0 = 0.
299 */
300 public C modPower(C a, long n, C m) {
301 return modPower( fac, a, n, m );
302 }
303
304
305 /** power of a to the n-th mod m.
306 * @param a element.
307 * @param n integer exponent.
308 * @param m modulus.
309 * @return a^n mod m, with 0^0 = 0.
310 */
311 public C modPower(C a, java.math.BigInteger n, C m) {
312 return modPower( fac, a, n, m );
313 }
314
315
316 /** Logarithm.
317 * @param p logarithm base.
318 * @param a element.
319 * @return k ≥ 1 minimal with p^k ≥ b.
320 */
321 public static <C extends RingElem<C>> long logarithm(C p, C a) {
322 //if ( p.compareTo(a) < 0 ) {
323 // return 0L;
324 //}
325 long k = 1L;
326 C m = p;
327 while ( m.compareTo(a) < 0 ) {
328 m = m.multiply(p);
329 k++;
330 }
331 return k;
332 }
333
334
335 /**
336 * Multiply elements in list.
337 * @param A list of elements (a_0,...,a_k).
338 * @param fac ring factory.
339 * @return prod(i=0,...k) a_i.
340 */
341 public static <C extends RingElem<C>> C multiply( RingFactory<C> fac, List<C> A) {
342 return multiply( (MonoidFactory<C>) fac, A);
343 }
344
345
346 /**
347 * Multiply elements in list.
348 * @param A list of elements (a_0,...,a_k).
349 * @param fac monoid factory.
350 * @return prod(i=0,...k) a_i.
351 */
352 public static <C extends MonoidElem<C>> C multiply( MonoidFactory<C> fac, List<C> A) {
353 if ( fac == null ) {
354 throw new IllegalArgumentException("fac may not be null for empty list");
355 }
356 C res = fac.getONE();
357 if ( A == null || A.size() == 0 ) {
358 return res;
359 }
360 for ( C a : A ) {
361 res = res.multiply(a);
362 }
363 return res;
364 }
365
366
367 /**
368 * Sum elements in list.
369 * @param A list of elements (a_0,...,a_k).
370 * @param fac ring factory.
371 * @return sum(i=0,...k) a_i.
372 */
373 public static <C extends RingElem<C>> C sum( RingFactory<C> fac, List<C> A) {
374 return sum( (AbelianGroupFactory<C>) fac, A);
375 }
376
377
378 /**
379 * Sum elements in list.
380 * @param A list of elements (a_0,...,a_k).
381 * @param fac monoid factory.
382 * @return sum(i=0,...k) a_i.
383 */
384 public static <C extends AbelianGroupElem<C>> C sum( AbelianGroupFactory<C> fac, List<C> A) {
385 if ( fac == null ) {
386 throw new IllegalArgumentException("fac may not be null for empty list");
387 }
388 C res = fac.getZERO();
389 if ( A == null || A.size() == 0 ) {
390 return res;
391 }
392 for ( C a : A ) {
393 res = res.sum(a);
394 }
395 return res;
396 }
397
398 }