Re:Calculating integer factorials in constant time, taking a...
by kleiba on Tuesday December 15, 2015 @09:33AM
(#10737911)
Interestingly, I was just doing some calculations over the weekend involving large factorials. Naturally, I used a "big integer" library to overcome the limitations of the hardware architecture. That anyone outside a class-room would be willing to restrict themselves to 32 or 64 bit for the largest integers thus seems contrived: of course, dealing with factorials will quickly get you past your system's word size, but that's what arbitrary-length integer libs are for.
[ Parent
| on HN ]
Re:Calculating integer factorials in constant time, taking a...
by a1k0n on Tuesday December 15, 2015 @10:46AM
(#10738398)
Depends what you need them for... In statistics, factorials appear in normalizing constants for various distributions (e.g., Poisson) and often you're working with floating point log-probabilities, in which case you can use the log-gamma function (built into most math libraries) to replace the log factorial. And that's a 64-bit float, no bignums needed.
Re:Calculating integer factorials in constant time, taking a...
by jeffwass on Tuesday December 15, 2015 @01:18PM
(#10739388)
But in what situation would you actually need an arbitrary precision library for general statistics? Ie, in what situations would any reasonable approximations not suffice for reasonable real-world precision?
Eg, Stirlings approximation for ln(n!) should serve fairly well for moderate and above values of n. And knowing your statistical distribution at large n you can likely find a decent distribution from a discrete case requiring n! into a continuous one, eg Gaussian.
Re:Calculating integer factorials in constant time, taking a...
by a1k0n on Wednesday December 16, 2015 @12:41AM
(#10742605)
You wouldn't, for statistics. That's my point.
Only in number theory problems do you actually need bignums for factorials, and those are usually toy problems or modulo some big prime.
I don't know of any actual applications where you need to compute the bignum factorial. I'm curious what the GP needed it for.