//<pre>
//  Integer arithmetic functions (copyright 1999 Information Disciplines, Inc.)

//  This pseudo-class contains various numerical functions that take
//  integer parameters or return integer results.  To support the widest
//  range, we use long integers for all numbers, except those having a
//  restricted range.  To avoid anomalies, we don't use unsigned numbers.

//  A few of the functions duplicate those in the java.lang.Math pseudo class. 
//  They are included here to provide consistency to the users 

public class IntegerFunction {

//   1. Integer-valued functions of one integer:
//   ------------------------------------------

 public static
   long abs (final long n)                 //  Absolute value
        {return  n >= 0 ? n : -n;}

 static                                    //  Number of digits   
   short ndigits(final long n, final int base)
        {long nx = abs(n);
         short ctr;
         for (ctr = 1; nx >= base; nx /=base, ++ctr);
         return ctr;}
 static
   short ndigits(final long n) {return ndigits(n,10);}


//  2.  Integer-valued functions of two integers
//  --------------------------------------------

 public static
   long gcd (final long m, final long n)   //  Greatest common divisor
        {return  m % n == 0 ? n : gcd(n, m%n);}

 public static
   long lcm (final long m, final long n)   //  Least common multiple
        {return  m * (n/gcd(m, n));}

 public static
   long max (final long m, final long n)   //  Maximum
        {return  m > n ? m : n;}

 public static
   long min (final long m, final long n)   //  Minimum
        {return  m < n ? m : n;}


//  3.  String-valued functions of one or two integers:
//  --------------------------------------------------

//  Convert integer to string by base
//  ---------------------------------

 public static
   String toString(final long n, final int base)
        {int     size     = ndigits(n,base) + (n < 0 ? 1 : 0);
         long    nx       = abs(n);
         char[]  result = new char[size];
         if (n < 0) result[0]= '-';        //  Attach prefix sign
         int posn = size-1;

//  Assemble characters right to left

         do  result[posn--] = DIGIT_TABLE.charAt((int)(nx % base));
             while((nx /= base) > 0);
         return new String(result);
        }
  static                                
         final String DIGIT_TABLE = "0123456789ABCDEF";
 public static String toString(long n) {return toString(n,10);}

//  Convert integer to Roman numerals
//  ---------------------------------

  public static String toRoman (int arg)
  {char[] unit = {'I','X','C','M'};      //  Table of characters
   char[] five = {'V','L','D'};          //     used in Roman numerals

   char[]  result = new char[16];    //  Accumulator for results
   short   resultPosn = 15;          //  Right-to-left index
   short   digit;                    //  Current digit
   boolean five_sw;                  //  Cur. digit needs initial five
   int n = Math.abs(arg);
   short   posn;

   if   (n >= 4000)                  //  Test for within acceptable range
   return toString(n,10);            //  No -- just return Arabic numerals

   for  (posn = 0;  n > 0;  posn++, n /= 10)
      {digit = (short)(n % 10);
       if  (digit == 9) {result[resultPosn--] = unit[posn+1]; digit = 1;}
       if  (digit == 4) {result[resultPosn--] = five[posn];   digit = 1;}

       five_sw = (digit >= 5);
       digit %= 5;                      //  Number of units in this position
       while (digit-- > 0)  result[resultPosn--] = unit[posn];
       if  (five_sw)        result[resultPosn--] = five[posn];
      }
   return new String(result).substring(resultPosn+1);
}


//   Integer to English 
//   ------------------

//    1.  Internal function to convert 3-digit portion: 
//    -------------------------------------------------

 private  static String toEng999 (int k)
 {final   String[] units = {""   ,"one"    ,"two"      ,"three"   ,"four",
                           "five","six"    ,"seven"    ,"eight"   ,"nine",
                            "ten","eleven" ,"twelve"   ,"thirteen","fourteen",
                        "fifteen","sixteen","seventeen","eighteen","nineteen"};
  final   String[] tens =  {""   , ""      ,"twenty"   ,"thirty"  ,"forty" ,
                          "fifty","sixty"  ,"seventy"  ,"eighty"  ,"ninety"};
 
  int    u =  k % 10;                    //  Separate the
  int    c =  k / 100;                   //     values of the 
  int    tu=  k % 100;                   //        three digits
  int    t = (tu-u) / 10;

  String result = (c == 0)  ? ""         //  Insert hundreds portion
                            : units[c] + " hundred" 
                            + (tu > 0 ? " " : "");
 
  return result += (tu < 20) ? units[tu] //  Insert tens and units portion
                             : tens [t]             
                               + ( u > 0 ? "-" : "") 
                               + units[u];
}


//    2.  Function called by the user
//    -------------------------------

 static public String toEnglish (long arg)
 {final  String[] grpName ={""," thousand"," million"," billion",
                               " trillion"," quadrillion"," quintillion"};
 
 String result = "";                        
 long n = abs(arg); 
 for (int   group_ctr=0; n>0; ++group_ctr) //  Process each group of 3-digits
     {int   group = (int) (n % 1000);
      n /= 1000;     //      right to left
      if  (group != 0)                     //    For each non-zero group
         result = toEng999(group)          //      Insert group value
         + grpName[group_ctr]              //         and group denomination
         +(result.length() > 0 ? ", " : "")//      Insert separating comma
         + result;                         //      Append rightmost portion  
     }
 return arg != 0 ? result : "zero";
}


//  4.  Other functions
//  -------------------

//  Decompose integer into prime factors
//  ------------------------------------

//  Upon return result[0] contains the number of factors (0 if N is 0), and
//  result[1] . . . result[result[0]] contain the factors in ascending order.

  public static long[] primeFactors(long N)
     {long [] fctr = new long[64];       //  Result array
      long n = Math.abs(N);              //  Guard against negative

      short fctrIndex = 0;

      if (n > 0) {                       //  Guard against zero

//  First do special cases 2 and 3
                                  
        while (n % 2 == 0)  {fctr[++fctrIndex] = 2; n /= 2;}
        while (n % 3 == 0)  {fctr[++fctrIndex] = 3; n /= 3;}

//  Then every 6n-1 and 6n+1 until the divisor exceeds the square root
//  of the current quotient.  NOTE:  Some trial divisors will be
//  non-primes, e.g. 25, 35, 49, 55.  They have no effect, however,
//  since their prime factors will already have been tried.

        for (int k = 5; k*k <= n; k += 6) 
          for (int dvsr = k; dvsr <= k+2; dvsr+=2)
            { while (n % dvsr == 0)
                 {fctr[++fctrIndex] = dvsr;  n /= dvsr;}
            }

        if (n > 1) fctr[++fctrIndex] = n; //  Store final factor, if any
       }

      fctr[0] = fctrIndex;                //  Store number of factors
      return fctr;
     }



//  Integer power of a real number (recursive implementation)
//  ------------------------------

 public static double power(double x, int n)    //  (Overflow is possible)
    {return  n <  0   ? 1 / power(x,-n)         //  Negative power 
          :  n == 0   ? 1                       //  Base
          :  n == 1   ? x                       //    cases
          :  n%2 == 0 ? (x = power(x, n/2)) * x //  Even power
          :              x * power(x, n-1);}    //  Odd power
}
//</pre>