Skip to main content
replaced http://codegolf.stackexchange.com/ with https://codegolf.stackexchange.com/
Source Link

Missed opportunity for code reuse

Compare

static BigInteger factorial(final BigInteger number) {
    BigInteger ret = BigInteger.ONE;

    for (BigInteger i = BigInteger.valueOf(2L);
            i.compareTo(number) <= 0; 
            i = i.add(BigInteger.ONE)) {
        ret = ret.multiply(i);
    }

    return ret;
}

with

    BigInteger numerator = BigInteger.ONE;

    for (BigInteger i = n.subtract(k).add(BigInteger.ONE); 
            i.compareTo(n) <= 0; 
            i = i.add(BigInteger.ONE)) {
        numerator = numerator.multiply(i);
    }

They could easily be refactored into a method

static BigInteger prod(final BigInteger from, final BigInteger to) {
    BigInteger ret = BigInteger.ONE;

    for (BigInteger i = from;
            i.compareTo(to) <= 0; 
            i = i.add(BigInteger.ONE)) {
        ret = ret.multiply(i);
    }

    return ret;
}

I've left the special cases for you to decide how you would want to handle them.


Unnecessary calculation

DynamicProgrammingBinomialCoefficientComputer currently admits two optimisations other than those mentioned in earlier answers.

  1. The recurrence is \$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\$. At no point do you need values of \$\binom{m}{r}\$ for \$r > k\$.

  2. \$\binom{n}{k} = \binom{n}{n-k}\$, so if you exploit the first optimisation you can also ensure that \$k \le \frac n 2\$.

The combination can reduce the number of values calculated from \$O(n^2)\$ to \$O(n \min(k, n-k))\$.


A different approach

You can avoid BigInteger divisions and still get the speed benefit of multiplication by first computing the prime factorisation of \$\binom{n}{k}\$ in ints and then multiplying them in BigInteger. One approach would be Kummer's theorem; another is to simply compute the prime factorisations of \$n!\$, \$k!\$, and \$(n-k)!\$ and subtract appropriately. See e.g. this answerthis answer on a sister site.

Missed opportunity for code reuse

Compare

static BigInteger factorial(final BigInteger number) {
    BigInteger ret = BigInteger.ONE;

    for (BigInteger i = BigInteger.valueOf(2L);
            i.compareTo(number) <= 0; 
            i = i.add(BigInteger.ONE)) {
        ret = ret.multiply(i);
    }

    return ret;
}

with

    BigInteger numerator = BigInteger.ONE;

    for (BigInteger i = n.subtract(k).add(BigInteger.ONE); 
            i.compareTo(n) <= 0; 
            i = i.add(BigInteger.ONE)) {
        numerator = numerator.multiply(i);
    }

They could easily be refactored into a method

static BigInteger prod(final BigInteger from, final BigInteger to) {
    BigInteger ret = BigInteger.ONE;

    for (BigInteger i = from;
            i.compareTo(to) <= 0; 
            i = i.add(BigInteger.ONE)) {
        ret = ret.multiply(i);
    }

    return ret;
}

I've left the special cases for you to decide how you would want to handle them.


Unnecessary calculation

DynamicProgrammingBinomialCoefficientComputer currently admits two optimisations other than those mentioned in earlier answers.

  1. The recurrence is \$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\$. At no point do you need values of \$\binom{m}{r}\$ for \$r > k\$.

  2. \$\binom{n}{k} = \binom{n}{n-k}\$, so if you exploit the first optimisation you can also ensure that \$k \le \frac n 2\$.

The combination can reduce the number of values calculated from \$O(n^2)\$ to \$O(n \min(k, n-k))\$.


A different approach

You can avoid BigInteger divisions and still get the speed benefit of multiplication by first computing the prime factorisation of \$\binom{n}{k}\$ in ints and then multiplying them in BigInteger. One approach would be Kummer's theorem; another is to simply compute the prime factorisations of \$n!\$, \$k!\$, and \$(n-k)!\$ and subtract appropriately. See e.g. this answer on a sister site.

Missed opportunity for code reuse

Compare

static BigInteger factorial(final BigInteger number) {
    BigInteger ret = BigInteger.ONE;

    for (BigInteger i = BigInteger.valueOf(2L);
            i.compareTo(number) <= 0; 
            i = i.add(BigInteger.ONE)) {
        ret = ret.multiply(i);
    }

    return ret;
}

with

    BigInteger numerator = BigInteger.ONE;

    for (BigInteger i = n.subtract(k).add(BigInteger.ONE); 
            i.compareTo(n) <= 0; 
            i = i.add(BigInteger.ONE)) {
        numerator = numerator.multiply(i);
    }

They could easily be refactored into a method

static BigInteger prod(final BigInteger from, final BigInteger to) {
    BigInteger ret = BigInteger.ONE;

    for (BigInteger i = from;
            i.compareTo(to) <= 0; 
            i = i.add(BigInteger.ONE)) {
        ret = ret.multiply(i);
    }

    return ret;
}

I've left the special cases for you to decide how you would want to handle them.


Unnecessary calculation

DynamicProgrammingBinomialCoefficientComputer currently admits two optimisations other than those mentioned in earlier answers.

  1. The recurrence is \$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\$. At no point do you need values of \$\binom{m}{r}\$ for \$r > k\$.

  2. \$\binom{n}{k} = \binom{n}{n-k}\$, so if you exploit the first optimisation you can also ensure that \$k \le \frac n 2\$.

The combination can reduce the number of values calculated from \$O(n^2)\$ to \$O(n \min(k, n-k))\$.


A different approach

You can avoid BigInteger divisions and still get the speed benefit of multiplication by first computing the prime factorisation of \$\binom{n}{k}\$ in ints and then multiplying them in BigInteger. One approach would be Kummer's theorem; another is to simply compute the prime factorisations of \$n!\$, \$k!\$, and \$(n-k)!\$ and subtract appropriately. See e.g. this answer on a sister site.

Source Link
Peter Taylor
  • 24.5k
  • 1
  • 49
  • 94

Missed opportunity for code reuse

Compare

static BigInteger factorial(final BigInteger number) {
    BigInteger ret = BigInteger.ONE;

    for (BigInteger i = BigInteger.valueOf(2L);
            i.compareTo(number) <= 0; 
            i = i.add(BigInteger.ONE)) {
        ret = ret.multiply(i);
    }

    return ret;
}

with

    BigInteger numerator = BigInteger.ONE;

    for (BigInteger i = n.subtract(k).add(BigInteger.ONE); 
            i.compareTo(n) <= 0; 
            i = i.add(BigInteger.ONE)) {
        numerator = numerator.multiply(i);
    }

They could easily be refactored into a method

static BigInteger prod(final BigInteger from, final BigInteger to) {
    BigInteger ret = BigInteger.ONE;

    for (BigInteger i = from;
            i.compareTo(to) <= 0; 
            i = i.add(BigInteger.ONE)) {
        ret = ret.multiply(i);
    }

    return ret;
}

I've left the special cases for you to decide how you would want to handle them.


Unnecessary calculation

DynamicProgrammingBinomialCoefficientComputer currently admits two optimisations other than those mentioned in earlier answers.

  1. The recurrence is \$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}\$. At no point do you need values of \$\binom{m}{r}\$ for \$r > k\$.

  2. \$\binom{n}{k} = \binom{n}{n-k}\$, so if you exploit the first optimisation you can also ensure that \$k \le \frac n 2\$.

The combination can reduce the number of values calculated from \$O(n^2)\$ to \$O(n \min(k, n-k))\$.


A different approach

You can avoid BigInteger divisions and still get the speed benefit of multiplication by first computing the prime factorisation of \$\binom{n}{k}\$ in ints and then multiplying them in BigInteger. One approach would be Kummer's theorem; another is to simply compute the prime factorisations of \$n!\$, \$k!\$, and \$(n-k)!\$ and subtract appropriately. See e.g. this answer on a sister site.