IntNum


1   // Copyright (c) 1997, 1998, 1999, 2000, 2006  Per M.A. Bothner.
2   // This is free software;  for terms and warranty disclaimer see ./COPYING.
3   
4   package gnu.math;
5   import java.io.*;
6   import java.math.BigDecimal  ;
7   import java.math.BigInteger  ;
8   
9   /** A class for infinite-precision integers.
10   * @author Per Bothner
11   */
12  
13  public class IntNum extends RatNum implements Externalizable
14  {
15    /** All integers are stored in 2's-complement form.
16     * If words == null, the ival is the value of this IntNum.
17     * Otherwise, the first ival elements of words make the value
18     * of this IntNum, stored in little-endian order, 2's-complement form. */
19    public int ival;
20    public int[] words;
21  
22  
23    /** We pre-allocate integers in the range minFixNum..maxFixNum. */
24    static final int minFixNum = -100;
25    static final int maxFixNum = 1024;
26    static final int numFixNum = maxFixNum-minFixNum+1;
27    static final IntNum[] smallFixNums = new IntNum[numFixNum];
28  
29    static {
30      for (int i = numFixNum;  --i >= 0; )
31        smallFixNums[i] = new IntNum(i + minFixNum);
32    }
33  
34    public IntNum ()
35    {
36    }
37  
38    /** Create a new (non-shared) IntNum, and initialize to an int.
39     * @param value the initial value */
40    public IntNum (int value)
41    {
42      ival = value;
43    }
44  
45    /** Return a (possibly-shared) IntNum with a given int value. */
46    public static IntNum make (int value)
47    {
48      if (value >= minFixNum && value <= maxFixNum)
49        return smallFixNums[(int) value - minFixNum];
50      else
51        return new IntNum (value);
52    }
53  
54    public static final IntNum zero ()
55    {
56      return smallFixNums[- minFixNum];
57    }
58  
59    public static final IntNum one ()
60    {
61      return smallFixNums[1 - minFixNum];
62    }
63  
64    public static final IntNum ten ()
65    {
66      return smallFixNums[10 - minFixNum];
67    }
68  
69    /** Return the IntNum for -1. */
70    public static IntNum minusOne ()
71    {
72      return smallFixNums[-1 - minFixNum];
73    }
74  
75    /** Return a (possibly-shared) IntNum with a given long value. */
76    public static IntNum make (long value)
77    {
78      if (value >= minFixNum && value <= maxFixNum)
79        return smallFixNums[(int)value - minFixNum];
80      int i = (int) value;
81      if ((long)i == value)
82        return new IntNum (i);
83      IntNum result = alloc (2);
84      result.ival = 2;
85      result.words[0] = i;
86      result.words[1] = (int) (value >> 32);
87      return result;
88    }
89  
90    /** Make an IntNum from an unsigned 64-bit value. */
91    public static IntNum makeU (long value)
92    {
93      if (value >= 0)
94        return make(value);
95      IntNum result = alloc(3);
96      result.ival = 3;
97      result.words[0] = (int) value;
98      result.words[1] = (int) (value >> 32);
99      result.words[2] = 0;
100     return result;
101   }
102 
103   /** Make a canonicalized IntNum from an array of words.
104    * The array may be reused (without copying). */
105   public static IntNum make (int[] words, int len)
106   {
107     if (words == null)
108       return make (len);
109     len = IntNum.wordsNeeded (words, len);
110     if (len <= 1)
111       return len == 0 ? zero () : make (words[0]);
112     IntNum num = new IntNum ();
113     num.words = words;
114     num.ival = len;
115     return num;
116   }
117 
118   public static IntNum make (int[] words)
119   {
120     return make(words, words.length);
121   }
122 
123   /** Allocate a new non-shared IntNum.
124    * @param nwords number of words to allocate
125    */
126   public static IntNum alloc (int nwords)
127   {
128     if (nwords <= 1)
129       return new IntNum ();
130     IntNum result = new IntNum ();
131     result.words = new int[nwords];
132     return result;
133   }
134 
135   /** Change words.length to nwords.
136   * We allow words.length to be upto nwords+2 without reallocating. */
137   public void realloc (int nwords)
138   {
139     if (nwords == 0)
140       {
141     if (words != null)
142       {
143         if (ival > 0)
144           ival = words[0];
145         words = null;
146       }
147       }
148     else if (words == null
149          || words.length < nwords
150          || words.length > nwords + 2)
151       {
152     int[] new_words = new int [nwords];
153     if (words == null)
154       {
155         new_words[0] = ival;
156         ival = 1;
157       }
158     else
159       {
160         if (nwords < ival)
161           ival = nwords;
162         System.arraycopy (words, 0, new_words, 0, ival);
163       }
164     words = new_words;
165       }
166   }
167 
168   public final IntNum numerator ()
169   {
170     return this;
171   }
172 
173   public final IntNum denominator ()
174   {
175     return one ();
176   }
177 
178   public final boolean isNegative ()
179   {
180     return (words == null ? ival : words[ival-1]) < 0;
181   }
182 
183   public int sign ()
184   {
185     int n = ival;
186     int[] w = words;
187     if (w == null)
188       return n > 0 ? 1 : n < 0 ? -1 : 0;
189     int i = w[--n];
190     if (i > 0)
191       return 1;
192     if (i < 0)
193       return -1;
194     for (;;)
195       {
196     if (n == 0)
197       return 0;
198     if (w[--n] != 0)
199       return 1;
200       }
201   }
202 
203   /** Return -1, 0, or 1, depending on which value is greater. */
204   public static int compare (IntNum x, IntNum y)
205   {
206     if (x.words == null && y.words == null)
207       return x.ival < y.ival ? -1 : x.ival > y.ival ? 1 : 0;
208     boolean x_negative = x.isNegative ();
209     boolean y_negative = y.isNegative ();
210     if (x_negative != y_negative)
211       return x_negative ? -1 : 1;
212     int x_len = x.words == null ? 1 : x.ival;
213     int y_len = y.words == null ? 1 : y.ival;
214     if (x_len != y_len) // We assume x and y are canonicalized.
215       return (x_len > y_len)!=x_negative ? 1 : -1;
216     return MPN.cmp (x.words, y.words, x_len);
217   }
218  
219   /** Return -1, 0, or 1, depending on which value is greater. */
220  public static int compare (IntNum x, long y)
221   {
222     long x_word;
223     if (x.words == null)
224       x_word = x.ival;
225     else
226       {
227     boolean x_negative = x.isNegative ();
228     boolean y_negative = y < 0;
229     if (x_negative != y_negative)
230       return x_negative ? -1 : 1;
231     int x_len = x.words == null ? 1 : x.ival;
232     if (x_len == 1)
233       x_word = x.words[0];
234     else if (x_len == 2)
235       x_word = x.longValue();
236     else // We assume x is canonicalized.
237       return x_negative ? -1 : 1;
238       }
239     return x_word < y ? -1 : x_word > y ? 1 : 0;
240   }
241 
242   public int compare (Object   obj)
243   {
244     if (obj instanceof IntNum)
245       return compare (this, (IntNum) obj);
246     return ((RealNum)obj).compareReversed (this);
247   }
248 
249   public final boolean isOdd ()
250   {
251     int low = words == null ? ival : words[0];
252     return (low & 1) != 0;
253   }
254 
255   public final boolean isZero ()
256   {
257     return words == null && ival == 0;
258   }
259 
260   public final boolean isOne ()
261   {
262     return words == null && ival == 1;
263   }
264 
265   public final boolean isMinusOne ()
266   {
267     return words == null && ival == -1;
268   }
269 
270   /** Calculate how many words are significant in words[0:len-1].
271    * Returns the least value x such that x>0 && words[0:x-1]==words[0:len-1],
272    * when words is viewed as a 2's complement integer.
273    */
274   public static int wordsNeeded (int[] words, int len)
275   {
276     int i = len;
277     if (i > 0)
278       {
279     int word = words[--i];
280     if (word == -1)
281       {
282         while (i > 0 && (word = words[i-1]) < 0)
283           {
284         i--;
285         if (word != -1) break;
286           }
287       }
288     else
289       {
290         while (word == 0 && i > 0 && (word = words[i-1]) >= 0)  i--;
291       }
292       }
293     return i+1;
294   }
295 
296   public IntNum canonicalize ()
297   {
298     if (words != null
299     && (ival = IntNum.wordsNeeded (words, ival)) <= 1)
300       {
301     if (ival == 1)
302       ival = words[0];
303     words = null;
304       }
305     if (words == null && ival >= minFixNum && ival <= maxFixNum)
306       return smallFixNums[(int) ival - minFixNum];
307     return this;
308   }
309 
310   /** Add two ints, yielding an IntNum. */
311   public static final IntNum add (int x, int y)
312   {
313     return IntNum.make ((long) x + (long) y);
314   }
315 
316   /** Add an IntNum and an int, yielding a new IntNum. */
317   public static IntNum add (IntNum x, int y)
318   {
319     if (x.words == null)
320       return IntNum.add (x.ival, y);
321     IntNum result = new IntNum (0);
322     result.setAdd (x, y);
323     return result.canonicalize ();
324   }
325 
326   /** Set this to the sum of x and y.
327    * OK if x==this. */
328   public void setAdd (IntNum x, int y)
329   {
330     if (x.words == null)
331       {
332     set ((long) x.ival + (long) y);
333     return;
334       }
335     int len = x.ival;
336     realloc (len + 1);
337     long carry = y;
338     for (int i = 0;  i < len;  i++)
339       {
340     carry += ((long) x.words[i] & 0xffffffffL);
341     words[i] = (int) carry;
342     carry >>= 32;
343       }
344     if (x.words[len - 1] < 0)
345       carry--;
346     words[len] = (int) carry;
347     ival = wordsNeeded (words, len+1);
348   }
349 
350   /** Destructively add an int to this. */
351   public final void setAdd (int y)
352   {
353     setAdd (this, y);
354   }
355 
356   /** Destructively set the value of this to an int. */
357   public final void set (int y)
358   {
359     words = null;
360     ival = y;
361   }
362 
363   /** Destructively set the value of this to a long. */
364   public final void set (long y)
365   {
366     int i = (int) y;
367     if ((long) i == y)
368       {
369     ival = i;
370     words = null;
371       }
372     else
373       {
374     realloc (2);
375     words[0] = i;
376     words[1] = (int) (y >> 32);
377     ival = 2;
378       }
379   }
380 
381   /** Destructively set the value of this to the given words.
382   * The words array is reused, not copied. */
383   public final void set (int[] words, int length)
384   {
385     this.ival = length;
386     this.words = words;
387   }
388 
389   /** Destructively set the value of this to that of y. */
390   public final void set (IntNum y)
391   {
392     if (y.words == null)
393       set (y.ival);
394     else if (this != y)
395       {
396     realloc(y.ival);
397     System.arraycopy(y.words, 0, words, 0, y.ival);
398     ival = y.ival;
399       }
400   }
401 
402   /** Add two IntNums, yielding their sum as another IntNum. */
403   public static IntNum add (IntNum x, IntNum y)
404   {
405     return add(x, y, 1);
406   }
407 
408   /** Subtract two IntNums, yielding their sum as another IntNum. */
409   public static IntNum sub (IntNum x, IntNum y)
410   {
411     return add(x, y, -1);
412   }
413 
414   /** Add two IntNums, yielding their sum as another IntNum. */
415   public static IntNum add (IntNum x, IntNum y, int k)
416   {
417     if (x.words == null && y.words == null)
418       return IntNum.make ((long) k * (long) y.ival + (long) x.ival);
419     if (k != 1)
420       {
421     if (k == -1)
422       y = IntNum.neg (y);
423     else
424       y = IntNum.times (y, IntNum.make (k));
425       }
426     if (x.words == null)
427       return IntNum.add (y, x.ival);
428     if (y.words == null)
429       return IntNum.add (x, y.ival);
430     // Both are big
431     int len;
432     if (y.ival > x.ival)
433       { // Swap so x is longer then y.
434     IntNum tmp = x;  x = y;  y = tmp;
435       }
436     IntNum result = alloc (x.ival + 1);
437     int i = y.ival;
438     long carry = MPN.add_n (result.words, x.words, y.words, i);
439     long y_ext = y.words[i-1] < 0 ? 0xffffffffL : 0;
440     for (; i < x.ival;  i++)
441       {
442     carry += ((long) x.words[i] & 0xffffffffL) + y_ext;;
443     result.words[i] = (int) carry;
444     carry >>>= 32;
445       }
446     if (x.words[i - 1] < 0)
447       y_ext--;
448     result.words[i] = (int) (carry + y_ext);
449     result.ival = i+1;
450     return result.canonicalize ();
451   }
452 
453   /** Multiply two ints, yielding an IntNum. */
454   public static final IntNum times (int x, int y)
455   {
456     return IntNum.make ((long) x * (long) y);
457   }
458 
459   public static final IntNum times (IntNum x, int y)
460   {
461     if (y == 0)
462       return zero();
463     if (y == 1)
464       return x;
465     int[] xwords = x.words;
466     int xlen = x.ival;
467     if (xwords == null)
468       return IntNum.make ((long) xlen * (long) y);
469     boolean negative;
470     IntNum result = IntNum.alloc (xlen+1);
471     if (xwords[xlen-1] < 0)
472       {
473     negative = true;
474     negate(result.words, xwords, xlen);
475     xwords = result.words;
476       }
477     else
478       negative = false;
479     if (y < 0)
480       {
481     negative = !negative;
482     y = -y;
483       }
484     result.words[xlen] = MPN.mul_1 (result.words, xwords, xlen, y);
485     result.ival = xlen+1;
486     if (negative)
487       result.setNegative ();
488     return result.canonicalize ();
489   }
490 
491   public static final IntNum times (IntNum x, IntNum y)
492   {
493     if (y.words == null)
494       return times(x, y.ival);
495     if (x.words == null)
496       return times(y, x.ival);
497     boolean negative = false;
498     int[] xwords;
499     int[] ywords;
500     int xlen = x.ival;
501     int ylen = y.ival;
502     if (x.isNegative ())
503       {
504     negative = true;
505     xwords = new int[xlen];
506     negate(xwords, x.words, xlen);
507       }
508     else
509       {
510     negative = false;
511     xwords = x.words;
512       }
513     if (y.isNegative ())
514       {
515     negative = !negative;
516     ywords = new int[ylen];
517     negate(ywords, y.words, ylen);
518       }
519     else
520       ywords = y.words;
521     // Swap if x is shorter then y.
522     if (xlen < ylen)
523       {
524     int[] twords = xwords;  xwords = ywords;  ywords = twords;
525     int tlen = xlen;  xlen = ylen;  ylen = tlen;
526       }
527     IntNum result = IntNum.alloc (xlen+ylen);
528     MPN.mul (result.words, xwords, xlen, ywords, ylen);
529     result.ival = xlen+ylen;
530     if (negative)
531       result.setNegative ();
532     return result.canonicalize ();
533   }
534 
535   public static void divide (long x, long y,
536                  IntNum quotient, IntNum remainder,
537                  int rounding_mode)
538   {
539     boolean xNegative, yNegative;
540     if (x < 0)
541       {
542     xNegative = true;
543     if (x == Long.MIN_VALUE)
544       {
545         divide (IntNum.make (x), IntNum.make (y),
546             quotient, remainder, rounding_mode);
547         return;
548       }
549     x = -x;
550       }
551     else
552       xNegative = false;
553 
554     if (y < 0)
555       {
556     yNegative = true;
557     if (y == Long.MIN_VALUE)
558       {
559         if (rounding_mode == TRUNCATE)
560           { // x != Long.Min_VALUE implies abs(x) < abs(y)
561         if (quotient != null)
562           quotient.set (0);
563         if (remainder != null)
564           remainder.set (x);
565           }
566         else
567           divide (IntNum.make (x), IntNum.make (y),
568               quotient, remainder, rounding_mode);
569         return;
570       }
571     y = -y;
572       }
573     else
574       yNegative = false;
575 
576     long q = x / y;
577     long r = x % y;
578     boolean qNegative = xNegative ^ yNegative;
579 
580     boolean add_one = false;
581     if (r != 0)
582       {
583     switch (rounding_mode)
584       {
585       case TRUNCATE:
586         break;
587       case CEILING:
588       case FLOOR:
589         if (qNegative == (rounding_mode == FLOOR))
590           add_one = true;
591         break;
592       case ROUND:
593         add_one = r > ((y - (q & 1)) >> 1);
594         break;
595       }
596       }
597     if (quotient != null)
598       {
599     if (add_one)
600       q++;
601     if (qNegative)
602       q = -q;
603     quotient.set (q);
604       }
605     if (remainder != null)
606       {
607     // The remainder is by definition: X-Q*Y
608     if (add_one)
609       {
610         // Subtract the remainder from Y.
611         r = y - r;
612         // In this case, abs(Q*Y) > abs(X).
613         // So sign(remainder) = -sign(X).
614         xNegative = ! xNegative;
615       }
616     else
617       {
618         // If !add_one, then: abs(Q*Y) <= abs(X).
619         // So sign(remainder) = sign(X).
620       }
621     if (xNegative)
622       r = -r;
623     remainder.set (r);
624       }
625   }
626 
627   /** Divide two integers, yielding quotient and remainder.
628    * @param x the numerator in the division
629    * @param y the denominator in the division
630    * @param quotient is set to the quotient of the result (iff quotient!=null)
631    * @param remainder is set to the remainder of the result
632    *  (iff remainder!=null)
633    * @param rounding_mode one of FLOOR, CEILING, TRUNCATE, or ROUND.
634    */
635   public static void divide (IntNum x, IntNum y,
636                  IntNum quotient, IntNum remainder,
637                  int rounding_mode)
638   {
639     if ((x.words == null || x.ival <= 2)
640     && (y.words == null || y.ival <= 2))
641       {
642     long x_l = x.longValue ();
643     long y_l = y.longValue ();
644     if (x_l != Long.MIN_VALUE && y_l != Long.MIN_VALUE)
645       {
646         divide (x_l, y_l, quotient, remainder, rounding_mode);
647         return;
648       }
649       }
650 
651     boolean xNegative = x.isNegative ();
652     boolean yNegative = y.isNegative ();
653     boolean qNegative = xNegative ^ yNegative;
654 
655     int ylen = y.words == null ? 1 : y.ival;
656     int[] ywords = new int[ylen];
657     y.getAbsolute (ywords);
658     while (ylen > 1 && ywords[ylen-1] == 0)  ylen--;
659 
660     int xlen = x.words == null ? 1 : x.ival;
661     int[] xwords = new int[xlen+2];
662     x.getAbsolute (xwords);
663     while (xlen > 1 && xwords[xlen-1] == 0)  xlen--;
664 
665     int qlen, rlen;
666 
667     int cmpval = MPN.cmp (xwords, xlen, ywords, ylen);
668     if (cmpval < 0)  // abs(x) < abs(y)
669       { // quotient = 0;  remainder = num.
670     int[] rwords = xwords;  xwords = ywords;  ywords = rwords;
671     rlen = xlen;  qlen = 1;  xwords[0] = 0;
672       }
673     else if (cmpval == 0)  // abs(x) == abs(y)
674       {
675     xwords[0] = 1;  qlen = 1;  // quotient = 1
676     ywords[0] = 0;  rlen = 1;  // remainder = 0;
677       }
678     else if (ylen == 1)
679       {
680     qlen = xlen;
681     rlen = 1;
682     ywords[0] = MPN.divmod_1 (xwords, xwords, xlen, ywords[0]);
683       }
684     else  // abs(x) > abs(y)
685       {
686     // Normalize the denominator, i.e. make its most significant bit set by
687     // shifting it normalization_steps bits to the left.  Also shift the
688     // numerator the same number of steps (to keep the quotient the same!).
689 
690     int nshift = MPN.count_leading_zeros (ywords[ylen-1]);
691     if (nshift != 0)
692       {
693         // Shift up the denominator setting the most significant bit of
694         // the most significant word.
695         MPN.lshift (ywords, 0, ywords, ylen, nshift);
696 
697         // Shift up the numerator, possibly introducing a new most
698         // significant word.
699         int x_high = MPN.lshift (xwords, 0, xwords, xlen, nshift);
700         xwords[xlen++] = x_high;
701     }
702 
703     if (xlen == ylen)
704       xwords[xlen++] = 0;
705     MPN.divide (xwords, xlen, ywords, ylen);
706     rlen = ylen;
707         MPN.rshift0 (ywords, xwords, 0, rlen, nshift);
708 
709     qlen = xlen + 1 - ylen;
710     if (quotient != null)
711       {
712         for (int i = 0;  i < qlen;  i++)
713           xwords[i] = xwords[i+ylen];
714       }
715       }
716 
717     while (rlen > 1 && ywords[rlen-1] == 0)
718       rlen--;
719     if (ywords[rlen-1] < 0)
720       {
721         ywords[rlen] = 0;
722         rlen++;
723       }
724 
725     // Now the quotient is in xwords, and the remainder is in ywords.
726 
727     boolean add_one = false;
728     if (rlen > 1 || ywords[0] != 0)
729       { // Non-zero remainder i.e. in-exact quotient.
730     switch (rounding_mode)
731       {
732       case TRUNCATE:
733         break;
734       case CEILING:
735       case FLOOR:
736         if (qNegative == (rounding_mode == FLOOR))
737           add_one = true;
738         break;
739       case ROUND:
740         // int cmp = compare (remainder<<1, abs(y));
741         IntNum tmp = remainder == null ? new IntNum() : remainder;
742         tmp.set (ywords, rlen);
743         tmp = shift (tmp, 1);
744         if (yNegative)
745           tmp.setNegative();
746         int cmp = compare (tmp, y);
747         // Now cmp == compare(sign(y)*(remainder<<1), y)
748         if (yNegative)
749           cmp = -cmp;
750         add_one = (cmp == 1) || (cmp == 0 && (xwords[0]&1) != 0);
751       }
752       }
753     if (quotient != null)
754       {
755         if (xwords[qlen-1] < 0)
756           {
757             xwords[qlen] = 0;
758             qlen++;
759           }
760     quotient.set (xwords, qlen);
761     if (qNegative)
762       {
763         if (add_one)  // -(quotient + 1) == ~(quotient)
764           quotient.setInvert ();
765         else
766           quotient.setNegative ();
767       }
768     else if (add_one)
769       quotient.setAdd (1);
770       }
771     if (remainder != null)
772       {
773     // The remainder is by definition: X-Q*Y
774     remainder.set (ywords, rlen);
775     if (add_one)
776       {
777         // Subtract the remainder from Y:
778         // abs(R) = abs(Y) - abs(orig_rem) = -(abs(orig_rem) - abs(Y)).
779         IntNum tmp;
780         if (y.words == null)
781           {
782         tmp = remainder;
783         tmp.set(yNegative ? ywords[0] + y.ival : ywords[0] - y.ival);
784           }
785         else
786           tmp = IntNum.add(remainder, y, yNegative ? 1 : -1);
787         // Now tmp <= 0.
788         // In this case, abs(Q) = 1 + floor(abs(X)/abs(Y)).
789         // Hence, abs(Q*Y) > abs(X).
790         // So sign(remainder) = -sign(X).
791         if (xNegative)
792           remainder.setNegative(tmp);
793         else
794           remainder.set(tmp);
795       }
796     else
797       {
798         // If !add_one, then: abs(Q*Y) <= abs(X).
799         // So sign(remainder) = sign(X).
800         if (xNegative)
801           remainder.setNegative ();
802       }
803       }
804   }
805 
806   public static IntNum quotient (IntNum x, IntNum y, int rounding_mode)
807   {
808     IntNum quotient = new IntNum ();
809     divide (x, y, quotient, null, rounding_mode);
810     return quotient.canonicalize ();
811   }
812 
813   public static IntNum quotient (IntNum x, IntNum y)
814   {
815     return quotient (x, y, TRUNCATE);
816   }
817 
818   public IntNum toExactInt (int rounding_mode)
819   {
820     return this;
821   }
822 
823   public RealNum toInt (int rounding_mode)
824   {
825     return this;
826   }
827 
828   public static IntNum remainder (IntNum x, IntNum y)
829   {
830     if (y.isZero())
831       return x;
832     IntNum rem = new IntNum ();
833     divide (x, y, null, rem, TRUNCATE);
834     return rem.canonicalize ();
835   }
836 
837   public static IntNum modulo (IntNum x, IntNum y)
838   {
839     if (y.isZero())
840       return x;
841     IntNum rem = new IntNum ();
842     divide (x, y, null, rem, FLOOR);
843     return rem.canonicalize ();
844   }
845 
846   public Numeric power (IntNum y)
847   {
848     if (isOne())
849       return this;
850     if (isMinusOne())
851       return y.isOdd () ? this : IntNum.one ();
852     if (y.words == null && y.ival >= 0)
853       return power (this, y.ival);
854     if (isZero())
855       return y.isNegative () ? RatNum.infinity(-1) : (RatNum) this;
856     return super.power (y);
857   }
858 
859   /** Calculate the integral power of an IntNum.
860    * @param x the value (base) to exponentiate
861    * @param y the exponent (must be non-negative)
862    */
863   public static IntNum power (IntNum x, int y)
864   {
865     if (y <= 0)
866       {
867     if (y == 0)
868       return one ();
869     else
870       throw new Error   ("negative exponent");
871       }
872     if (x.isZero ())
873       return x;
874     int plen = x.words == null ? 1 : x.ival;  // Length of pow2.
875     int blen = ((x.intLength () * y) >> 5) + 2 * plen;
876     boolean negative = x.isNegative () && (y & 1) != 0;
877     int[] pow2 = new int [blen];
878     int[] rwords = new int [blen];
879     int[] work = new int [blen];
880     x.getAbsolute (pow2);   // pow2 = abs(x);
881     int rlen = 1;
882     rwords[0] = 1; // rwords = 1;
883     for (;;)  // for (i = 0;  ; i++)
884       {
885     // pow2 == x**(2**i)
886     // prod = x**(sum(j=0..i-1, (y>>j)&1))
887     if ((y & 1) != 0)
888       { // r *= pow2
889         MPN.mul (work, pow2, plen, rwords, rlen);
890         int[] temp = work;  work = rwords;  rwords = temp;
891         rlen += plen;
892         while (rwords[rlen-1] == 0)  rlen--;
893       }
894     y >>= 1;
895     if (y == 0)
896       break;
897     // pow2 *= pow2;
898     MPN.mul (work, pow2, plen, pow2, plen);
899     int[] temp = work;  work = pow2;  pow2 = temp;  // swap to avoid a copy
900     plen *= 2;
901     while (pow2[plen-1] == 0)  plen--;
902       }
903     if (rwords[rlen-1] < 0)
904       rlen++;
905     if (negative)
906       negate (rwords, rwords, rlen);
907     return IntNum.make (rwords, rlen);
908   }
909 
910   /** Calculate Greatest Common Divisor for non-negative ints. */
911   public static final int gcd (int a, int b)
912   {
913     // Euclid's algorithm, copied from libg++.
914     if (b > a)
915       {
916     int tmp = a; a = b; b = tmp;
917       }
918     for(;;)
919       {
920     if (b == 0)
921       return a;
922     else if (b == 1)
923       return b;
924     else
925       {
926         int tmp = b;
927         b = a % b;
928         a = tmp;
929       }
930       }
931   }
932 
933   public static IntNum gcd (IntNum x, IntNum y)
934   {
935     int xval = x.ival;
936     int yval = y.ival;
937     if (x.words == null)
938       {
939     if (xval == 0)
940       return IntNum.abs(y);
941     if (y.words == null
942         && xval != Integer.MIN_VALUE && yval != Integer.MIN_VALUE)
943       {
944         if (xval < 0)
945           xval = -xval;
946         if (yval < 0)
947           yval = -yval;
948         return IntNum.make (IntNum.gcd (xval, yval));
949       }
950     xval = 1;
951       }
952     if (y.words == null)
953       {
954     if (yval == 0)
955       return IntNum.abs(x);
956     yval = 1;
957       }
958     int len = (xval > yval ? xval : yval) + 1;
959     int[] xwords = new int[len];
960     int[] ywords = new int[len];
961     x.getAbsolute (xwords);
962     y.getAbsolute (ywords);
963     len = MPN.gcd (xwords, ywords, len);
964     IntNum result = new IntNum (0);
965     result.ival = len;
966     result.words = xwords;
967     return result.canonicalize ();
968   }
969 
970   public static IntNum lcm (IntNum x, IntNum y)
971   {
972     if (x.isZero () || y.isZero ())
973       return IntNum.zero ();
974     x = IntNum.abs (x); 
975     y = IntNum.abs (y);
976     IntNum quotient = new IntNum ();
977     divide (times (x, y), gcd (x, y), quotient, null, TRUNCATE);
978     return quotient.canonicalize ();
979   }
980 
981   void setInvert ()
982   {
983     if (words == null)
984       ival = ~ival;
985     else
986       {
987     for (int i = ival;  --i >= 0; )
988       words[i] = ~words[i];
989       }
990   }
991 
992   void setShiftLeft (IntNum x, int count)
993   {
994     int[] xwords;
995     int xlen;
996     if (x.words == null)
997       {
998     if (count < 32)
999       {
1000        set ((long) x.ival << count);
1001        return;
1002      }
1003    xwords = new int[1];
1004    xwords[0] = x.ival;
1005    xlen = 1;
1006      }
1007    else
1008      {
1009    xwords = x.words;
1010    xlen = x.ival;
1011      }
1012    int word_count = count >> 5;
1013    count &= 31;
1014    int new_len = xlen + word_count;
1015    if (count == 0)
1016      {
1017    realloc (new_len);
1018    for (int i = xlen;  --i >= 0; )
1019      words[i+word_count] = xwords[i];
1020      }
1021    else
1022      {
1023    new_len++;
1024    realloc (new_len);
1025    int shift_out = MPN.lshift (words, word_count, xwords, xlen, count);
1026    count = 32 - count;
1027    words[new_len-1] = (shift_out << count) >> count;  // sign-extend.
1028      }
1029    ival = new_len;
1030    for (int i = word_count;  --i >= 0; )
1031      words[i] = 0;
1032  }
1033
1034  void setShiftRight (IntNum x, int count)
1035  {
1036    if (x.words == null)
1037      set (count < 32 ? x.ival >> count : x.ival < 0 ? -1 : 0);
1038    else if (count == 0)
1039      set (x);
1040    else
1041      {
1042    boolean neg = x.isNegative ();
1043    int word_count = count >> 5;
1044    count &= 31;
1045    int d_len = x.ival - word_count;
1046    if (d_len <= 0)
1047      set (neg ? -1 : 0);
1048    else
1049      {
1050        if (words == null || words.length < d_len)
1051          realloc (d_len);
1052        MPN.rshift0 (words, x.words, word_count, d_len, count);
1053        ival = d_len;
1054        if (neg)
1055          words[d_len-1] |= -2 << (31 - count);
1056      }
1057      }
1058  }
1059
1060  void setShift (IntNum x, int count)
1061  {
1062    if (count > 0)
1063      setShiftLeft (x, count);
1064    else
1065      setShiftRight (x, -count);
1066  }
1067
1068  public static IntNum shift (IntNum x, int count)
1069  {
1070    if (x.words == null)
1071      {
1072    if (count <= 0)
1073      return make (count > -32 ? x.ival >> (-count) : x.ival < 0 ? -1 : 0);
1074    if (count < 32)
1075      return make ((long) x.ival << count);
1076      }
1077    if (count == 0)
1078      return x;
1079    IntNum result = new IntNum (0);
1080    result.setShift (x, count);
1081    return result.canonicalize ();
1082  }
1083
1084  public void format (int radix, StringBuffer   buffer)
1085  {
1086    if (words == null)
1087      buffer.append(Integer.toString (ival, radix));
1088    else if (ival <= 2)
1089      buffer.append(Long.toString (longValue (), radix));
1090    else
1091      {
1092    boolean neg = isNegative ();
1093    int[] work;
1094    if (neg || radix != 16)
1095      {
1096        work = new int[ival];
1097        getAbsolute (work);
1098      }
1099    else
1100      work = words;
1101    int len = ival;
1102
1103    if (radix == 16)
1104      {
1105        if (neg)
1106          buffer.append ('-');
1107        int buf_start = buffer.length ();
1108        for (int i = len;  --i >= 0; )
1109          {
1110        int word = work[i];
1111        for (int j = 8;  --j >= 0; )
1112          {
1113            int hex_digit = (word >> (4 * j)) & 0xF;
1114            // Suppress leading zeros:
1115            if (hex_digit > 0 || buffer.length () > buf_start)
1116              buffer.append (Character.forDigit (hex_digit, 16));
1117          }
1118          }
1119      }
1120    else
1121      {
1122        int i = buffer.length();
1123        for (;;)
1124          {
1125        int digit = MPN.divmod_1 (work, work, len, radix);
1126        buffer.append (Character.forDigit (digit, radix));
1127        while (len > 0 && work[len-1] == 0) len--;
1128        if (len == 0)
1129          break;
1130          }
1131        if (neg)
1132          buffer.append ('-');
1133        /* Reverse buffer. */
1134        int j = buffer.length () - 1;
1135        while (i < j)
1136          {
1137        char tmp = buffer.charAt (i);
1138        buffer.setCharAt (i, buffer.charAt (j));
1139        buffer.setCharAt (j, tmp);
1140        i++;  j--;
1141          }
1142      }
1143      }
1144  }
1145
1146  public String   toString (int radix)
1147  {
1148    if (words == null)
1149      return Integer.toString (ival, radix);
1150    else if (ival <= 2)
1151      return Long.toString (longValue (), radix);
1152    int buf_size = ival * (MPN.chars_per_word (radix) + 1);
1153    StringBuffer   buffer = new StringBuffer   (buf_size);
1154    format(radix, buffer);
1155    return buffer.toString ();
1156  }
1157
1158  public int intValue ()
1159  {
1160    if (words == null)
1161      return ival;
1162    return words[0];
1163  }
1164
1165  /** Cast an Object to an int.  The Object must (currently) be an IntNum. */
1166  public static int intValue (Object   obj)
1167  {
1168    IntNum inum = (IntNum) obj;
1169    if (inum.words != null)
1170      // This is not quite appropriate, but will do.
1171      throw new ClassCastException   ("integer too large");
1172    return inum.ival;
1173  }
1174
1175  public long longValue ()
1176  {
1177    if (words == null)
1178      return ival;
1179    if (ival == 1)
1180      return words[0];
1181    return ((long)words[1] << 32) + ((long)words[0] & 0xffffffffL);
1182  }
1183
1184  public int hashCode ()
1185  {
1186    return words == null ? ival : (words[0] + words[ival-1]);
1187  }
1188
1189  /* Assumes x and y are both canonicalized. */
1190  public static boolean equals (IntNum x, IntNum y)
1191  {
1192    if (x.words == null && y.words == null)
1193      return x.ival == y.ival;
1194    if (x.words == null || y.words == null || x.ival != y.ival)
1195      return false;
1196    for (int i = x.ival; --i >= 0; )
1197      {
1198    if (x.words[i] != y.words[i])
1199      return false;
1200      }
1201    return true;
1202  }
1203
1204  /* Assumes this and obj are both canonicalized. */
1205  public boolean equals (Object   obj)
1206  {
1207    if (obj == null || ! (obj instanceof IntNum))
1208      return false;
1209    return IntNum.equals (this, (IntNum) obj);
1210  }
1211
1212  public static IntNum valueOf (char[] buf, int offset, int length,
1213                int radix, boolean negative)
1214  {
1215    int byte_len = 0;
1216    byte[] bytes = new byte[length];
1217    for (int i = 0;  i < length;  i++)
1218      {
1219    char ch = buf[offset + i];
1220    if (ch == '-')
1221      negative = true;
1222    else if (ch == '_' || (byte_len == 0 && (ch == ' ' || ch == '\t')))
1223      continue;
1224    else
1225      {
1226        int digit = Character.digit(ch, radix);
1227        if (digit < 0)
1228          break;
1229        bytes[byte_len++] = (byte) digit;
1230      }
1231      }
1232    return valueOf (bytes, byte_len, negative, radix);
1233  }
1234
1235  public static IntNum valueOf (String   s, int radix)
1236       throws NumberFormatException  
1237  {
1238    int len = s.length ();
1239    // Testing (len < 2 * MPN.chars_per_word(radix)) would be more accurate,
1240    // but slightly more expensive, for little practical gain.
1241    if (len + radix <= 28)
1242      return IntNum.make (Long.parseLong (s, radix));
1243    
1244    int byte_len = 0;
1245    byte[] bytes = new byte[len];
1246    boolean negative = false;
1247    for (int i = 0;  i < len;  i++)
1248      {
1249    char ch = s.charAt (i);
1250    if (ch == '-')
1251      negative = true;
1252    else if (ch == '_' || (byte_len == 0 && (ch == ' ' || ch == '\t')))
1253      continue;
1254    else
1255      {
1256        int digit = Character.digit (ch, radix);
1257        if (digit < 0)
1258          throw new NumberFormatException  ("For input string: \""+s+'"');
1259        bytes[byte_len++] = (byte) digit;
1260      }
1261      }
1262    return valueOf (bytes, byte_len, negative, radix);
1263  }
1264
1265  public static IntNum valueOf (byte[] digits, int byte_len,
1266                boolean negative, int radix)
1267  {
1268    int chars_per_word = MPN.chars_per_word(radix);
1269    int[] words = new int[byte_len / chars_per_word + 1];
1270    int size = MPN.set_str(words, digits, byte_len, radix);
1271    if (size == 0)
1272      return zero();
1273    if (words[size-1] < 0)
1274      words[size++] = 0;
1275    if (negative)
1276      negate (words, words, size);
1277    return make (words, size);
1278  }
1279
1280  public static IntNum valueOf (String   s)
1281       throws NumberFormatException  
1282  {
1283    return IntNum.valueOf (s, 10);
1284  }
1285
1286  public double doubleValue ()
1287  {
1288    if (words == null)
1289      return (double) ival;
1290    if (ival <= 2)
1291      return (double) longValue ();
1292    if (isNegative ())
1293      return IntNum.neg (this).roundToDouble (0, true, false);
1294    else
1295      return roundToDouble (0, false, false);
1296  }
1297
1298  /** Return true if any of the lowest n bits are one.
1299   * (false if n is negative).  */
1300  boolean checkBits (int n)
1301  {
1302    if (n <= 0)
1303      return false;
1304    if (words == null)
1305      return n > 31 || ((ival & ((1 << n) - 1)) != 0);
1306    int i;
1307    for (i = 0; i < (n >> 5) ; i++)
1308      if (words[i] != 0)
1309    return true;
1310    return (n & 31) != 0 && (words[i] & ((1 << (n & 31)) - 1)) != 0;
1311  }
1312
1313  /** Convert a semi-processed IntNum to double.
1314   * Number must be non-negative.  Multiplies by a power of two, applies sign,
1315   * and converts to double, with the usual java rounding.
1316   * @param exp power of two, positive or negative, by which to multiply
1317   * @param neg true if negative
1318   * @param remainder true if the IntNum is the result of a truncating
1319   * division that had non-zero remainder.  To ensure proper rounding in
1320   * this case, the IntNum must have at least 54 bits.  */
1321  public double roundToDouble (int exp, boolean neg, boolean remainder)
1322  {
1323    // Compute length.
1324    int il = intLength();
1325
1326    // Exponent when normalized to have decimal point directly after
1327    // leading one.  This is stored excess 1023 in the exponent bit field.
1328    exp += il - 1;
1329
1330    // Gross underflow.  If exp == -1075, we let the rounding
1331    // computation determine whether it is minval or 0 (which are just
1332    // 0x0000 0000 0000 0001 and 0x0000 0000 0000 0000 as bit
1333    // patterns).
1334    if (exp < -1075)
1335      return neg ? -0.0 : 0.0;
1336
1337    // gross overflow
1338    if (exp > 1023)
1339      return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1340
1341    // number of bits in mantissa, including the leading one.
1342    // 53 unless it's denormalized
1343    int ml = (exp >= -1022 ? 53 : 53 + exp + 1022);
1344
1345    // Get top ml + 1 bits.  The extra one is for rounding.
1346    long m;
1347    int excess_bits = il - (ml + 1);
1348    if (excess_bits > 0)
1349      m = ((words == null) ? ival >> excess_bits
1350       : MPN.rshift_long (words, ival, excess_bits));
1351    else
1352      m = longValue () << (- excess_bits);
1353
1354    // Special rounding for maxval.  If the number exceeds maxval by
1355    // any amount, even if it's less than half a step, it overflows.
1356    if (exp == 1023 && ((m >> 1) == (1L << 53) - 1))
1357      {
1358    if (remainder || checkBits (il - ml))
1359      return neg ? Double.NEGATIVE_INFINITY : Double.POSITIVE_INFINITY;
1360    else
1361      return neg ? - Double.MAX_VALUE : Double.MAX_VALUE;
1362      }
1363
1364    // Normal round-to-even rule: round up if the bit dropped is a one, and
1365    // the bit above it or any of the bits below it is a one.
1366    if ((m & 1) == 1
1367    && ((m & 2) == 2 || remainder || checkBits (excess_bits)))
1368      {
1369    m += 2;
1370    // Check if we overflowed the mantissa
1371    if ((m & (1L << 54)) != 0)
1372      {
1373        exp++;
1374        // renormalize
1375        m >>= 1;
1376      }
1377    // Check if a denormalized mantissa was just rounded up to a
1378    // normalized one.
1379    else if (ml == 52 && (m & (1L << 53)) != 0)
1380      exp++;
1381      }
1382    
1383    // Discard the rounding bit
1384    m >>= 1;
1385
1386    long bits_sign = neg ? (1L << 63) : 0;
1387    exp += 1023;
1388    long bits_exp = (exp <= 0) ? 0 : ((long)exp) << 52;
1389    long bits_mant = m & ~(1L << 52);
1390    return Double.longBitsToDouble (bits_sign | bits_exp | bits_mant);
1391  }
1392
1393
1394  public Numeric add (Object   y, int k)
1395  {
1396    if (y instanceof IntNum)
1397      return IntNum.add (this, (IntNum) y, k);
1398    if (!(y instanceof Numeric))
1399      throw new IllegalArgumentException   ();
1400    return ((Numeric)y).addReversed (this, k);
1401  }
1402
1403  public Numeric mul (Object   y)
1404  {
1405    if (y instanceof IntNum)
1406      return IntNum.times (this, (IntNum) y);
1407    if (!(y instanceof Numeric))
1408      throw new IllegalArgumentException   ();
1409    return ((Numeric)y).mulReversed (this);
1410  }
1411
1412  public Numeric div (Object   y)
1413  {
1414    if (y instanceof RatNum)
1415      {
1416    RatNum r = (RatNum) y;
1417    return RatNum.make (IntNum.times (this, r.denominator()),
1418                r.numerator());
1419      }
1420    if (! (y instanceof Numeric))
1421      throw new IllegalArgumentException   ();
1422    return ((Numeric)y).divReversed (this);
1423  }
1424
1425  /** Copy the abolute value of this into an array of words.
1426   * Assumes words.length >= (this.words == null ? 1 : this.ival).
1427   * Result is zero-extended, but need not be a valid 2's complement number.
1428   */
1429    
1430  public void getAbsolute (int[] words)
1431  {
1432    int len;
1433    if (this.words == null)
1434      {
1435    len = 1;
1436    words[0] = this.ival;
1437      }
1438    else
1439      {
1440    len = this.ival;
1441    for (int i = len;  --i >= 0; )
1442      words[i] = this.words[i];
1443      }
1444    if (words[len-1] < 0)
1445      negate (words, words, len);
1446    for (int i = words.length;  --i > len; )
1447      words[i] = 0;
1448  }
1449
1450  /** Set dest[0:len-1] to the negation of src[0:len-1].
1451   * Return true if overflow (i.e. if src is -2**(32*len-1)).
1452   * Ok for SRC==dest. */
1453  public static boolean negate (int[] dest, int[] src, int len)
1454  {
1455    long carry = 1;
1456    boolean negative = src[len-1] < 0;
1457    for (int i = 0;  i < len;  i++)
1458      {
1459        carry += ((long) (~src[i]) & 0xffffffffL);
1460        dest[i] = (int) carry;
1461        carry >>= 32;
1462      }
1463    return (negative && dest[len-1] < 0);
1464  }
1465
1466  /** Destructively set this to the negative of x.
1467   * It is OK if x==this.*/
1468  public void setNegative (IntNum x)
1469  {
1470    int len = x.ival;
1471    if (x.words == null)
1472      {
1473    if (len == Integer.MIN_VALUE)
1474      set (- (long) len);
1475    else
1476      set (-len);
1477    return;
1478      }
1479    realloc (len + 1);
1480    if (IntNum.negate (words, x.words, len))
1481      words[len++] = 0;
1482    ival = len;
1483  }
1484
1485  /** Destructively negate this. */
1486  public final void setNegative ()
1487  {
1488    setNegative (this);
1489  }
1490
1491  public static IntNum abs (IntNum x)
1492  {
1493    return x.isNegative () ? neg (x) : x;
1494  }
1495
1496  public static IntNum neg (IntNum x)
1497  {
1498    if (x.words == null && x.ival != Integer.MIN_VALUE)
1499      return make (- x.ival);
1500    IntNum result = new IntNum (0);
1501    result.setNegative (x);
1502    return result.canonicalize ();
1503  }
1504
1505  public Numeric neg ()
1506  {
1507    return IntNum.neg (this);
1508  }
1509
1510  /** Calculates {@code ceiling(log2(this < 0 ? -this : this+1))}.
1511   * See Common Lisp: the Language, 2nd ed, p. 361.
1512   */
1513  public int intLength ()
1514  {
1515    if (words == null)
1516      return MPN.intLength (ival);
1517    else
1518      return MPN.intLength (words, ival);
1519  }
1520
1521  /**
1522   * @serialData If the value is in the range (int)0xC000000 .. 0x7fffffff
1523   * (inclusive) write out the value (using writeInt).
1524   * Otherwise, write (using writeInt) (0x80000000|nwords), where nwords is
1525   * the number of words following.  The words are the minimal
1526   * 2's complement big-endian representation of the value, written using
1527   * writeint.
1528   * (Even if the current value is not canonicalized, the output is).
1529   */
1530  public void writeExternal(ObjectOutput out) throws IOException
1531  {
1532    int nwords = words == null ? 1 : wordsNeeded(words, ival);
1533    if (nwords <= 1)
1534      {
1535    int i = words == null ? ival : words.length == 0 ? 0 : words[0];
1536    if (i >= (int)0xC0000000)
1537      out.writeInt(i);
1538    else
1539      {
1540        out.writeInt(0x80000001);
1541        out.writeInt(i);
1542      }
1543      }
1544    else
1545      {
1546    out.writeInt(0x80000000|nwords);
1547    while (--nwords >= 0)
1548      out.writeInt(words[nwords]);
1549      }
1550    
1551  }
1552 
1553  public void readExternal(ObjectInput in)
1554    throws IOException, ClassNotFoundException  
1555  {
1556    int i = in.readInt();
1557    if (ival <= (int) 0xC0000000)
1558      {
1559    i &= 0x7fffffff;
1560    if (i == 1)
1561      i = in.readInt();
1562    else
1563      {
1564        int[] w = new int[i];
1565        for (int j = i;  --j >= 0; )
1566          w[j] = in.readInt();
1567        words = w;
1568      }
1569      }
1570    ival = i;
1571  }
1572
1573  public Object   readResolve() throws ObjectStreamException
1574  {
1575    return canonicalize();
1576  }
1577
1578  public BigInteger   asBigInteger ()
1579  {
1580    if (words == null || ival <= 2)
1581      return BigInteger.valueOf(longValue());
1582    return new BigInteger  (toString());
1583  }
1584
1585  public BigDecimal   asBigDecimal ()
1586  {
1587    if (words == null)
1588      return new BigDecimal  (ival);
1589    if (ival <= 2)
1590      return BigDecimal.valueOf(longValue());
1591    return new BigDecimal  (toString());
1592  }
1593}
1594
A to Z: JavaDoc & Examples Daily Java News & Articles Open Source Projects Open Source Codes Free Computer Books Remove Frame
Popular Tags