I'm using GMP to calculate very large factorials (e.g. 234234!). Is there any way of knowing, before one does the calculation, how many digits long the result will (or might) be?
+1
A:
Yes, see Stirling approximation
It says n! ~= sqrt(2*Pi*n)*(n/e)^n. To get the number of digits, take 1+log(n!)/log(10).
Eric Bainville
2009-07-11 07:37:50
to clarify - 1+log(n)/log(10) would give the number of digits of n, not of n!
grifaton
2009-07-11 07:41:20
thanks, I fixed it
Eric Bainville
2009-07-11 07:47:52
it will require to calculate n! any ways :), that is not what boost wants to do
Ratnesh Maurya
2009-07-11 07:50:55
As Rats remarked on my previously identical reply, calculating n^n is not really feasible either. It quickly goes beyond what even a double-precision float can hold, and using Java BigInteger, calculation time on my (admittedly slow) system were 30s for 100,000, 130s for 200,000 - you can see where that's going.
Michael Borgwardt
2009-07-11 08:57:57
+11
A:
You can transform Stirling's approximation formula using simple logarithmic math to get you the number of digits:
n! ~ sqr(2*pi*n) * (n/e)^n
log10(n!) ~ log10(2*pi*n)/2 + n*log10(n/e)
Hardware float math is sufficient for this, which makes it lightning fast.
Michael Borgwardt
2009-07-11 07:38:44
I just remembered that I actually once faced exactly the same problem and how I solved it
Michael Borgwardt
2009-07-11 08:06:24
Probably worth mentioning that Stirling's formula gives an *under*-estimate of n!. For most practical purposes where you need to know the number of digits, an under-estimation is the fast lane to a buffer overrun. So you probably need to do a bit of investigation and jiggering to get an *over*-estimate, but I think the Wikipedia page contains enough information.
Steve Jessop
2010-03-10 12:51:37
+1
A:
it would be
nlog(n) - n + log(n(1 + 4n(1 + 2n)))/6 + log(pi)/2
see topic "rate of growth" @ http://en.wikipedia.org/wiki/Factorial Srinivasa Ramanujan method
Ratnesh Maurya
2009-07-11 07:59:29
+1
A:
Well about four people have mentioned Stirling so... another option is a LUT storing the number of digits for each of the first N factorials. Assuming 4 bytes for the integer and 4 bytes for the number of digits, you could store the first 1,000,000 factorials in around 8MB.
James D
2009-07-11 08:01:47
You still have to calculate the values for the table though. And I doubt you want to spend a few years or decades doing, which is what you would, calculating it straightforward.
Michael Borgwardt
2009-07-11 08:50:50
Well, you'd calculate all N factorials from 1! to N! in a single consecutive pass. So you'd be looking at N total multiplications and at some point you'd bog down in heavy-number arithmetic but should this take decades? What's the correlation between N and processing time?
James D
2009-07-11 10:12:52
This isn't the most efficient method, but by Knuth, every programmer should know enough math to think of it almost immediately.
Michael Borgwardt
2009-07-11 08:16:35
except me, of course, who doesn't know enough math (or maths, as we call it in this country.)
boost
2009-07-17 06:39:05