Source code

001/*
002 * $Id: GCDFactory.java 5110 2015-02-12 20:32:08Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import org.apache.log4j.Logger;
009
010import edu.jas.arith.BigInteger;
011import edu.jas.arith.BigRational;
012import edu.jas.arith.ModInteger;
013import edu.jas.arith.ModIntegerRing;
014import edu.jas.arith.ModLong;
015import edu.jas.arith.ModLongRing;
016import edu.jas.kern.ComputerThreads;
017import edu.jas.structure.GcdRingElem;
018import edu.jas.structure.RingFactory;
019
020
021/**
022 * Greatest common divisor algorithms factory. Select appropriate GCD engine
023 * based on the coefficient types.
024 * @author Heinz Kredel
025 * @usage To create objects that implement the
026 *        <code>GreatestCommonDivisor</code> interface use the
027 *        <code>GCDFactory</code>. It will select an appropriate implementation
028 *        based on the types of polynomial coefficients C. There are two methods
029 *        to obtain an implementation: <code>getProxy()</code> and
030 *        <code>getImplementation()</code>. <code>getImplementation()</code>
031 *        returns an object of a class which implements the
032 *        <code>GreatestCommonDivisor</code> interface. <code>getProxy()</code>
033 *        returns a proxy object of a class which implements the
034 *        <code>GreatestCommonDivisor</code>r interface. The proxy will run two
035 *        implementations in parallel, return the first computed result and
036 *        cancel the second running task. On systems with one CPU the computing
037 *        time will be two times the time of the fastest algorithm
038 *        implmentation. On systems with more than two CPUs the computing time
039 *        will be the time of the fastest algorithm implmentation.
040 * 
041 *        <pre>
042 * GreatestCommonDivisor&lt;CT&gt; engine;
043 * engine = GCDFactory.&lt;CT&gt; getImplementation(cofac);
044 * or engine = GCDFactory.&lt;CT&gt; getProxy(cofac);
045 * c = engine.gcd(a, b);
046 * </pre>
047 * 
048 *        For example, if the coefficient type is BigInteger, the usage looks
049 *        like
050 * 
051 *        <pre>
052 * BigInteger cofac = new BigInteger();
053 * GreatestCommonDivisor&lt;BigInteger&gt; engine;
054 * engine = GCDFactory.getImplementation(cofac);
055 * or engine = GCDFactory.getProxy(cofac);
056 * c = engine.gcd(a, b);
057 * </pre>
058 * 
059 * @see edu.jas.ufd.GreatestCommonDivisor#gcd(edu.jas.poly.GenPolynomial P,
060 *      edu.jas.poly.GenPolynomial S) <b>Todo:</b> Base decision also on degree
061 *      vectors and number of variables of polynomials. Incorporate also number
062 *      of CPUs / threads available (done with GCDProxy).
063 */
064
065public class GCDFactory {
066
067
068    private static final Logger logger = Logger.getLogger(GCDFactory.class);
069
070
071    /**
072     * Protected factory constructor.
073     */
074    protected GCDFactory() {
075    }
076
077
078    /**
079     * Determine suitable implementation of gcd algorithms, case ModLong.
080     * @param fac ModLongRing.
081     * @return gcd algorithm implementation.
082     */
083    public static GreatestCommonDivisorAbstract<ModLong> getImplementation(ModLongRing fac) {
084        GreatestCommonDivisorAbstract<ModLong> ufd;
085        if (fac.isField()) {
086            ufd = new GreatestCommonDivisorModEval<ModLong>();
087            //ufd = new GreatestCommonDivisorSimple<ModLong>();
088            return ufd;
089        }
090        ufd = new GreatestCommonDivisorSubres<ModLong>();
091        return ufd;
092    }
093
094
095    /**
096     * Determine suitable proxy for gcd algorithms, case ModLong.
097     * @param fac ModLongRing.
098     * @return gcd algorithm implementation.
099     */
100    public static GreatestCommonDivisorAbstract<ModLong> getProxy(ModLongRing fac) {
101        GreatestCommonDivisorAbstract<ModLong> ufd1, ufd2;
102        ufd1 = new GreatestCommonDivisorSubres<ModLong>();
103        if (fac.isField()) {
104            ufd2 = new GreatestCommonDivisorModEval<ModLong>();
105        } else {
106            ufd2 = new GreatestCommonDivisorSimple<ModLong>();
107        }
108        return new GCDProxy<ModLong>(ufd1, ufd2);
109    }
110
111
112    /**
113     * Determine suitable implementation of gcd algorithms, case ModInteger.
114     * @param fac ModIntegerRing.
115     * @return gcd algorithm implementation.
116     */
117    public static GreatestCommonDivisorAbstract<ModInteger> getImplementation(ModIntegerRing fac) {
118        GreatestCommonDivisorAbstract<ModInteger> ufd;
119        if (fac.isField()) {
120            ufd = new GreatestCommonDivisorModEval<ModInteger>();
121            //ufd = new GreatestCommonDivisorSimple<ModInteger>();
122            return ufd;
123        }
124        ufd = new GreatestCommonDivisorSubres<ModInteger>();
125        return ufd;
126    }
127
128
129    /**
130     * Determine suitable proxy for gcd algorithms, case ModInteger.
131     * @param fac ModIntegerRing.
132     * @return gcd algorithm implementation.
133     */
134    public static GreatestCommonDivisorAbstract<ModInteger> getProxy(ModIntegerRing fac) {
135        GreatestCommonDivisorAbstract<ModInteger> ufd1, ufd2;
136        ufd1 = new GreatestCommonDivisorSubres<ModInteger>();
137        if (fac.isField()) {
138            ufd2 = new GreatestCommonDivisorModEval<ModInteger>();
139        } else {
140            ufd2 = new GreatestCommonDivisorSimple<ModInteger>();
141        }
142        return new GCDProxy<ModInteger>(ufd1, ufd2);
143    }
144
145
146    /**
147     * Determine suitable implementation of gcd algorithms, case BigInteger.
148     * @param fac BigInteger.
149     * @return gcd algorithm implementation.
150     */
151    @SuppressWarnings("unused")
152    public static GreatestCommonDivisorAbstract<BigInteger> getImplementation(BigInteger fac) {
153        GreatestCommonDivisorAbstract<BigInteger> ufd;
154        if (true) {
155            ufd = new GreatestCommonDivisorModular<ModLong>(); // dummy type
156        } else {
157            ufd = new GreatestCommonDivisorSubres<BigInteger>();
158        }
159        return ufd;
160    }
161
162
163    /**
164     * Determine suitable procy for gcd algorithms, case BigInteger.
165     * @param fac BigInteger.
166     * @return gcd algorithm implementation.
167     */
168    @SuppressWarnings("unused")
169    public static GreatestCommonDivisorAbstract<BigInteger> getProxy(BigInteger fac) {
170        GreatestCommonDivisorAbstract<BigInteger> ufd1, ufd2;
171        ufd1 = new GreatestCommonDivisorSubres<BigInteger>();
172        ufd2 = new GreatestCommonDivisorModular<ModLong>(); // dummy type
173        return new GCDProxy<BigInteger>(ufd1, ufd2);
174    }
175
176
177    /**
178     * Determine suitable implementation of gcd algorithms, case BigRational.
179     * @param fac BigRational.
180     * @return gcd algorithm implementation.
181     */
182    @SuppressWarnings("unused")
183    public static GreatestCommonDivisorAbstract<BigRational> getImplementation(BigRational fac) {
184        GreatestCommonDivisorAbstract<BigRational> ufd;
185        ufd = new GreatestCommonDivisorPrimitive<BigRational>();
186        return ufd;
187    }
188
189
190    /**
191     * Determine suitable proxy for gcd algorithms, case BigRational.
192     * @param fac BigRational.
193     * @return gcd algorithm implementation.
194     */
195    public static GreatestCommonDivisorAbstract<BigRational> getProxy(BigRational fac) {
196        GreatestCommonDivisorAbstract<BigRational> ufd1, ufd2;
197        ufd1 = new GreatestCommonDivisorSubres<BigRational>();
198        ufd2 = new GreatestCommonDivisorSimple<BigRational>();
199        return new GCDProxy<BigRational>(ufd1, ufd2);
200    }
201
202
203    /**
204     * Determine suitable implementation of gcd algorithms, other cases.
205     * @param fac RingFactory&lt;C&gt;.
206     * @return gcd algorithm implementation.
207     */
208    @SuppressWarnings("unchecked")
209    public static <C extends GcdRingElem<C>> GreatestCommonDivisorAbstract<C> getImplementation(
210                    RingFactory<C> fac) {
211        GreatestCommonDivisorAbstract/*raw type<C>*/ufd;
212        logger.debug("fac = " + fac.getClass().getName());
213        Object ofac = fac;
214        if (ofac instanceof BigInteger) {
215            ufd = new GreatestCommonDivisorModular<ModInteger>();
216            //ufd = new GreatestCommonDivisorSubres<BigInteger>();
217            //ufd = new GreatestCommonDivisorModular<ModInteger>(true);
218        } else if (ofac instanceof ModIntegerRing) {
219            ufd = new GreatestCommonDivisorModEval<ModInteger>();
220            //ufd = new GreatestCommonDivisorSimple<ModInteger>();
221        } else if (ofac instanceof ModLongRing) {
222            ufd = new GreatestCommonDivisorModEval<ModLong>();
223            //ufd = new GreatestCommonDivisorSimple<ModLong>();
224        } else if (ofac instanceof BigRational) {
225            ufd = new GreatestCommonDivisorSubres<BigRational>();
226        } else {
227            if (fac.isField()) {
228                ufd = new GreatestCommonDivisorSimple<C>();
229            } else {
230                ufd = new GreatestCommonDivisorSubres<C>();
231            }
232        }
233        logger.debug("implementation = " + ufd);
234        return ufd;
235    }
236
237
238    /**
239     * Determine suitable proxy for gcd algorithms, other cases.
240     * @param fac RingFactory&lt;C&gt;.
241     * @return gcd algorithm implementation. <b>Note:</b> This method contains a
242     *         hack for Google app engine to not use threads.
243     * @see edu.jas.kern.ComputerThreads#NO_THREADS
244     */
245    @SuppressWarnings("unchecked")
246    public static <C extends GcdRingElem<C>> GreatestCommonDivisorAbstract<C> getProxy(RingFactory<C> fac) {
247        if (ComputerThreads.NO_THREADS) { // hack for Google app engine
248            return GCDFactory.<C> getImplementation(fac);
249        }
250        GreatestCommonDivisorAbstract/*raw type<C>*/ufd;
251        logger.debug("fac = " + fac.getClass().getName());
252        Object ofac = fac;
253        if (ofac instanceof BigInteger) {
254            ufd = new GCDProxy<BigInteger>(new GreatestCommonDivisorSubres<BigInteger>(),
255                            new GreatestCommonDivisorModular<ModInteger>());
256        } else if (ofac instanceof ModIntegerRing) {
257            ufd = new GCDProxy<ModInteger>(new GreatestCommonDivisorSimple<ModInteger>(), // Subres
258                            new GreatestCommonDivisorModEval<ModInteger>());
259        } else if (ofac instanceof ModLongRing) {
260            ufd = new GCDProxy<ModLong>(new GreatestCommonDivisorSimple<ModLong>(), // Subres
261                            new GreatestCommonDivisorModEval<ModLong>());
262        } else if (ofac instanceof BigRational) {
263            ufd = new GCDProxy<BigRational>(new GreatestCommonDivisorSubres<BigRational>(),
264                            new GreatestCommonDivisorSimple<BigRational>());
265        } else {
266            if (fac.isField()) {
267                ufd = new GCDProxy<C>(new GreatestCommonDivisorSimple<C>(),
268                                new GreatestCommonDivisorSubres<C>());
269            } else {
270                ufd = new GCDProxy<C>(new GreatestCommonDivisorSubres<C>(),
271                                new GreatestCommonDivisorPrimitive<C>()); // no resultant
272            }
273        }
274        logger.debug("ufd = " + ufd);
275        return ufd;
276    }
277
278}