Source code

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