title: Computing large combinations
body: <p>How would you compute a combination such as (100,000 choose 50,000)?</p>
  
  <p>I have tried three different approaches thus far but for obvious reasons each has failed:</p>
  
  <p>1) Dynamic Programming- The size of the array just gets to be so ridiculous it seg faults</p>
  
  <pre><code>unsigned long long int grid[p+1][q+1];
  
  //Initialise x boundary conditions
  for (long int i = 0; i &lt; q; ++i) {
    grid[p][i] = 1;
  }
  
  //Initialise y boundary conditions
  for (long int i = 0; i &lt; p; ++i) {
    grid[i][q] = 1;
  }
  
  
  for (long int i = p - 1; i &gt;= 0; --i) {
    for (long int j = q - 1; j &gt;= 0; --j) {
       grid[i][j] = grid[i+1][j] + grid[i][j+1];
     }
  }
  </code></pre>
  
  <p>2) Brute Force - Obviously calculating even 100! isn't realistic</p>
  
  <pre><code>unsigned long long int factorial(long int n)
  {
    return (n == 1 || n == 0) ? 1 : factorial(n - 1) * n;
  }
  </code></pre>
  
  <p>3) Multiplicative Formula- I'm unable to store the values they are just so large </p>
  
  <pre><code>const int gridSize = 100000; //say 100,000
  unsigned long long int paths = 1;
  
  for (int i = 0; i &lt; gridSize; i++) {
      paths *= (2 * gridSize) - i;
      paths /= i + 1;
  }
  
  // code from (http://www.mathblog.dk/project-euler-15/)
  </code></pre>
  
  <p>If it helps for context the aim of this is to solve the "How many routes are there through an m×n grid" problem for large inputs. Maybe I am miss-attacking the problem?</p>