Source code

001/*
002 * $Id: Power.java 5872 2018-07-20 16:01:46Z kredel $
003 */
004
005package edu.jas.structure;
006
007
008import java.util.List;
009
010import org.apache.logging.log4j.Logger;
011import org.apache.logging.log4j.LogManager; 
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 > 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 > 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 > 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.
145     * @param a element.
146     * @param n integer exponent.
147     * @param fac ring factory.
148     * @return a^n, with 0^0 = 0 and a^{-n} = {1/a}^n.
149     */
150    @SuppressWarnings("unchecked")
151    public static <C extends RingElem<C>> C power(RingFactory<C> fac, C a, long n) {
152        if (a == null || a.isZERO()) {
153            return a;
154        }
155        //return a;
156        return (C) Power.<MonoidElem> power((MonoidFactory) fac, a, n);
157    }
158
159
160    /**
161     * power of a to the n-th.
162     * @param a element.
163     * @param n integer exponent.
164     * @param fac monoid factory.
165     * @return a^n, with a^{-n} = {1/a}^n.
166     */
167    public static <C extends MonoidElem<C>> C power(MonoidFactory<C> fac, C a, long n) {
168        if (n == 0) {
169            if (fac == null) {
170                throw new IllegalArgumentException("fac may not be null for a^0");
171            }
172            return fac.getONE();
173        }
174        if (a.isONE()) {
175            return a;
176        }
177        C b = a;
178        if (n < 0) {
179            b = a.inverse();
180            n = -n;
181        }
182        if (n == 1) {
183            return b;
184        }
185        C p = fac.getONE();
186        long i = n;
187        do {
188            if (i % 2 == 1) {
189                p = p.multiply(b);
190            }
191            i = i / 2;
192            if (i > 0) {
193                b = b.multiply(b);
194            }
195        } while (i > 0);
196        if (n > 11 && debug) {
197            logger.info("n  = " + n + ", p  = " + p);
198        }
199        return p;
200    }
201
202
203    /**
204     * power of a to the n-th modulo m.
205     * @param a element.
206     * @param n integer exponent.
207     * @param m modulus.
208     * @param fac monoid factory.
209     * @return a^n mod m, with a^{-n} = {1/a}^n.
210     */
211    public static <C extends MonoidElem<C>> C modPower(MonoidFactory<C> fac, C a, long n, C m) {
212        if (n == 0) {
213            if (fac == null) {
214                throw new IllegalArgumentException("fac may not be null for a^0");
215            }
216            return fac.getONE();
217        }
218        if (a.isONE()) {
219            return a;
220        }
221        C b = a.remainder(m);
222        if (n < 0) {
223            b = a.inverse().remainder(m);
224            n = -n;
225        }
226        if (n == 1) {
227            return b;
228        }
229        C p = fac.getONE();
230        long i = n;
231        do {
232            if (i % 2 == 1) {
233                p = p.multiply(b).remainder(m);
234            }
235            i = i / 2;
236            if (i > 0) {
237                b = b.multiply(b).remainder(m);
238            }
239        } while (i > 0);
240        if (n > 11 && debug) {
241            logger.info("n  = " + n + ", p  = " + p);
242        }
243        return p;
244    }
245
246
247    /**
248     * power of a to the n-th modulo m.
249     * @param a element.
250     * @param n integer exponent.
251     * @param m modulus.
252     * @param fac monoid factory.
253     * @return a^n mod m, with a^{-n} = {1/a}^n.
254     */
255    public static <C extends MonoidElem<C>> C modPower(MonoidFactory<C> fac, C a, java.math.BigInteger n, C m) {
256        if (n.signum() == 0) {
257            if (fac == null) {
258                throw new IllegalArgumentException("fac may not be null for a^0");
259            }
260            return fac.getONE();
261        }
262        if (a.isONE()) {
263            return a;
264        }
265        C b = a.remainder(m);
266        if (n.signum() < 0) {
267            b = a.inverse().remainder(m);
268            n = n.negate();
269        }
270        if (n.compareTo(java.math.BigInteger.ONE) == 0) {
271            return b;
272        }
273        if (n.bitLength() <= 63) {
274            long l = n.longValue();
275            return modPower(fac, a, l, m);
276        }
277        C p = fac.getONE();
278        java.math.BigInteger i = n;
279        do {
280            if (i.testBit(0)) {
281                p = p.multiply(b).remainder(m);
282            }
283            i = i.shiftRight(1);
284            if (i.signum() > 0) {
285                b = b.multiply(b).remainder(m);
286            }
287        } while (i.signum() > 0);
288        if (debug) {
289            logger.info("n  = " + n + ", p  = " + p);
290        }
291        return p;
292    }
293
294
295    /**
296     * power of a to the n-th.
297     * @param a element.
298     * @param n integer exponent.
299     * @return a^n, with 0^0 = 0.
300     */
301    public C power(C a, long n) {
302        return power(fac, a, n);
303    }
304
305
306    /**
307     * power of a to the n-th.
308     * @param a long.
309     * @param n integer exponent.
310     * @return a^n, with a^0 = 1.
311     */
312    public static long power(long a, long n) {
313        if (n == 0) {
314            return 1L;
315        }
316        if (a == 1L) {
317            return a;
318        }
319        long b = a;
320        if (n == 1L) {
321            return b;
322        }
323        long p = 1L;
324        long i = n;
325        do {
326            if (i % 2 == 1) {
327                p = p * b;
328            }
329            i = i / 2;
330            if (i > 0) {
331                b = b * b;
332            }
333        } while (i > 0);
334        if (n > 11 && debug) {
335            logger.info("n  = " + n + ", p  = " + p);
336        }
337        return p;
338    }
339
340
341    /**
342     * power of a to the n-th mod m.
343     * @param a element.
344     * @param n integer exponent.
345     * @param m modulus.
346     * @return a^n mod m, with 0^0 = 0.
347     */
348    public C modPower(C a, long n, C m) {
349        return modPower(fac, a, n, m);
350    }
351
352
353    /**
354     * power of a to the n-th mod m.
355     * @param a element.
356     * @param n integer exponent.
357     * @param m modulus.
358     * @return a^n mod m, with 0^0 = 0.
359     */
360    public C modPower(C a, java.math.BigInteger n, C m) {
361        return modPower(fac, a, n, m);
362    }
363
364
365    /**
366     * Logarithm.
367     * @param p logarithm base.
368     * @param a element.
369     * @return k &ge; 1 minimal with p^k &ge; b.
370     */
371    public static <C extends RingElem<C>> long logarithm(C p, C a) {
372        //if ( p.compareTo(a) < 0 ) {
373        //    return 0L;
374        //}
375        long k = 1L;
376        C m = p;
377        while (m.compareTo(a) < 0) {
378            m = m.multiply(p);
379            k++;
380        }
381        return k;
382    }
383
384
385    /**
386     * Multiply elements in list.
387     * @param A list of elements (a_0,...,a_k).
388     * @param fac ring factory.
389     * @return prod(i=0,...k) a_i.
390     */
391    public static <C extends RingElem<C>> C multiply(RingFactory<C> fac, List<C> A) {
392        return multiply((MonoidFactory<C>) fac, A);
393    }
394
395
396    /**
397     * Multiply elements in list.
398     * @param A list of elements (a_0,...,a_k).
399     * @param fac monoid factory.
400     * @return prod(i=0,...k) a_i.
401     */
402    public static <C extends MonoidElem<C>> C multiply(MonoidFactory<C> fac, List<C> A) {
403        if (fac == null) {
404            throw new IllegalArgumentException("fac may not be null for empty list");
405        }
406        C res = fac.getONE();
407        if (A == null || A.isEmpty()) {
408            return res;
409        }
410        for (C a : A) {
411            res = res.multiply(a);
412        }
413        return res;
414    }
415
416
417    /**
418     * Sum elements in list.
419     * @param A list of elements (a_0,...,a_k).
420     * @param fac ring factory.
421     * @return sum(i=0,...k) a_i.
422     */
423    public static <C extends RingElem<C>> C sum(RingFactory<C> fac, List<C> A) {
424        return sum((AbelianGroupFactory<C>) fac, A);
425    }
426
427
428    /**
429     * Sum elements in list.
430     * @param A list of elements (a_0,...,a_k).
431     * @param fac monoid factory.
432     * @return sum(i=0,...k) a_i.
433     */
434    public static <C extends AbelianGroupElem<C>> C sum(AbelianGroupFactory<C> fac, List<C> A) {
435        if (fac == null) {
436            throw new IllegalArgumentException("fac may not be null for empty list");
437        }
438        C res = fac.getZERO();
439        if (A == null || A.isEmpty()) {
440            return res;
441        }
442        for (C a : A) {
443            res = res.sum(a);
444        }
445        return res;
446    }
447
448}