Number of digits in N!

[jmcgill]

Hello.

Is there a method for computing the number of digits, in a given numeric
base, of N factorial, without actually computing the factorial?

For example, 8! has 5 digits in base 10; 10! has 7 digits in base 10.
Is there a way to compute that information without actually evaluating
the factorial?

 

[Frita Pauling]

Hello.

Is there a method for computing the number of digits, in a given numeric
base, of N factorial, without actually computing the factorial?

For example, 8! has 5 digits in base 10; 10! has 7 digits in base 10.
Is there a way to compute that information without actually evaluating
the factorial?

how accurate do you want to be?

 

[Willem]

jmcgill wrote:
) Is there a method for computing the number of digits, in a given numeric
) base, of N factorial, without actually computing the factorial?
)
) For example, 8! has 5 digits in base 10; 10! has 7 digits in base 10.
) Is there a way to compute that information without actually evaluating
) the factorial?

I think the number of digits (base 10) in 10! should be:

sum (1<= x <= 10 | log10(x))

With appropriate rounding, of course.


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

 

[Pascal Bourguignon]

Is there a method for computing the number of digits, in a given numeric
base, of N factorial, without actually computing the factorial?

For example, 8! has 5 digits in base 10; 10! has 7 digits in base 10.
Is there a way to compute that information without actually evaluating
the factorial?

The function "number of digits" is a logarithm function, so computing
it is equivalent to compute the product.

Therefore, the answer to your question would be: NO.


On the other hand, you can use Stirling's formula to approximate the
log of factorial, that is, the number of digits.

http://mathworld.wolfram.com/StirlingsApproximation.html

If you want the digits in base 10, just divide by ln(10):

factdigits(n) = ln(n!)/ln(10)

factdigits(n) = ceiling((n+½)ln(n)-n+½ln(2π))/ln(10)

 

[Stuart]

Is there a method for computing the number of digits, in a given numeric
base, of N factorial, without actually computing the factorial?

For example, 8! has 5 digits in base 10; 10! has 7 digits in base 10.
Is there a way to compute that information without actually evaluating
the factorial?

Depends on how accurate you need the answer to be and over what range!

For small ranges it would probably be easiest and quickest to simply look-up
the answer.

For large ranges you could consider Stirling's Approximation:
ln(n!) approx = n * ln(n) - n

You could combine this with the rules for changing the base of logarithms,
then round up the result to get an approximation to the number of digits!

You could consider other approximations (see Wolfram's web site).

You could combine a look-up for a sub-range (where the approximation is
fairly inaccurate) with a computation based on an approximation formula.

Regards

 

[Ancient_Hacker]

Hello.

Is there a method for computing the number of digits, in a given numeric
base, of N factorial, without actually computing the factorial?

For example, 8! has 5 digits in base 10; 10! has 7 digits in base 10.
Is there a way to compute that information without actually evaluating
the factorial?

Pretty easy, because the product of integers is the sum of their logs.

so 1 * 2 * 3 * 4 * 5 ... is equal to exp( log(1) + log(2) + log(3)
+ log(4) + log(5) )

and the number of digits is log10(x), so take the log base 10 of the
above expression.

But we still have a loop in there, I suspect you want a non-loop
expression.

For that you could try stirling's approximatuion (see wikipedia).

 

[Mitch]

Is there a method for computing the number of digits, in a given numeric
base, of N factorial, without actually computing the factorial?

Depends on what you mean by 'actually'. So ostensibly, yes, but with a
caveat.

As others have noted, the function you are looking for is simply

floor(log(n!)) + 1 (the # of digits in base b, assuming all logs
base b)

and using Stirling's approximation to the factorial this can be
computed using:

ceiling( (n+1/2) log n - n log e + 1/2 log 2 pi + log(1+ a bunch of
very small stuff))

that last annoying term can be ignored because of the ceiling. (at
least this works numerically for n>=2 for all bases except 2 and 6
where there is only one off by one error each).

The caveat is that in computing logs and e and pi (to enough digits),
one may being enough 'work' that ends up being just as much as needed
to compute the factorial and log in the original (that is, in using the
computation without the explicit use of factorial at the top, there
might be a hidden computation of factorial or, more cryptically, enough
bit manipulations have been performed that are comparable to those
inolved in the original.

To this question, I don't know the answer (I don't know if computing
the log of the factorial is of the same computational complexity as
computing the factorial itself).

An upper bound of O(log log n M(n log n)) (where M is the complexity
of integer multiplication) is given by:
Borwein, Peter B. On the complexity of calculating factorials. J.
Algorithms 6 (1985), no. 3, 376--380

but this says nothing (at least not to me) about the complexity of
computing the log of a factorial.

Mitch

 

[Bart Goddard]

Hello.

Is there a method for computing the number of digits, in a given numeric
base, of N factorial, without actually computing the factorial?

For example, 8! has 5 digits in base 10; 10! has 7 digits in base 10.
Is there a way to compute that information without actually evaluating
the factorial?

As others have said, you want to compute sum_k=1^N ln(k)/ln(b) where
b is your favorite base (and add one to it.) This sum is bounded
above by

int(ln x/ln b, x=2..N) and below by int(ln(x-1)/ln b,x=2..N). The
difference between these integrals is a bound on the error
of approximating your sum by one of the integrals. Since
the integrals are easy to evaluate, you have a good
approximation.

E.g., 100! has 158 digits, but int(ln x/ln b, x=2..100)+1
= 157.57....

(The error diverges, however. But it does so extremely slowly.)

Bart

 

[Pascal Bourguignon]

jmcgill wrote:
) Is there a method for computing the number of digits, in a given numeric
) base, of N factorial, without actually computing the factorial?
)
) For example, 8! has 5 digits in base 10; 10! has 7 digits in base 10.
) Is there a way to compute that information without actually evaluating
) the factorial?

I think the number of digits (base 10) in 10! should be:

sum (1<= x <= 10 | log10(x))

With appropriate rounding, of course.

Of course, but this sum (before rounding) is 10! (log10(n!) actually,
but it's the same) You have computed the factorial when it was asked
to avoid it!

--
__Pascal Bourguignon__ http://www.informatimago.com/

NEW GRAND UNIFIED THEORY DISCLAIMER: The manufacturer may
technically be entitled to claim that this product is
ten-dimensional. However, the consumer is reminded that this
confers no legal rights above and beyond those applicable to
three-dimensional objects, since the seven new dimensions are
"rolled up" into such a small "area" that they cannot be
detected.

 

[James McGill]

Depends on how accurate you need the answer to be and over what range!

I was looking for a way to format the output of a "Pascal's Triangle" of
an arbitrary number of rows, centering each row, without computing all
the rows before formatting, so coarse approximations are fine.

The factorials involved become very huge very quickly, and means that
computing an arbitrary row requires a scalar type much larger than the
elements in that row.

Thanks to everyone who clued me in on Stirling's formula; it means I
could implement my idea without needing any sort of bignum approach.

This is not homework; the idea of generating Pascal's Triangle was some
other person's homework, I just did it for fun (preparing for an ACM
coding competition), and realized I'd like to center each row without
having to compute the maximum width by computing the full range of the
rows before outputting anything.

Because Stirling's formula works in reasonable values, it is possible to
compute the approximate number of characters in the Nth row of the
Triangle (at least I think so).

Maybe there's a simpler way that I had not considered.

Thanks again,

James

 

[James McGill]

Of course, but this sum (before rounding) is 10! (log10(n!) actually,
but it's the same) You have computed the factorial when it was asked
to avoid it!

I should have clarified my reason for considering the problem.

Computing factorials quickly exceeds the limit of a given scalar
datatype. I wanted to format a representation of a "Pascal's Triangle"
in such a way that the low-order rows are centered with respect to later
rows, without computing the entire set of rows. Since evaluating the
factorials directly, in order to populate the last row in the set,
quickly grows beyond the size of the datatypes that could represent the
same row, I thought there might be a way to measure an arbitrary row
according to the number of characters it would need, and use that
information for formatting each row that is computed.

There might be simpler ways to do this, that I'm not smart enough to
see. I will try the Stirling method and see where it leads.

 

[Pascal Bourguignon]

I was looking for a way to format the output of a "Pascal's Triangle"
of an arbitrary number of rows, centering each row, without computing
all the rows before formatting, so coarse approximations are fine.

The factorials involved become very huge very quickly, and means that
computing an arbitrary row requires a scalar type much larger than the
elements in that row.

Thanks to everyone who clued me in on Stirling's formula; it means I
could implement my idea without needing any sort of bignum approach.

This is not homework; the idea of generating Pascal's Triangle was
some other person's homework, I just did it for fun (preparing for an
ACM coding competition), and realized I'd like to center each row
without having to compute the maximum width by computing the full
range of the rows before outputting anything.

Because Stirling's formula works in reasonable values, it is possible
to compute the approximate number of characters in the Nth row of the
Triangle (at least I think so).

Maybe there's a simpler way that I had not considered.

Well, for the maximum width, I used (ceiling (log (pascal n (truncate n 2)) 10))

Of course, it doesn't matter that I call (pascal n (truncate n 2))
because I memoized the function and it is really computed only once.


I fail to see where n! enters the scene though...


(defun pascal (i j)
"Return the value of the entry (i,j) of Pascal's Triangle.
+----------> i
| 1 1 1 1 1
| 1 2 3 4
| 1 3 6
| 1 4
| 1
v
j
"
(if (or (<= i 1) (<= j 1))
1
(+ (pascal i (1- j)) (pascal (1- i) j))))


(asdfos 'asdf:load-op :memoize)
(memoize:memoize-function 'pascal :key (function list) :test (function equal))

(defun print-pascal-triangle (n &key top-down-p)
"Prints Pascal's Triangle up to line n"
(if top-down-p
(loop
with width = (ceiling (log (pascal n (truncate n 2)) 10))
for line from 1 to n
do (loop
initially (format t "~%~VA"
(truncate (* (/ (- n line) 2) (1+ width))) "")
for column from 1 below line
do (format t " ~V@A" width (pascal (- line column) column)))
finally (format t "~%"))
(loop
with width = (ceiling (log (pascal n n) 10))
for i from 1 to n
do (loop
for j from 1 to n
do (format t " ~V@A" width (pascal i j))
finally (format t "~%")))))

--
__Pascal Bourguignon__ http://www.informatimago.com/

IMPORTANT NOTICE TO PURCHASERS: The entire physical universe,
including this product, may one day collapse back into an
infinitesimally small space. Should another universe subsequently
re-emerge, the existence of this product in that universe cannot be
guaranteed.

 

[Pascal Bourguignon]

I should have clarified my reason for considering the problem.

Computing factorials quickly exceeds the limit of a given scalar
datatype.

What do you mean?

(ext:! 300)
-->
306057512216440636035370461297268629388588804173576999416776741259476533176716867465515291422477573349939147888701726368864263907759003154226842927906974559841225476930271954604008012215776252176854255965356903506788725264321896264299365204576448830388909753943489625436053225980776521270822437639449120128678675368305712293681943649956460498166450227716500185176546469340112226034729724066333258583506870150169794168850353752137554910289126407157154830282284937952636580145235233156936482233436799254594095276820608062232812387383880817049600000000000000000000000000000000000000000000000000000000000000000000000000

(time (progn (setf r (ext:! 100000)) (integer-length r)))
Real time: 1.338735 sec.
Run time: 1.296081 sec.
Space: 4789392 Bytes
GC: 6, GC time: 0.096005 sec.
--> 1516705
(integer-length is ceiling o log2)

I wanted to format a representation of a "Pascal's
Triangle" in such a way that the low-order rows are centered with
respect to later
rows, without computing the entire set of rows. Since evaluating the
factorials directly, in order to populate the last row in the set,
quickly grows beyond the size of the datatypes that could represent
the same row, I thought there might be a way to measure an arbitrary
row according to the number of characters it would need, and use that
information for formatting each row that is computed.

There might be simpler ways to do this, that I'm not smart enough to
see. I will try the Stirling method and see where it leads.

You can compute pascal as a quotient of factorials, but it's easier to
compute it as sums. Therefore you don't need factorials.

Watch formula (3) in:
http://mathworld.wolfram.com/PascalsTriangle.html

--
__Pascal Bourguignon__ http://www.informatimago.com/

HEALTH WARNING: Care should be taken when lifting this product,
since its mass, and thus its weight, is dependent on its velocity
relative to the user.

 

[luiroto]

Hello.

Is there a method for computing the number of digits, in a given numeric
base, of N factorial, without actually computing the factorial?

Yes. For base 10 :

Let Pi = 3.14159265358979323846

C = 1 / log(10) log = Neperian logarithm

K = log(2*Pi) / 2

L = N.(log(N) - 1 ) + log(N) / 2 + 1/(12.N) + K N > 3

Number of digits of N! = [C. L ] +1 [ ] means floor of

Example: Number of digits of 100! = 158

Ludovicus

 

[Dik T. Winter]

> jmcgill wrote:
>

....

[Using Sterling:]

> ceiling( (n+1/2) log n - n log e + 1/2 log 2 pi + log(1+ a bunch of
> very small stuff))

Assuming log to the base required. However, it is better to first
calculate base e and change base at the end. (log_b(k) = log(k)/log(b).)

Mathworld gives the simpler:
n log n - n log + 1
I think the approximation you give is an extended approximation from the
original (and log(1 + ...) should be replaced by (1 + ...) * log e).

> The caveat is that in computing logs and e and pi (to enough digits),

You do not need e, but you need pi. The needed precision is small
2 pi is about 6, so even with base 2 (which gives the largest log
for 2 pi), the log is less than 3.

> one may being enough 'work' that ends up being just as much as needed
> to compute the factorial and log in the original (that is, in using the
> computation without the explicit use of factorial at the top, there
> might be a hidden computation of factorial or, more cryptically, enough
> bit manipulations have been performed that are comparable to those
> inolved in the original.

Wrong. The only place were you need precision is in log n. But even
for the largest double precision number the base 2 log (the largest)
is just over 1000 (on IEEE). The standard logarithm function is good
enough for that. But of course, if you want a reasonable approximation
of the number of digits in that factorial you need a logarithm that is
precise in 1024 bits... For numbers in the range to 2 ** 32, the
logarithm is good enough to get a fairly good approximation.

> To this question, I don't know the answer (I don't know if computing
> the log of the factorial is of the same computational complexity as
> computing the factorial itself).

The computation of the log of the factorial is just about as complex
as the computation of the factorial itself. But you do not need the
log of the factorial to approximate the number of digits, you need
only an approximation of it, and that is much less complex.

 

[Jon Slaughter]

Hello.

Is there a method for computing the number of digits, in a given numeric
base, of N factorial, without actually computing the factorial?

For example, 8! has 5 digits in base 10; 10! has 7 digits in base 10.
Is there a way to compute that information without actually evaluating
the factorial?

since log(x) = y is equivilent to b^y = x we see that y "measures" the
number of factors of b that x contains. (off by 1 though)

if b represents the numerical base that x is "in" then we are realy counting
the digits of x

e.g., suppose x = 283 in base 10

then log[10](283) ~= 2.4517

you will notice that log[10](10^y) = y. and since 10^y "paritions" the
digits in the sense that all numbers between 0 and 10^1 have the same
digits, and in general all numbers between 10^y and 10^(y+1) have the same
digits.

So as many have pointed out ciel(log(x)) returns the number of digits.


now you want to count the number of digits of n!

hence you just plug in:

ceil(log(n!))

now since n! = n*(n-1)*..*3*2*1 and log(x*y) = log(x) + log*(y) we
have

#digits of n! = ceil(sum(log(k),k=1..n))

some people say you are computing n! behind the scenes or something but in
reality you are not. You are computing a sum of logs. Sure its not
necessarily easier to compute the log of something but if your trying to
find the number of digits of 10000! then this method will easily work
compared to trying to actually compute 10000!. Ofcourse it would be better
to use sterlings approximation or a combination of this and sterlings(as
sterlings is an asymptotic approximation).

Now, you can also reduce the run time of this sum by noting that ln(n) +
ln(2n) = 2*ln(n) + ln(2) and so on. i.e., you split up the sum into parts
that you can handle easily and quickly. If, say, n is divisible by 10(which
is very easy to check) then you can reduce the sum by a factor of 10. In
essense if you have a factorization you can use this to your advantage.

suppose n = 2^y1*3^y2*5^y3...

then log(n) = y1*log(y1) + y2*log(3) + y3*log(5) + ...

Ofcourse the representation doesn't even have to be a prime factorization.
You could end up using euclids algorithm here help I suppose... and if n is
a large prime then your out of luck.

But I suppose you could always add 1 to n if, say, n is odd and then compute
the number of digits and then figure out how many extra digits were added:

i.e.

log((n+1)!) = log(n+1) + log(n!)

and you'll notice that log(n!) counts the number of digits of n! which is
what we are looking for(well close enough).

i.e., we can see that the number of digit that (n+1)! has compared to n! is
simply log(n+1)(ofcourse theres the problem with the ceil but)

I'm sure theres many tricks one can do and maybe the sterling approximation
is the best but it depends on what exactly you are trying to do.

 

[shohreh.harris]

...

[Using Sterling:]

ceiling( (n+1/2) log n - n log e + 1/2 log 2 pi + log(1+ a bunch of
very small stuff))

Assuming log to the base required. However, it is better to first
calculate base e and change base at the end. (log_b(k) = log(k)/log(b).)

sure, that makes sense. I was thinking too literally.

Mathworld gives the simpler:
n log n - n log + 1

I think the approximation you give is an extended approximation from the
original (and log(1 + ...) should be replaced by (1 + ...) * log e).


You do not need e, but you need pi. The needed precision is small
2 pi is about 6, so even with base 2 (which gives the largest log
for 2 pi), the log is less than 3.

again, good idea.

Wrong. The only place were you need precision is in log n.

(and also log_b e, surely? (but of course we expect b to be much less
than n))
the simplification above makes that clear now.

But even

for the largest double precision number the base 2 log (the largest)
is just over 1000 (on IEEE). The standard logarithm function is good
enough for that. But of course, if you want a reasonable approximation
of the number of digits in that factorial you need a logarithm that is
precise in 1024 bits... For numbers in the range to 2 ** 32, the
logarithm is good enough to get a fairly good approximation.

even though I was thinking theoretically (for n being way outside of
IEEE standards, say infinite precision), one could still consider
smallish n like 2000 whose factorial is only mildly outside. and so one
does need to do without a direct factorial computation (and even in
infinite precision one would want to avoid needless calculation of huge
numbers even if possible).

The computation of the log of the factorial is just about as complex
as the computation of the factorial itself. But you do not need the
log of the factorial to approximate the number of digits, you need
only an approximation of it, and that is much less complex.

all I was getting at was that I highly suspect that log n! is easy to
compute, much easier than n!, but I just don't know how to go about
-proving- it.

Mitch

 

[Pascal Bourguignon]

all I was getting at was that I highly suspect that log n! is easy to
compute, much easier than n!, but I just don't know how to go about
-proving- it.

log(a*b)=log(a)+log(b)

It's simplier to do additions than multiplications.

log(n!) = log(1)+log(2)+...+log(n)

n! = e^(log(1)+log(2)+...+log(n))

But doing n-1 multiplications (even on big nums) might be much more
easier than doing n log and one exp.

 

[Proginoskes]

Of course, but this sum (before rounding) is 10! (log10(n!) actually,
but it's the same) You have computed the factorial when it was asked
to avoid it!

Oh, really?

log 1 = 0
log 2 = 0.3010299957
log 3 = 0.4771212547
log 4 = 0.6020599914
log 5 = 0.6989700043
log 6 = 0.7781512504
log 7 = 0.8450980400
log 8 = 0.9030899871
log 9 = 0.9542425094
log 10 = 1.0

(All are accurate except for possibly to the last digit.)

The sum is 6.559763033 (last 2 digits possibly wrong, but the rest are
correct).

The answer is 7.

Where did I use the fact that 10! = 3,628,800?

--- Christopher Heckman

 

[Proginoskes]

The function "number of digits" is a logarithm function, so computing
it is equivalent to compute the product.

Therefore, the answer to your question would be: NO.

Oh, really?

log 1 = 0
log 2 = 0.3010299957
log 3 = 0.4771212547
log 4 = 0.6020599914
log 5 = 0.6989700043
log 6 = 0.7781512504
log 7 = 0.8450980400
log 8 = 0.9030899871
log 9 = 0.9542425094
log 10 = 1.0

(All are accurate except for possibly to the last digit.)

The sum is 6.559763033 (last 2 digits possibly wrong, but the rest are
correct).

The answer is 7.

Where did I use the fact that 10! = 3,628,800?

--- Christopher Heckman