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
* - What it does contain is sine, cosine, exponential, log, arctan, and Bessel J (?!?!?!?!)
You don't need space for 40!/20!, for example:
The same idea can be trivially tweaked to compute any binomial coefficient without ever storing an integer greater than the final result.Good point. But what if `i` does not divide `ans` evenly? I suppose you could use floats and then round.
It always divides it evenly, that's why it works.
After the i-th iteration of the for loop, ans will contain n!/((n-i)!i!) which is exactly \binom{n}{i}, an integer.
Technically "ans" can grow above the final result in my example, but even that could be fixed if one really wants (e.g. i must divide either ans or n-i, you play a bit with divmod to figure out which division you do first.)
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.
And does it quite fast too:
https://www.wilfred.me.uk/blog/2014/10/20/the-fastest-bigint...
I think BC's features are equivalent to:
- Python's native integer handling, which already has no size limit.
- PLUS part of the Decimal module in Python's stdlib: BC's floats are DECIMAL by default, not binary.
- PLUS an implementation of Bessel's J function, while neglecting Bessel's K.
- Some features for base conversion using `ibase` and `obase`. So, I suppose you can output numbers to base 60. [EDIT: Correction from earlier: ibase is allowed to be at most 16, while POSIX allows for the maximum value of obase to be at least 99, which therefore does allow for formatting output to base 60.]