logoalt Hacker News

ogogmad • today at 6:17 PM • 2 replies • view on HN

  me@localhost:~> bc
  d=1; for(i=21; i < 41; i++){d *= i;}; print d; print "\n";
  335367096786357081410764800000
  n = 1; for(i = 1; i < 21; i++){n *= i;}; print n; print "\n";
  2432902008176640000
  d/n;
  137846528820
I couldn't start Python for some reason, so I went 1337 and used BC, which comes preinstalled in every Unix-like OS. BC has a surprising advantage here since 40!/20! cannot be represented as a 64-bit integer since its value exceeds 2^64. That said, BC's stdlib does not provide the factorial function* - so I had to resort to for-loops instead.

* - What it does contain is sine, cosine, exponential, log, arctan, and Bessel J (?!?!?!?!)

Replies

aesthesia • today at 7:32 PM

Just noting that Python natively handles integers larger than the machine word size since version 2.5, so this would have worked in Python as well.

➕ show 1 reply
qsort • today at 6:46 PM

You don't need space for 40!/20!, for example:

  let ans = 1
  for (let i=1; i<21; ++i) {
    ans *= (41 - i)
    ans /= i
  }
The same idea can be trivially tweaked to compute any binomial coefficient without ever storing an integer greater than the final result.
➕ show 1 reply