Number of digits in N!

[Pascal Bourguignon]

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]

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]

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]

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

 

[Phil Carmody]

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

 

[Phil Carmody]

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

 

[Proginoskes]

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]

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.

 

[Richard Bos]

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]

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.

 

[Andrey Tarasevich]

...

Wrong.

Wrong.

 

[Andrey Tarasevich]

No, they're not.

Yes, they are.

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.

Just like any algorithm will lead to an error sooner or later. The only
reason it is an "approximation" is that the log-based algorithm of
calculating factorial starts to suffer from rounding errors sooner than
the straightforward algorithm. In that sense, if we wanted to calculate
the factorial, the log-based algorithm would make a bad practical choice
because of it introduces rounding errors a lot sooner (as we can observe
in 10! example). But for solving that original problem the log-based
algorithm works fine. It still calculates factorial though. It does it
_poorly_, but that's still not enough to say that it _doesn't_ calculate
the factorial.

 

[jmcgill]

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

The point of my original question was coming from an attempt to output
Pascal's Triangle further than was possible with the naive approach (you
reach int overflow well before you reach the rows of the series where
the int cannot represent the values themselves, because the intermediate
calculations require factorials.)

The other thing driving my original question was a desire to know, given
a constraint on the rows, how many columns of text would be required to
display the entire triangle.

The ensuing thread is very interesting to me, but some of the discussion
has missed the point of the original question.

 

[Jon Slaughter]

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

But an isomorphism always exist. Or, atleast an isometry. y = ax + b and
even y = b are simple isomorphism in a group(and hence a ring and field)
that let you get all the other elements.

f(x) = ax + b;

hence f(x + y) = a*(x+y) + 2b = a*x + b + a*y + b = f(x) + f(y)

hence f(x) is a homeomorphism and its obvious thats its an isomorphism.

I didn't speak of universal equivalence, I spoke of equivalence of the
logarithmic scale (with addition) and the linear scale (with
multiplication).

I'm not sure what your talking about any more but if you think that just
because we compute algorithmically sum(log(k),k=2..n) then it is the same as
computing log(n!) then your wrong. It can easily be proven by writing the
two algorithms out and computing there run time.

Now, if you mean they are equivilent representations of the same
mathematical entity then your right, thats the whole point. If they were not
then there would be no use us to use the quicker(algorithm). But just
because something is equivilent mathematically doesn't mean that they are
equivilent algorithmically(or other ways too).

3 = 12/4.

these are different mathematical representations of the same concept... they
are not different algorithmic representations of the same concept as they
are also not different symbolic representations of the same concept(what I
mean is that symbolically they are not the same just as they are not
algorithmically the same but they are mathematically the same).

Now one might ask why things that are mathematically equivilent not
algorithmically equivilent and thats a valid question. I think the answer
is simply that if it was the case then we would probably be asking the
opposite. (and life would be much harder as there would be no way to
simplify things).

 

[Jon Slaughter]

But that's still entirely my point.


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.

I think you are twisting things though. Because in essense I can use the
same logic you are using and say well, were not computing n! but the number
of digits of n!.

i.e. log(n!) != n! (not numerically but conceptually).

If you want to in some abstract way say we are computing n! when we compute
sum(log(k)) then you can say that but no one will understand you and they
will think you mean something else.

What we mean is that in the algorithm we did not compute n! at any step.
What you mean is that we did when you rearrange the algorithm and do other
things to it.

i.e. we mean sum(log(k)) is different algorithmically to log(n!) and you
mean they are mathematically the same. just like 10 is mathematically the
same as 2 + 4 + 3 + 1... they are not algorithmically the same as one is
easier to "compute".


Its true that in some sense we are "computing" n! when we do sum(log(k)) but
this computing does really exist because if it did we could not compute
sum(log(k)) for very large n's... the same n's that would break log(n!).

i.e., you have to realize that your wrong in some sense because we can
compute the sum for n = 10000 but not log(n!). i.e. there is a difference.
Now ask yourself what is the difference? where does it break down? obviously
there are only two spots... either the log part breaks it or the n! part.
Its not the log because then it would break in the first case too... so it
has to be the n!. but if we had n! in the sum then it would break too... it
doesn't and hence we don't have the n! in it. (and I'm dealing on the
algorithmic plane here).

 

[Willem]

Andrey wrote:
) 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.

This sum of lograithms doesn't need to be exact, so all it represents is an
_approximation_ of the factorial. Thus it's not calculating the factorial.


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

 

[Jon Slaughter]

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

Yes, but try computing 1030203! and log(1030203!)(using some other method
than just tkaing the log of the first). Then ask yourself which is easier.
Sure its much easyer to compute 3!,4! directly and then take the log... but
when you start dealing with problems where n is very large you get way in
over your head very quick(not only with storage problems but time problems
too).

 

[Willem]

(e-mail address removed) wrote:
) Proginoskes wrote:
)> 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?
)
) this post is dejavu.
) what's the difference, one still has to compute log(x) somehow. it is
) even easier to ocmpute factorial itself.

Let's change that calculation slightly then.

log 1 ~= 0.0
log 2 ~= 0.3
log 3 ~= 0.5
log 4 ~= 0.6
log 5 ~= 0.7
log 6 ~= 0.8
log 7 ~= 0.8
log 8 ~= 0.9
log 9 ~= 1.0
log 10 ~= 1.0

The sum is 6.6, so the answer is 7.


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]

I think you are twisting things though. Because in essense I can use the
same logic you are using and say well, were not computing n! but the number
of digits of n!.

i.e. log(n!) != n! (not numerically but conceptually).

If you want to in some abstract way say we are computing n! when we compute
sum(log(k)) then you can say that but no one will understand you and they
will think you mean something else.

What we mean is that in the algorithm we did not compute n! at any step.
What you mean is that we did when you rearrange the algorithm and do other
things to it.

i.e. we mean sum(log(k)) is different algorithmically to log(n!) and you
mean they are mathematically the same. just like 10 is mathematically the
same as 2 + 4 + 3 + 1... they are not algorithmically the same as one is
easier to "compute".


Its true that in some sense we are "computing" n! when we do sum(log(k)) but
this computing does really exist because if it did we could not compute
sum(log(k)) for very large n's... the same n's that would break log(n!).

Agreed. My point is that the way the problem was stated, I don't
consider a solution summing the logarithms to be valid, while a
solution using Stirling approximation is.

i.e., you have to realize that your wrong in some sense because we can
compute the sum for n = 10000 but not log(n!). i.e. there is a difference.

I'll spare you the 35 kbyte dump, but my computer has no problem in
computing 10000! and counting the number of digits needed to
represent it in base 10:

LISP> (time (length (prin1-to-string (ext:! 10000))))
Real time: 0.304857 sec.
Run time: 0.296018 sec.
Space: 617096 Bytes
35660

 

[Keith Thompson]

Yes, they are.

[...]

If "6.559763033" is a representation of 3628800, then how would you
represent 6.559763033?

"10**6.559763033" is an approximate representation of 3628800.
"6.559763033" is merely a representation of 6.559763033.

Note that "10!" is also a representation of 3628800, which saves you a
lot of work if you don't mind not knowing the actual answer.