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]

"jmcgill" <jm*****@email.arizona.eduwrote in message
news:GS9Vg.766$rS.181@fed1read05...

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]

jmcgill <jm*****@email.arizona.eduwrites:

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/Stirlin...oximation.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)

--
__Pascal Bourguignon__ http://www.informatimago.com/
The mighty hunter
Returns with gifts of plump birds,
Your foot just squashed one.

[Stuart]

"jmcgill" <jm*****@email.arizona.eduwrote in message
news:GS9Vg.766$rS.181@fed1read05...

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
--
Stuart

[Ancient_Hacker]

jmcgill wrote:

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]

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?

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]

jm*****@email.arizona.edu wrote:

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

--
The man without a .sig

[Pascal Bourguignon]

Willem <wi****@stack.nlwrites:

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]

Stuart wrote:

"jmcgill" <jm*****@email.arizona.eduwrote in message
news:GS9Vg.766$rS.181@fed1read05...

>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!

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

[Pascal Bourguignon]

James McGill <jm*****@email.arizona.eduwrites:

Stuart wrote:

>"jmcgill" <jm*****@email.arizona.eduwrote in message
news:GS9Vg.766$rS.181@fed1read05...

>>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!

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))))
(asdf:oos '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.

[James McGill]

Pascal Bourguignon wrote:

> 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!

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]

James McGill <jm*****@email.arizona.eduwrites:

Pascal Bourguignon wrote:

>> 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!

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)
-->
30605751221644063603537046129726862938858880417357 69994167767412594765331767168674655152914224775733 49939147888701726368864263907759003154226842927906 97455984122547693027195460400801221577625217685425 59653569035067887252643218962642993652045764488303 88909753943489625436053225980776521270822437639449 12012867867536830571229368194364995646049816645022 77165001851765464693401122260347297240663332585835 06870150169794168850353752137554910289126407157154 83028228493795263658014523523315693648223343679925 45940952768206080622328123873838808170496000000000 00000000000000000000000000000000000000000000000000 000000000000000

(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]

jmcgill wrote:

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]

In article <11*********************@b28g2000cwb.googlegroups. com"Mitch" <ma*****@gmail.comwrites:

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?

....

[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.
--
dik t. winter, cwi, kruislaan 413, 1098 sj amsterdam, nederland, [phone]
home: bovenover 215, 1025 jn amsterdam, nederland; http://www.cwi.nl/~dik/

[Jon Slaughter]

"jmcgill" <jm*****@email.arizona.eduwrote in message
news:GS9Vg.766$rS.181@fed1read05...

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[b](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[b](x)) returns the number of digits.
now you want to count the number of digits of n!

hence you just plug in:

ceil(log[b](n!))

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

#digits of n! = ceil(sum(log[b](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[b](n) = y1*log[b](y1) + y2*log[b](3) + y3*log[b](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[b]((n+1)!) = log[b](n+1) + log[b](n!)

and you'll notice that log[b](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[b](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]

Dik T. Winter wrote:

IMitch writes:

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?

...

[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).

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.

again, good idea.

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.

(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).

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.

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]

sh************@gmail.com writes:

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.
--
__Pascal Bourguignon__ http://www.informatimago.com/

"By filing this bug report you have challenged the honor of my
family. Prepare to die!"

[Proginoskes]

Pascal Bourguignon wrote:

Willem <wi****@stack.nlwrites:

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!

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]

Pascal Bourguignon wrote:

jmcgill <jm*****@email.arizona.eduwrites:

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.

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

[Klueless]

"Klueless" <kl******@worldnet.att.netwrote in message news:b_********************@bgtnsc05-news.ops.worldnet.att.net...

"jmcgill" <jm*****@email.arizona.eduwrote in message news:GS9Vg.766$rS.181@fed1read05...

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

For a different base B, other than 10, use
1+Floor(Log(Gamma(N+1))/Log(B))

[Phil Carmody]

Pascal Bourguignon <pj*@informatimago.comwrites:

Willem <wi****@stack.nlwrites:

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!

Wrong.

Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.

[Phil Carmody]

Pascal Bourguignon <pj*@informatimago.comwrites:

jmcgill <jm*****@email.arizona.eduwrites:

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.

Wrong.

Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.

[dcorbit]

jmcgill wrote:

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?

/*
The only redeeming value to this algorithm is that it can calculate the
number of digits of very long input values. E.g.:
Enter a value to calculate the number of digits for the factorial:
100000
That factorial is 456574 digits
*/
#include <math.h>
#include <stdlib.h>
#include <stdio.h>

char string[32767];

int main(void)
{
long l,
index;
double sum = 0;

puts("Enter a value to calculate the number of digits for the
factorial:");
fflush(stdout);
fgets(string, sizeof string, stdin);
l = atol(string);
if (l < 1) {
puts("That value is too small. Enter a number >= 1.");
exit(EXIT_FAILURE);
}
for (index = 1; index <= l; index++) {
sum += log10((double) index);
}

printf("That factorial is %.0f digits\n", floor(sum)+1.0);
return 0;
}

[Stuart]

"James McGill" <jm*****@email.arizona.eduwrote in message
news:eg***********@hisatsinom.cs.arizona.edu...

Stuart wrote:

>"jmcgill" <jm*****@email.arizona.eduwrote in message
news:GS9Vg.766$rS.181@fed1read05...

>>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!

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.

As the number of digits grows quite quickly, such "formatting" for the
latter rows is going to give very long rows. It will also make early rows,
containing 1-2 digit numbers look quite barren.

Depending on the challenge you are setting yourself, you might want to
consider setting an upper bound for the number of digits, then for numbers
that exceed this, performing some 'boxed' line wrapping. This, in itself,
may provide some more interesting programming challenges:
- How will you co-ordinate wrapped number images for each entry on the
Triangle row?
- Do you need to know, when you start the row, how many output lines it
will occupy,
or can you build them up as you go along?

Regards
--
Stuart

of achieving

[jmcgill]

Stuart wrote:

As the number of digits grows quite quickly, such "formatting" for the
latter rows is going to give very long rows. It will also make early rows,
containing 1-2 digit numbers look quite barren.

Of course. It was just an experiment, as I found the exercise of
"creating the triangle" far too easy, and then found that of "formatting
in a single pass" to be beyond my understanding of numbers. I had no
intention of actually formatting a 6144-row Pascal's Triangle for
printing on 100-meter-wide paper :-)

[luiroto]

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?

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

10^3! = 2568
10^4! = 35660
10^5! = 456574
10^6! = 5565709
10^7! = 65657060
Ludovicus

[CBFalconer]

Proginoskes wrote:

Pascal Bourguignon wrote:

>Willem <wi****@stack.nlwrites:

>>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!

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?

Ingenious. Here is a simple demo program for the method.

#include <stdio.h>
#include <math.h /* log10, ceil */
#include <stdlib.h/* strtol */

int main(int argc, char **argv)
{
int i, last;
double logten, sum;

sum = 0;
if (2 != argc) puts("Usage: factsize maxarg");
else {
last = strtol(argv[1], NULL, 10);
for (i = 1; i <= last; i++) {
logten = log10(i);
sum += logten;
printf("%d %f %f %d\n", i, logten, sum, (int)ceil(sum));
}
}
return 0;
}

--
Some informative links:
<news:news.announce.newusers
<http://www.geocities.com/nnqweb/>
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/>

[John Smith]

jmcgill wrote:

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?

/* Stirling's approximation for n! & ln(n!) */
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#define PI 3.141592653589793
long double stirling(long double n);
long double lnstirling(long double n);

int main(int argc, char *argv[])
{
long double n, sa, lnsa, pi;

if(argc != 2) exit(EXIT_FAILURE);
pi = PI;
n = strtold(argv[1], NULL);
sa = stirling(n);
lnsa = lnstirling(n);
printf("%.Lf! = %.2Lf\n", n, sa);
printf("ln(%.Lf!) = %.8Lf\n", n, lnsa);

return 0;
}

/* Stirling's approximation */
long double stirling(long double n)
{
long double t1, t2, t3;

t1 = sqrt(2.0 * PI * n);
t2 = pow(n, n);
t3 = exp(-n + 1.0 / 12.0 / n);

return t1 * t2 * t3;
}

/* ln(stirling) */
long double lnstirling(long double n)
{
return (n +.5) * log(n) - n + log(2.0 * PI) / 2.0;
}

*** NOT PART OF THE PROGRAM ABOVE ***

/* Return the natural log of gamma(x) */
double log_gamma(double x)
{
int idx, sizep;
double r, g;
double p[] = {1.000000000190015,
76.18009172947146,
-86.50532032941677,
24.01409824083091,
-1.231739572450155,
1.208650973866179E-3,
-5.395239384953E-6};
r = p[0];
g = 5.;
sizep = sizeof(p) / sizeof(*p);

for (idx = 1; idx < sizep; idx++)
{
r += p[idx] / (x + idx);
}

return log(r) + log(atan(1) * 8) / 2 - log(x) +
log(x + g + .5) * (x + .5) - (x + g + .5);
}

[Proginoskes]

CBFalconer wrote:

Proginoskes wrote:

Pascal Bourguignon wrote:

Willem <wi****@stack.nlwrites:
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!

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?

Ingenious. [...]

Only relatively speaking. Evidently Pascal Bourguignon has not taken a
course involving logarithms (which are taught in College Algebra here
in the USA).

--- Christopher Heckman

[Pascal Bourguignon]

"Proginoskes" <CC*******@gmail.comwrites:

CBFalconer wrote:

>Proginoskes wrote:

Pascal Bourguignon wrote:
Willem <wi****@stack.nlwrites:
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!

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?

Ingenious. [...]

Only relatively speaking. Evidently Pascal Bourguignon has not taken a
course involving logarithms (which are taught in College Algebra here
in the USA).

No, I learned logarithms in France. And in France,
log(3628800)=6.55976303287679375...
which is the sum you've computed.

Since there is an isomorphism between (R+*,*) and (R,+), computing
log(f(x)) or f(x) is the same thing. That's why we use the
logarithms: to be able to compute complex multiplications doing
instead simple additions.

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

"This machine is a piece of GAGH! I need dual Opteron 850
processors if I am to do battle with this code!"

[Logan Shaw]

Pascal Bourguignon wrote:

"Proginoskes" <CC*******@gmail.comwrites:

>CBFalconer wrote:

>>Proginoskes wrote:
Pascal Bourguignon wrote:

>>>>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?

>>Ingenious. [...]

>Only relatively speaking. Evidently Pascal Bourguignon has not taken a
course involving logarithms (which are taught in College Algebra here
in the USA).

No, I learned logarithms in France. And in France,
log(3628800)=6.55976303287679375...
which is the sum you've computed.

Since there is an isomorphism between (R+*,*) and (R,+), computing
log(f(x)) or f(x) is the same thing.

I think Proginoskes' point was that if you understood logarithms, you
would have thought to apply them by taking the sum of logarithms
rather than the logarithm of products. It is true that they are
mathematically equivalent, but they are not computationally equivalent.
For one thing, some languages have limits on the size of integers.
But there is another issue as well. It is often ignored in the analysis
of the running time of algorithms, but the amount of time it takes to
perform arithmetic operations is dependent on the size of the values
(or of the types chosen to represent those values). No computer has
an adder with an infinite number of bits; if you start adding values
larger than the adder, you must loop. And similarly for other operations
like multiplication.

Since the function number_of_digits(factorial(n)) grows approximately
linearly, that is a significant issue. It would not be very good
problem-solving to ignore the issue just because both methods are
mathematically equivalent. Assuming you care about efficiency, that is.

- Logan

[Pascal Bourguignon]

Logan Shaw <ls**********@austin.rr.comwrites:

Pascal Bourguignon wrote:

>"Proginoskes" <CC*******@gmail.comwrites:

>>CBFalconer wrote:
Proginoskes wrote:
Pascal Bourguignon wrote:

>>>>>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?

>>>Ingenious. [...]

>>Only relatively speaking. Evidently Pascal Bourguignon has not taken a
course involving logarithms (which are taught in College Algebra here
in the USA).

>No, I learned logarithms in France. And in France,
log(3628800)=6.55976303287679375...
which is the sum you've computed.
Since there is an isomorphism between (R+*,*) and (R,+), computing
log(f(x)) or f(x) is the same thing.

I think Proginoskes' point was that if you understood logarithms, you
would have thought to apply them by taking the sum of logarithms
rather than the logarithm of products. It is true that they are
mathematically equivalent, but they are not computationally equivalent.

The question wasn't to compute the result in a computationally
efficient way, it was to do it without computing the factorial.

My point is that summing the logs IS computing the factorial.

How could I make this point if I didn't understood logarithms?
--
__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.

[CBFalconer]

Pascal Bourguignon wrote:

>

.... snip ...

>
The question wasn't to compute the result in a computationally
efficient way, it was to do it without computing the factorial.

My point is that summing the logs IS computing the factorial.

How could I make this point if I didn't understood logarithms?

I disagree. The factorial is an exact integral value. By their
very nature, the logs, and a final pow call (if any, to compute an
approximate factorial) are inexact approximations. The point of
the logs to base 10 is that they directly represent the digits
required for the representation.

--
Some informative links:
<news:news.announce.newusers
<http://www.geocities.com/nnqweb/>
<http://www.catb.org/~esr/faqs/smart-questions.html>
<http://www.caliburn.nl/topposting.html>
<http://www.netmeister.org/news/learn2quote.html>
<http://cfaj.freeshell.org/google/>

[luiroto]

lu*****@yahoo.com wrote:

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?

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

1000! = 2568
10000! = 35660
100000! = 456574
1000000! = 5565709
10000000! = 65657060

[Logan Shaw]

Pascal Bourguignon wrote:

Logan Shaw <ls**********@austin.rr.comwrites:

>Pascal Bourguignon wrote:

>>Since there is an isomorphism between (R+*,*) and (R,+), computing
log(f(x)) or f(x) is the same thing.

>I think Proginoskes' point was that if you understood logarithms, you
would have thought to apply them by taking the sum of logarithms
rather than the logarithm of products. It is true that they are
mathematically equivalent, but they are not computationally equivalent.

The question wasn't to compute the result in a computationally
efficient way, it was to do it without computing the factorial.

My point is that summing the logs IS computing the factorial.

How could I make this point if I didn't understood logarithms?

True enough, it shows a knowledge of logarithms. But I don't think
it's a valid argument about computation.

Computing log(fact(n)) is not equivalent to computing fact(n). Yes,
an isomorphism exists, and that's noteworthy, but computation is
about transforming information. If you haven't done the whole
transformation, you haven't done the whole computation. There's an
isomorphism between a set of messages and the set of encrypted
versions of those messages as well. Does that mean encrypting,
transmitting, and decrypting is equivalent to just encrypting,
transmitting, and storing the encrypted messages?

For that matter, here are two sets that are isomorphic. The
first set is this:

{
( 1, "(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))" ),
( 2, "(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))" ),
( 3, "(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))" ),
( 4, "(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))" ),
( 5, "(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))" )
}

And the second set:

{ 1, 2, 6, 24, 120 }

If I gave the input { 1, 2, 3, 4, 5 } to two programs, and if one computed
the first set while the other computed the second, would you say that the
two programs had computed the same thing? I wouldn't.

So, I would say that computing log(fact(n)) is not equivalent to
computing fact(n). It's close, but there is one step at the end
that has been left out, so it's different.

- Logan

[Pascal Bourguignon]

Logan Shaw <ls**********@austin.rr.comwrites:

True enough, it shows a knowledge of logarithms. But I don't think
it's a valid argument about computation.

Computing log(fact(n)) is not equivalent to computing fact(n). Yes,
an isomorphism exists, and that's noteworthy, but computation is
about transforming information. If you haven't done the whole
transformation, you haven't done the whole computation. There's an
isomorphism between a set of messages and the set of encrypted
versions of those messages as well. Does that mean encrypting,
transmitting, and decrypting is equivalent to just encrypting,
transmitting, and storing the encrypted messages?

If the problem asked to avoid constructing the message in the first
place, yes.

For that matter, here are two sets that are isomorphic. The
first set is this:

{
( 1, "(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))" ),
( 2, "(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))" ),
( 3, "(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))" ),
( 4, "(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))" ),
( 5, "(defun fact (n) (if (eq n 0) 1 (* n (fact (- n 1)))))" )
}

And the second set:

{ 1, 2, 6, 24, 120 }

If I gave the input { 1, 2, 3, 4, 5 } to two programs, and if one computed
the first set while the other computed the second, would you say that the
two programs had computed the same thing? I wouldn't.

You're confusing the representation that might be outputed with the
internal structures of the program. Both programs could print the
same characters, and you wouldn't know any better.

So, I would say that computing log(fact(n)) is not equivalent to
computing fact(n). It's close, but there is one step at the end
that has been left out, so it's different.

The external representation is not the same as the way the
implementation work.

For all I know, Intel might store in the physical registers the
logarithms of my numbers.

(defstruct num sign value)

(defun num (n)
(cond ((= 0 n) (make-num :sign 0 :value 0))
((< 0 n) (make-num :sign 1 :value (log n)))
(t (make-num :sign -1 :value (log (- n))))))

(defun plus (a b)
;; Black box implementation. The hardware might do it differently!
(num (+ (* (num-sign a) (exp (num-value a)))
(* (num-sign b) (exp (num-value b))))))

(defun times (a b)
;; Black box implementation. The hardware might do it differently!
(make-num :sign (* (num-sign a) (num-sign b))
:value (+ (num-value a) (num-value b))))

(defmethod print-object ((self num) stream)
;; Black box implementation. The hardware might do it differently!
;; Notably, we could implement the usual algorithm, dividing by 10
;; (ie. the hardware would just subtract the log of 10).
(format t " #.(num ~D) " (* (num-sign self) (exp (num-value self))))
self)

[181](num 2)
#.(num 2.0)
[182](num 3)
#.(num 3.0)
[183](times (num 2) (num 3))
#.(num 6.0)
[184](plus (num 2) (num 3))
#.(num 5.0)
[185]>

As a programmer, I don't know and I don't want to know how the
hardware implements my base abstractions. As far as I'm concerned, it
can use Church's Numerals, Peano's or logarithms.
As long as there's an isomorphism, there's an abstraction. That's why
you don't need to do the final exponentiation to have computed the
factorial.
Note that the algorithmic complexities we evaluate as programmers are
expressed in terms of these abstractions. How many add, how many
multiplications, how many memory accesses. We never consider
(theorically) the complexity of the underlying hardware. This is the
job of the electronicians at Intel's.

(By the way, the floating point representation is close to a logarithm
representation. The integral part is already stored as the logarithm
of the number, only the mantissa is not entirely converted).

--
__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.

[Proginoskes]

Pascal Bourguignon wrote:

Logan Shaw <ls**********@austin.rr.comwrites:

Pascal Bourguignon wrote:

"Proginoskes" <CC*******@gmail.comwrites:

CBFalconer wrote:
Proginoskes wrote:
Pascal Bourguignon wrote:

>>>>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?

>>Ingenious. [...]

>Only relatively speaking. Evidently Pascal Bourguignon has not taken a
course involving logarithms (which are taught in College Algebra here
in the USA).

No, I learned logarithms in France. And in France,
log(3628800)=6.55976303287679375...
which is the sum you've computed.
Since there is an isomorphism between (R+*,*) and (R,+), computing
log(f(x)) or f(x) is the same thing.

I think Proginoskes' point was that if you understood logarithms, you
would have thought to apply them by taking the sum of logarithms
rather than the logarithm of products. It is true that they are
mathematically equivalent, but they are not computationally equivalent.

The question wasn't to compute the result in a computationally
efficient way, it was to do it without computing the factorial.

Which I did. Again, the number 3,628,800 does not appear anywhere in my
calculations. Therefore, I calculated the number 7 "without computing
the factorial".

My point is that summing the logs IS computing the factorial.

The fact that log(10!) is the same as my sum means I got the right
number. However, I did not need the value of 10! to calculate it.

How could I make this point if I didn't understood logarithms?

Then you should know that the point of logarithms is that you can
calculate the value of a difficult expression without calculating that
expression itself. If I wanted to calculate
log(sqrt(2)), I can do this without calculating the square root of 2 by
calculating
0.5 log(2) instead.

"Calculating" a value r means that you have some approximation to r at
some point.

--- Christopher Heckman

[Andrey Tarasevich]

Proginoskes wrote:

>...
The question wasn't to compute the result in a computationally
efficient way, it was to do it without computing the factorial.

Which I did. Again, the number 3,628,800 does not appear anywhere in my
calculations. Therefore, I calculated the number 7 "without computing
the factorial".
...

The only reason you are having this argument is that you forgot to agree
on the terminology.

You are saying that "number 3,628,800 does not appear anywhere" in your
calculations. How do you know that? May I remind you that '3,628,800' is
_not_ really a number. We call it a "number" in everyday conversations
because in most everyday contexts calling '3,628,800' a "number" is not
a big error. It is an error, but, once again, everybody understands what
we are really trying to say.

Now, in this discussion the difference becomes more important. So, what
'3,628,800' really is, if it not a "number"? '3,628,800' is a _decimal_
_representation_ of a number. Numbers are mathematical abstractions that
cannot be seen, smelt or touched. The only things about numbers that we
can see, smell or touch are particular _representations_ of numbers.

What you are really claiming above is that there's no decimal
representation of 10! an any point in your program. Fine, I'd be more
surprised it it was there. You can also safely claim that there's no
binary representation of 10! at any point in your program. That'd make
more sense, but that still misses the point. Because anyone can claim
that your sum of logarithms is noting less than an exotic representation
of 10! and, therefore, you are calculating 10! in your code. You just
choose an obscure representation for the result in order to throw the
wolves off your trail.

--
Best regards,
Andrey Tarasevich

[Jon Slaughter]

"Andrey Tarasevich" <an**************@hotmail.comwrote in message
news:12*************@news.supernews.com...

Proginoskes wrote:

>>...
The question wasn't to compute the result in a computationally
efficient way, it was to do it without computing the factorial.

Which I did. Again, the number 3,628,800 does not appear anywhere in my
calculations. Therefore, I calculated the number 7 "without computing
the factorial".
...

The only reason you are having this argument is that you forgot to agree
on the terminology.

You are saying that "number 3,628,800 does not appear anywhere" in your
calculations. How do you know that? May I remind you that '3,628,800' is
_not_ really a number. We call it a "number" in everyday conversations
because in most everyday contexts calling '3,628,800' a "number" is not
a big error. It is an error, but, once again, everybody understands what
we are really trying to say.

Now, in this discussion the difference becomes more important. So, what
'3,628,800' really is, if it not a "number"? '3,628,800' is a _decimal_
_representation_ of a number. Numbers are mathematical abstractions that
cannot be seen, smelt or touched. The only things about numbers that we
can see, smell or touch are particular _representations_ of numbers.

What you are really claiming above is that there's no decimal
representation of 10! an any point in your program. Fine, I'd be more
surprised it it was there. You can also safely claim that there's no
binary representation of 10! at any point in your program. That'd make
more sense, but that still misses the point. Because anyone can claim
that your sum of logarithms is noting less than an exotic representation
of 10! and, therefore, you are calculating 10! in your code. You just
choose an obscure representation for the result in order to throw the
wolves off your trail.

What you say might be true but its entirely off the point. It doesn't matter
what he calls it because the fact of the matter is computing the factorial
of a whatever is not needed when taking the log of it. This is the whole
point about logs. They convert multiplication to addition. Factorials are
multiplication and a log of it allows you to compute the same result with
additions. Additions are much less expensive(in terms of speed and memory)
in todays processors and so one only has to assume that.

Also the fact of the matter is that we are wanting the numerical
representation of the number of digits of n! and not n! itself. Its not the
case that you have to compute any factorial to do this just like its not the
case that you have to compute the first n digits of pi to compute the next
one. You can compute the 10^43234 digit of pi without knowing any others.

If your algorithm to count the digits of n! blindly and ignorantly computes
n! first then its just ignorance and not a single thing you can say about it
will change that. No amount of semantics can change the fact that on a
processor that works in binary the amount of space and the time needed to
calculate n! is exponential.. but it can be proved that the other methods
stated are not.

In essense even though log(n!) mathematically is equivilent to
sum(log(k),k=2..n) they are not algorithmically equivilent atleast on todays
processors.

[Pascal Bourguignon]

"Proginoskes" <CC*******@gmail.comwrites:

Which I did. Again, the number 3,628,800 does not appear anywhere in my
calculations. Therefore, I calculated the number 7 "without computing
the factorial".

Of course you did! "6.559763033" and "3,628,800" and "3628800" are
representations for the same number, "factorial of ten". The first is
a written representation of the number on the logarithmic scale, while
the others are different representations of the number on linear
scales. But they're both but _representations_ for the same number.

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

COMPONENT EQUIVALENCY NOTICE: The subatomic particles (electrons,
protons, etc.) comprising this product are exactly the same in every
measurable respect as those used in the products of other
manufacturers, and no claim to the contrary may legitimately be
expressed or implied.

[Jon Slaughter]

"Pascal Bourguignon" <pj*@informatimago.comwrote in message
news:87************@thalassa.informatimago.com...

"Proginoskes" <CC*******@gmail.comwrites:

>Which I did. Again, the number 3,628,800 does not appear anywhere in my
calculations. Therefore, I calculated the number 7 "without computing
the factorial".

Of course you did! "6.559763033" and "3,628,800" and "3628800" are
representations for the same number, "factorial of ten". The first is
a written representation of the number on the logarithmic scale, while
the others are different representations of the number on linear
scales. But they're both but _representations_ for the same number.

lol. then whats the point. With your definition all numbers have the same
representation.
i.e., there is only one number... why might as well call it 0.

i.e., its very easy to transform any number into another number and by your
definition if there exists such a transform then they must be equivilent.

your logic fails because this is not true... they are only EQUIVILENT under
that transformation. They are not universally equivilent. Your basically
mixing apples with oranges.

[Pascal Bourguignon]

"Jon Slaughter" <Jo***********@Hotmail.comwrites:

"Andrey Tarasevich" <an**************@hotmail.comwrote in message
news:12*************@news.supernews.com...

>Proginoskes wrote:

>>>...
The question wasn't to compute the result in a computationally
efficient way, it was to do it without computing the factorial.

Which I did. Again, the number 3,628,800 does not appear anywhere in my
calculations. Therefore, I calculated the number 7 "without computing
the factorial".
...

The only reason you are having this argument is that you forgot to agree
on the terminology.

You are saying that "number 3,628,800 does not appear anywhere" in your
calculations. How do you know that? May I remind you that '3,628,800' is
_not_ really a number. We call it a "number" in everyday conversations
because in most everyday contexts calling '3,628,800' a "number" is not
a big error. It is an error, but, once again, everybody understands what
we are really trying to say.

Now, in this discussion the difference becomes more important. So, what
'3,628,800' really is, if it not a "number"? '3,628,800' is a _decimal_
_representation_ of a number. Numbers are mathematical abstractions that
cannot be seen, smelt or touched. The only things about numbers that we
can see, smell or touch are particular _representations_ of numbers.

What you are really claiming above is that there's no decimal
representation of 10! an any point in your program. Fine, I'd be more
surprised it it was there. You can also safely claim that there's no
binary representation of 10! at any point in your program. That'd make
more sense, but that still misses the point. Because anyone can claim
that your sum of logarithms is noting less than an exotic representation
of 10! and, therefore, you are calculating 10! in your code. You just
choose an obscure representation for the result in order to throw the
wolves off your trail.

What you say might be true but its entirely off the point.

But that's still entirely my point.

It doesn't matter what he calls it because the fact of the matter
is computing the factorial of a whatever is not needed when taking
the log of it. This is the whole point about logs. They convert
multiplication to addition. Factorials are multiplication and a log
of it allows you to compute the same result with
additions. Additions are much less expensive(in terms of speed and
memory) in todays processors and so one only has to assume that.

And again, the OP didn't ask to compute the result without doing
multiplications, he asked to compute the result without computing
factorial of n.

--
__Pascal Bourguignon__ http://www.informatimago.com/
Small brave carnivores
Kill pine cones and mosquitoes
Fear vacuum cleaner

[Pascal Bourguignon]

"Jon Slaughter" <Jo***********@Hotmail.comwrites:

"Pascal Bourguignon" <pj*@informatimago.comwrote in message
news:87************@thalassa.informatimago.com...

>"Proginoskes" <CC*******@gmail.comwrites:

>>Which I did. Again, the number 3,628,800 does not appear anywhere in my
calculations. Therefore, I calculated the number 7 "without computing
the factorial".

Of course you did! "6.559763033" and "3,628,800" and "3628800" are
representations for the same number, "factorial of ten". The first is
a written representation of the number on the logarithmic scale, while
the others are different representations of the number on linear
scales. But they're both but _representations_ for the same number.

lol. then whats the point. With your definition all numbers have the same
representation.
i.e., there is only one number... why might as well call it 0.
i.e., its very easy to transform any number into another number and by your
definition if there exists such a transform then they must be equivilent.

If you can find an isomorphism between the structures of these
transforms and the set of numbers you consider, yep.

your logic fails because this is not true... they are only EQUIVILENT under
that transformation. They are not universally equivilent. Your basically
mixing apples with oranges.

I didn't speak of universal equivalence, I spoke of equivalence of the
logarithmic scale (with addition) and the linear scale (with
multiplication).
--
__Pascal Bourguignon__ http://www.informatimago.com/
Small brave carnivores
Kill pine cones and mosquitoes
Fear vacuum cleaner

[Phil Carmody]

Andrey Tarasevich <an**************@hotmail.comwrites:

Proginoskes wrote:

....

What you are really claiming above is that there's no decimal
representation of 10! an any point in your program.

Wrong.

Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.

[Phil Carmody]

Pascal Bourguignon <pj*@informatimago.comwrites:

"Proginoskes" <CC*******@gmail.comwrites:

Which I did. Again, the number 3,628,800 does not appear anywhere in my
calculations. Therefore, I calculated the number 7 "without computing
the factorial".

Of course you did! "6.559763033" and "3,628,800" and "3628800" are
representations for the same number, "factorial of ten". The first is
a written representation of the number on the logarithmic scale, while
the others are different representations of the number on linear
scales. But they're both but _representations_ for the same number.

You appear to think, if your brain maintains any sort of consistency,
that the following algorithm

double foo(double x) { return x; }

calculates the cubes and fifth powers. And seventh powers.
And in fact any function for which there's a R<->R bijection.
Phil
--
"Home taping is killing big business profits. We left this side blank
so you can help." -- Dead Kennedys, written upon the B-side of tapes of
/In God We Trust, Inc./.

[Proginoskes]

Jon Slaughter wrote:

"Pascal Bourguignon" <pj*@informatimago.comwrote in message
news:87************@thalassa.informatimago.com...

"Proginoskes" <CC*******@gmail.comwrites:

Which I did. Again, the number 3,628,800 does not appear anywhere in my
calculations. Therefore, I calculated the number 7 "without computing
the factorial".

Of course you did! "6.559763033" and "3,628,800" and "3628800" are
representations for the same number, "factorial of ten". The first is
a written representation of the number on the logarithmic scale, while
the others are different representations of the number on linear
scales. But they're both but _representations_ for the same number.

lol. then whats the point. With your definition all numbers have the same
representation.
i.e., there is only one number... why might as well call it 0.

i.e., its very easy to transform any number into another number and by your
definition if there exists such a transform then they must be equivilent.

your logic fails because this is not true... they are only EQUIVILENT under
that transformation. They are not universally equivilent. Your basically
mixing apples with oranges.

Yes, Pascal Bourguignon is only making himself look sillier and
sillier.

--- Christopher Heckman

[Pascal Bourguignon]

Phil Carmody <th*****************@yahoo.co.ukwrites:

Pascal Bourguignon <pj*@informatimago.comwrites:

>"Proginoskes" <CC*******@gmail.comwrites:

Which I did. Again, the number 3,628,800 does not appear anywhere in my
calculations. Therefore, I calculated the number 7 "without computing
the factorial".

Of course you did! "6.559763033" and "3,628,800" and "3628800" are
representations for the same number, "factorial of ten". The first is
a written representation of the number on the logarithmic scale, while
the others are different representations of the number on linear
scales. But they're both but _representations_ for the same number.

You appear to think, if your brain maintains any sort of consistency,
that the following algorithm

double foo(double x) { return x; }

calculates the cubes and fifth powers. And seventh powers.
And in fact any function for which there's a R<->R bijection.

I've spoke of isomorphism between fields, rings or groups, not just a
bijection.

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

"Do not adjust your mind, there is a fault in reality"
-- on a wall many years ago in Oxford.

[Richard Bos]

Pascal Bourguignon <pj*@informatimago.comwrote:

"Proginoskes" <CC*******@gmail.comwrites:

Which I did. Again, the number 3,628,800 does not appear anywhere in my
calculations. Therefore, I calculated the number 7 "without computing
the factorial".

Of course you did! "6.559763033" and "3,628,800" and "3628800" are
representations for the same number, "factorial of ten". The first is
a written representation of the number on the logarithmic scale, while
the others are different representations of the number on linear
scales. But they're both but _representations_ for the same number.

No, they're not. 3,628,800 and 3628800 are indeed representations of the
same number; but 6.559763033 is only a representation of _an
approximation_ of the logarithm of the same number. That approximation
may lead you to the same number for this case, on your computer; but the
problem is that you can't possibly be sure that this will remain true
for subsequent factorials, and in fact you can be quite confident that
it will lead to an error sooner or later.

Richard

[makc.the.great]

Proginoskes wrote:

Pascal Bourguignon wrote:

jmcgill <jm*****@email.arizona.eduwrites:

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.

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

this post is dejavu.
what's the difference, one still has to compute log(x) somehow. it is
even easier to ocmpute factorial itself.