001 /*
002 * $Id: Residue.java 3366 2010-10-24 13:02:14Z kredel $
003 */
004
005 package edu.jas.poly;
006
007 import org.apache.log4j.Logger;
008
009 import edu.jas.structure.Element;
010 import edu.jas.structure.NotInvertibleException;
011 import edu.jas.structure.RingElem;
012 import edu.jas.structure.RingFactory;
013 import edu.jas.structure.GcdRingElem;
014
015
016 /**
017 * Residue element based on RingElem residue.
018 * Objects of this class are (nearly) immutable.
019 * @author Heinz Kredel
020 */
021 public class Residue<C extends RingElem<C> >
022 implements RingElem< Residue<C> > {
023
024 private static final Logger logger = Logger.getLogger(Residue.class);
025 private boolean debug = logger.isDebugEnabled();
026
027
028 /** Residue class factory data structure.
029 */
030 protected final ResidueRing<C> ring;
031
032
033 /** Value part of the element data structure.
034 */
035 protected final C val;
036
037
038 /** Flag to remember if this residue element is a unit.
039 * -1 is unknown, 1 is unit, 0 not a unit.
040 */
041 protected int isunit = -1; // initially unknown
042
043
044 /** The constructor creates a Residue object
045 * from a ring factory.
046 * @param r ring factory.
047 */
048 public Residue(ResidueRing<C> r) {
049 this( r, r.ring.getZERO(), 0 );
050 }
051
052
053 /** The constructor creates a Residue object
054 * from a ring factory and a ring element.
055 * @param r ring factory.
056 * @param a ring element.
057 */
058 public Residue(ResidueRing<C> r, C a) {
059 this( r, a, -1 );
060 }
061
062
063 /** The constructor creates a Residue object
064 * from a ring factory, a ring element and an indicator if a is a unit.
065 * @param r ring factory.
066 * @param a ring element.
067 * @param u isunit indicator, -1, 0, 1.
068 */
069 public Residue(ResidueRing<C> r, C a, int u) {
070 ring = r;
071 C v = a.remainder( ring.modul );
072 if ( v.signum() < 0 ) {
073 v = v.sum( ring.modul );
074 }
075 val = v;
076 switch ( u ) {
077 case 0: isunit = u;
078 break;
079 case 1: isunit = u;
080 break;
081 default: isunit = -1;
082 }
083 if ( val.isUnit() ) {
084 isunit = 1;
085 }
086 }
087
088
089 /**
090 * Get the corresponding element factory.
091 * @return factory for this Element.
092 * @see edu.jas.structure.Element#factory()
093 */
094 public ResidueRing<C> factory() {
095 return ring;
096 }
097
098
099 /** Clone this.
100 * @see java.lang.Object#clone()
101 */
102 @Override
103 public Residue<C> clone() {
104 return new Residue<C>( ring, val );
105 }
106
107
108 /** Is Residue zero.
109 * @return If this is 0 then true is returned, else false.
110 * @see edu.jas.structure.RingElem#isZERO()
111 */
112 public boolean isZERO() {
113 return val.equals( ring.ring.getZERO() );
114 }
115
116
117 /** Is Residue one.
118 * @return If this is 1 then true is returned, else false.
119 * @see edu.jas.structure.RingElem#isONE()
120 */
121 public boolean isONE() {
122 return val.equals( ring.ring.getONE() );
123 }
124
125
126 /** Is Residue unit.
127 * @return If this is a unit then true is returned, else false.
128 * @see edu.jas.structure.RingElem#isUnit()
129 */
130 @SuppressWarnings("unchecked")
131 public boolean isUnit() {
132 if ( isunit > 0 ) {
133 return true;
134 }
135 if ( isunit == 0 ) {
136 return false;
137 }
138 // val.isUnit() already tested
139 // not jet known
140 if ( val instanceof GcdRingElem
141 && ring.modul instanceof GcdRingElem ) {
142 GcdRingElem v = (GcdRingElem)val;
143 GcdRingElem m = (GcdRingElem)ring.modul;
144 C gcd = (C) v.gcd( m );
145 if ( debug ) {
146 logger.info("gcd = " + gcd);
147 }
148 boolean u = gcd.isONE();
149 if ( u ) {
150 isunit = 1;
151 } else {
152 isunit = 0;
153 }
154 return u;
155 }
156 // still unknown
157 return false;
158 }
159
160
161 /** Get the String representation as RingElem.
162 * @see java.lang.Object#toString()
163 */
164 @Override
165 public String toString() {
166 return "Residue[ " + val.toString()
167 + " mod " + ring.toString() + " ]";
168 }
169
170
171 /** Get a scripting compatible string representation.
172 * @return script compatible representation for this Element.
173 * @see edu.jas.structure.Element#toScript()
174 */
175 //JAVA6only: @Override
176 public String toScript() {
177 // Python case
178 return "Residue( " + val.toScript()
179 + " , " + ring.toScript() + " )";
180 }
181
182
183 /** Get a scripting compatible string representation of the factory.
184 * @return script compatible representation for this ElemFactory.
185 * @see edu.jas.structure.Element#toScriptFactory()
186 */
187 //JAVA6only: @Override
188 public String toScriptFactory() {
189 // Python case
190 return factory().toScript();
191 }
192
193
194 /** Residue comparison.
195 * @param b Residue.
196 * @return sign(this-b), 0 means that this and b are equivalent in this residue class ring.
197 */
198 //JAVA6only: @Override
199 public int compareTo(Residue<C> b) {
200 C v = b.val;
201 if ( ! ring.equals( b.ring ) ) {
202 v = v.remainder( ring.modul );
203 }
204 return val.compareTo( v );
205 }
206
207
208 /** Comparison with any other object.
209 * @see java.lang.Object#equals(java.lang.Object)
210 * @return true means that this and b are equivalent in this residue class ring.
211 */
212 @SuppressWarnings("unchecked") // not jet working
213 @Override
214 public boolean equals(Object b) {
215 if ( ! ( b instanceof Residue ) ) {
216 return false;
217 }
218 Residue<C> a = null;
219 try {
220 a = (Residue<C>) b;
221 } catch (ClassCastException e) {
222 }
223 if ( a == null ) {
224 return false;
225 }
226 return ( 0 == compareTo( a ) );
227 }
228
229
230 /** Hash code for this local.
231 * @see java.lang.Object#hashCode()
232 */
233 @Override
234 public int hashCode() {
235 int h;
236 h = ring.hashCode();
237 h = 37 * h + val.hashCode();
238 return h;
239 }
240
241
242 /** Residue absolute value.
243 * @return the absolute value of this.
244 * @see edu.jas.structure.RingElem#abs()
245 */
246 public Residue<C> abs() {
247 return new Residue<C>( ring, val.abs() );
248 }
249
250
251 /** Residue summation.
252 * @param S Residue.
253 * @return this+S.
254 */
255 public Residue<C> sum(Residue<C> S) {
256 return new Residue<C>( ring, val.sum( S.val ) );
257 }
258
259
260 /** Residue negate.
261 * @return -this.
262 * @see edu.jas.structure.RingElem#negate()
263 */
264 public Residue<C> negate() {
265 return new Residue<C>( ring, val.negate() );
266 }
267
268
269 /** Residue signum.
270 * @see edu.jas.structure.RingElem#signum()
271 * @return signum(this).
272 */
273 public int signum() {
274 return val.signum();
275 }
276
277
278 /** Residue subtraction.
279 * @param S Residue.
280 * @return this-S.
281 */
282 public Residue<C> subtract(Residue<C> S) {
283 return new Residue<C>( ring, val.subtract( S.val ) );
284 }
285
286
287 /** Residue division.
288 * @param S Residue.
289 * @return this/S.
290 */
291 public Residue<C> divide(Residue<C> S) {
292 return multiply( S.inverse() );
293 }
294
295
296 /** Residue inverse.
297 * @see edu.jas.structure.RingElem#inverse()
298 * @return S with S = 1/this if defined.
299 */
300 @SuppressWarnings("unchecked")
301 public Residue<C> inverse() {
302 if ( isunit == 0 ) {
303 throw new NotInvertibleException("element not invertible (0) " + this);
304 }
305 if ( val instanceof GcdRingElem
306 && ring.modul instanceof GcdRingElem ) {
307 GcdRingElem v = (GcdRingElem)val;
308 GcdRingElem m = (GcdRingElem)ring.modul;
309 C[] egcd = (C[])v.egcd( m );
310 if ( debug ) {
311 logger.info("egcd = " + egcd[0] + ", f = " + egcd[1]);
312 }
313 if ( ! egcd[0].isONE() ) {
314 isunit = 0;
315 throw new NotInvertibleException("element not invertible (gcd)" + this);
316 }
317 isunit = 1;
318 C x = egcd[1];
319 return new Residue<C>( ring, x );
320 }
321 if ( val.isUnit() ) {
322 C x = val.inverse();
323 return new Residue<C>( ring, x );
324 }
325 System.out.println("isunit = " + isunit
326 + ", isUnit() = " + this.isUnit() );
327 throw new NotInvertibleException("element not invertible (!gcd)" + this);
328 }
329
330
331 /** Residue remainder.
332 * @param S Residue.
333 * @return this - (this/S)*S.
334 */
335 public Residue<C> remainder(Residue<C> S) {
336 C x = val.remainder( S.val );
337 return new Residue<C>( ring, x );
338 }
339
340
341 /** Residue multiplication.
342 * @param S Residue.
343 * @return this*S.
344 */
345 public Residue<C> multiply(Residue<C> S) {
346 return new Residue<C>( ring, val.multiply( S.val ) );
347 }
348
349
350 /**
351 * Greatest common divisor.
352 * <b>Note: </b>Not implemented, throws UnsupportedOperationException.
353 * @param b other element.
354 * @return gcd(this,b).
355 */
356 public Residue<C> gcd(Residue<C> b) {
357 throw new UnsupportedOperationException("gcd not implemented " + this.getClass().getName());
358 }
359
360
361 /**
362 * Extended greatest common divisor.
363 * <b>Note: </b>Not implemented, throws UnsupportedOperationException.
364 * @param b other element.
365 * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
366 */
367 public Residue<C>[] egcd(Residue<C> b) {
368 throw new UnsupportedOperationException("egcd not implemented " + this.getClass().getName());
369 }
370
371 }