Source code

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