Aprog/src/net/sourceforge/aprog/tools/MathTools.java

   1 /*
   2  *  The MIT License
   3  *
   4  *  Copyright 2011 Codist Monk.
   5  *
   6  *  Permission is hereby granted, free of charge, to any person obtaining a copy
   7  *  of this software and associated documentation files (the "Software"), to deal
   8  *  in the Software without restriction, including without limitation the rights
   9  *  to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10  *  copies of the Software, and to permit persons to whom the Software is
  11  *  furnished to do so, subject to the following conditions:
  12  *
  13  *  The above copyright notice and this permission notice shall be included in
  14  *  all copies or substantial portions of the Software.
  15  *
  16  *  THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17  *  IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18  *  FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19  *  AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20  *  LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21  *  OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  22  *  THE SOFTWARE.
  23  */
  24
  25 package net.sourceforge.aprog.tools;
  26
  27 import java.util.ArrayList;
  28 import java.util.List;
  29
  30 /**
  31  * @author codistmonk (creation 2011-06-11)
  32  */
  33 public final class MathTools {
  34
  35     /**
  36      * @throws IllegalInstantiationException To prevent instantiation
  37      */
  38     private MathTools() {
  39         throw new IllegalInstantiationException();
  40     }
  41
  42     // TODO Add tests
  43
  44     private static final long[] FIRST_FACTORIALS = {
  45         1L, 1L, 2L, 6L, 24L, 120L, 720L, 5040L, 40320L, 362880L, 3628800L
  46     };
  47
  48     /**
  49      * @param a
  50      * <br>Range: any long
  51      * @param b
  52      * <br>Range: any long
  53      * @return
  54      * <br>Range: any long
  55      */
  56     public static final long gcd(final long a, final long b) {
  57         return b == 0 ? a : gcd(b, a % b);
  58     }
  59
  60     /**
  61      * @param a
  62      * <br>Range: any long
  63      * @param b
  64      * <br>Range: any long
  65      * @return
  66      * <br>Range: any long
  67      */
  68     public static final long lcm(final long a, final long b) {
  69         return a * b / gcd(a, b);
  70     }
  71
  72     /**
  73      * @param n
  74      * <br>Range: any long
  75      * @return
  76      * <br>Range: <code>[1 .. Long.MAX_VALUE]</code>
  77      */
  78     public static final long factorial(final long n) {
  79         return n < FIRST_FACTORIALS.length ? FIRST_FACTORIALS[(int) n] : nPk(n, n);
  80     }
  81
  82     /**
  83      * @param n
  84      * <br>Range: any long
  85      * @param k
  86      * <br>Range: any long
  87      * @return <code>n!/(n-k)!</code>
  88      * <br>Range: <code>[0 .. Long.MAX_VALUE]</code>
  89      */
  90     public static final long nPk(final long n, final long k) {
  91         if (n < k) {
  92             return 1;
  93         }
  94
  95         long result = 1;
  96
  97         for (long i = n - k + 1; i <= n; ++i) {
  98             result *= i;
  99         }
 100
 101         return result;
 102     }
 103
 104     /**
 105      * "gamma nk" or "n multichoose k".
 106      *
 107      * @param n
 108      * <br>Range: any long
 109      * @param k
 110      * <br>Range: any long
 111      * @return <code>nCk(n + k - 1, k)</code>
 112      * <br>Range: <code>[0 .. Long.MAX_VALUE]</code>
 113      */
 114     public static final long multichoose(final long n, final long k) {
 115         return nCk(n + k - 1, k);
 116     }
 117
 118     /**
 119      * "n choose k".
 120      *
 121      * @param n
 122      * <br>Range: any long
 123      * @param k
 124      * <br>Range: any long
 125      * @return <code>n!/(k!(n-k)!)</code>
 126      * <br>Range: <code>[0 .. Long.MAX_VALUE]</code>
 127      */
 128     public static final long nCk(final long n, final long k) {
 129         List<Long> values = new ArrayList<Long>((int) n + 1);
 130         List<Long> newValues = new ArrayList<Long>((int) n + 1);
 131
 132         values.add(1L);
 133
 134         for (long i = 1; i <= n; ++i) {
 135             newValues.clear();
 136
 137             for (long j = 0; j <= i; ++j) {
 138                 newValues.add(get(values, j - 1) + get(values, j));
 139             }
 140
 141             final List<Long> tmp = values;
 142             values = newValues;
 143             newValues = tmp;
 144         }
 145
 146         return get(values, k);
 147     }
 148
 149     /**
 150      * @param values
 151      * <br>Not null
 152      * @param index
 153      * <br>Range: any long
 154      * @return
 155      * <br>Range: any long
 156      */
 157     private static final long get(final List<Long> values, final long index) {
 158         return index < 0 || values.size() <= index ? 0 : values.get((int) index);
 159     }
 160
 161 }