Source code

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