def binomialCoefficient()

in core/src/main/scala/com/spotify/featran/transformers/PolynomialExpansion.scala [141:198]

• 40 lines of code
• 11 McCabe index (conditional complexity)

  def binomialCoefficient(n: Int, k: Int): Long = {
    checkBinomial(n, k)
    if (n == k || k == 0) {
      1L
    } else if (k == 1 || k == n - 1) {
      n.toLong
    } else if (k > n / 2) {
      // Use symmetry for large k
      binomialCoefficient(n, n - k)
    } else {
      // We use the formula
      // (n choose k) = n! / (n-k)! / k!
      // (n choose k) == ((n-k+1)*...*n) / (1*...*k)
      // which could be written
      // (n choose k) == (n-1 choose k-1) * n / k
      var result = 1L
      if (n <= 61) {
        // For n <= 61, the naive implementation cannot overflow.
        var i = n - k + 1
        var j = 1
        while (j <= k) {
          result = result * i / j
          i += 1
          j += 1
        }
      } else if (n <= 66) {
        // For n > 61 but n <= 66, the result cannot overflow,
        // but we must take care not to overflow intermediate values.
        var i = n - k + 1
        var j = 1
        while (j <= k) {
          // We know that (result * i) is divisible by j,
          // but (result * i) may overflow, so we split j:
          // Filter out the gcd, d, so j/d and i/d are integer.
          // result is divisible by (j/d) because (j/d)
          // is relative prime to (i/d) and is a divisor of
          // result * (i/d).
          val d = gcd(i, j)
          result = (result / (j / d)) * (i / d)
          i += 1
          j += 1
        }
      } else {
        // For n > 66, a result overflow might occur, so we check
        // the multiplication, taking care to not overflow
        // unnecessary.
        var i = n - k + 1
        var j = 1
        while (j <= k) {
          val d = gcd(i, j)
          result = mulAndCheck(result / (j / d), (i / d).toLong)
          i += 1
          j += 1
        }
      }
      result
    }
  }