Number of digits in N!

[Chris Uppal]

Phil Carmody wrote:

[me:]

Repeat that argument with the cantor set.

Interesting, thanks.

Maybe I was misusing the term "dense" (It's been decades since I last
had to use it). All I meant was that for every value, x, in (0, 1),
and for every epsilon, there is at least one point in the set which was
within epsilon of x. And analogously for "dense around a point".

This is the first time I've heard of Cantor's set (unless I've
forgotten it, of course); but it looks at first glance as if it is
"dense" (in my sense, whether or not that is correct terminology)
around 0, 1/3. 2/3, and 1 (and so on fractally). Is that wrong ?

-- chris

 

[Proginoskes]

Phil Carmody wrote:

[me:]

Repeat that argument with the cantor set.

Interesting, thanks.

Maybe I was misusing the term "dense" (It's been decades since I last
had to use it). All I meant was that for every value, x, in (0, 1),
and for every epsilon, there is at least one point in the set which was
within epsilon of x. And analogously for "dense around a point".

This is the first time I've heard of Cantor's set (unless I've
forgotten it, of course); but it looks at first glance as if it is
"dense" (in my sense, whether or not that is correct terminology)

A set S being "dense at a point x" is usually phrased as "x is an
accumulation point of [a sequence of elements of] S" or "x is a limit
point of S".

--- Christopher Heckman

 

[M.J.T. Guy]

This raises an interesting question (of which I do not know the
answer): Given any
epsilon > 0, are there an infinite number of N's such that

{log(N!)} > 1 - epsilon ?

Consider log(N!) for N = 10^n + x, x <= 3*10^(n/2). The successive values
(mod 1) are increasing, differ by O(10^(n/2)) and span an interval > 1.
Hence the fractional parts of log(N!) are dense in [0, 1].


Mike Guy

 

[M.J.T. Guy]

Consider log(N!) for N = 10^n + x, x <= 3*10^(n/2). The successive values
(mod 1) are increasing, differ by O(10^(n/2)) and span an interval > 1.

^^^^^^^^
That should be 10^(_n/2) of course.

Hence the fractional parts of log(N!) are dense in [0, 1].

Mike Guy

 

[Allin Cottrell]

Phil Carmody said:


Repea at ar he ca set.

ROFL (or at least the British equivalent).

Allin Cottrell
Wake Forest University

 

[Andrey Tarasevich]

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.

Neither of this question/statements make sense without specifying which
concrete representation you are talking about. There's an infinite
number of different ones.

Even a mere "6.559763033" will represent completely different numbers
when interpreted as, say, either decimal or hexadecimal representation.

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.

That's true. Computer programs don't create information. They can only
transform it from one representation to the other. The whole point of
this is to produce the final result in the representation that makes it
easy to perceive (or consume, if you will). A program that is supposed
to calculate factorial, but outputs the result of 10! as "10!" is
absolutely correct from the purely formal point of view. Yet it is
completely useless for obvious reasons.

Another important point is that in order to be useful a program should
produce its result in a convenient representation that is either

1) fixed and pre-defined, or
2) non-fixed, but the concrete representation can always be easily
derived from the program's output (easily = the complexity of such
derivation is [significantly] lower that the complexity of obtaining the
same result in some "conventional" representation).

Someone else here argued jokingly that a program that always produces 0
as its result can be thought of as solving every numerical problem in
the world (for some reason 42 feels like a better choice though) and one
just needs to find the "correct" representation. Technically, this
statement is more serious than it seems at the first sight. Yes this
program _does_ solve every numerical problem in the world. Yet this
program is useless simply because it violates the above requirement -
the complexity of finding the correct representation is equivalent to
the complexity of the problem itself.

In our original case the log-based algorithm calculates 10! in a
well-known fixed pre-defined representation. The representation itself
feels a little weird for an unprepared mind stuck on decimals or other
positional formats (which another reason why it ignited such a
discussion), but this does not really change anything.

 

[Andrey Tarasevich]

Andrey Tarasevich wrote:
...

No, the straightforward algorithm involves only rational numbers (which
can be represented with a finite amount of information) and thus never
needs to suffer from rounding errors. The log-based one must suffer from
rounding errors since it involves irrational numbers (which require an
infinite amount of information to be represented directly).
...

No, that's not what I'm talking about. What I'm trying to say is that
assuming that we use, say, 4-byte numbers to represent intermediate
results in the program, either method will start to loose precision
sooner or later.

 

[Proginoskes]

Richard Bos wrote:

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.

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.

Neither of this question/statements make sense without specifying which
concrete representation you are talking about. There's an infinite
number of different ones.

Even a mere "6.559763033" will represent completely different numbers
when interpreted as, say, either decimal or hexadecimal representation.

Random off-topic observation:

The number 21963283741 is the only positive integer represented by the
same set of bits on the PDP-6/10 as a float as for an integer. If
32-bit numbers (in IEEE format) are used instead, the only number
represented the same way in both representations is 0. (Source: HAKMEM
#174; see http://www.inwap.com/pdp10/hbaker/hakmem/hakmem.html for a
HTML version. There's lots of neat tricks & trivia in the HAKMEM
document, by the way.)

--- Christopher Heckman

 

[Chris Uppal]

Could you explain what you mean by "10^n + x, x <= ...", please. Is it
sci-math-speak for "10^N + x where x is ..." ?

1. ^^^^^^^^
That should be 10^(_n/2) of course.

And what does the _ signify here ?

-- chris

 

[luiroto]

That's true. Computer programs don't create information. They can only
transform it from one representation to the other. >

If computer programs don't create information, why then, there exists
simulations?
It is not scientific theories equivalent to computer programs?
The Chaos Theory contradicts that proposition because a system of
non-lineal
differential equations produces results utterly unpredictibles.
Ludovicus

 

[Logan Shaw]

No, that's not what I'm talking about. What I'm trying to say is that
assuming that we use, say, 4-byte numbers to represent intermediate
results in the program, either method will start to loose precision
sooner or later.

We could assume 4-byte integers, but that would be an artificial
restriction. Virtually every major computer language has support
for integers of unbounded (but finite, for any given integer) size.

Any given integer can be represented in a finite number of bits. The
same is not true for any particular given logarithm. Some of them
(such as log2(256)) can be represented in a finite number of bits, but
some of them cannot.

- Logan

 

[Willem]

Logan wrote:
) Any given integer can be represented in a finite number of bits. The
) same is not true for any particular given logarithm. Some of them
) (such as log2(256)) can be represented in a finite number of bits, but
) some of them cannot.

Well, you can't even represent 1/3 in a finite number of bits, then.


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

 

[Elijah Cardon]

We could assume 4-byte integers, but that would be an artificial
restriction. Virtually every major computer language has support
for integers of unbounded (but finite, for any given integer) size.

Any given integer can be represented in a finite number of bits. The
same is not true for any particular given logarithm. Some of them
(such as log2(256)) can be represented in a finite number of bits, but
some of them cannot.

I just about shook myself apart laughing reading what I could of this
thread. My only question would be what the original post possibly could
have been. EC

 

[Chris Dollin]

Logan wrote:
) Any given integer can be represented in a finite number of bits. The
) same is not true for any particular given logarithm. Some of them
) (such as log2(256)) can be represented in a finite number of bits, but
) some of them cannot.

Well, you can't even represent 1/3 in a finite number of bits, then.

Sure you can: with a `ratio` object with numerator 1 and denominator 3:

Setpop
1_/2 =>
** 1_/2
datakey(1_/2) =>
** <key ratio>

You could, if you wanted to, play this same game in C.

 

[Pascal Bourguignon]

I just about shook myself apart laughing reading what I could of this
thread. My only question would be what the original post possibly could
have been. EC

It was:

From: jmcgill <[email protected]>
Subject: Number of digits in N!
Newsgroups: comp.lang.c, comp.programming, sci.math
Date: Thu, 05 Oct 2006 08:54:34 -0700
Organization: Cox Communications
Message-ID: <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?

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

PLEASE NOTE: Some quantum physics theories suggest that when the
consumer is not directly observing this product, it may cease to
exist or will exist only in a vague and undetermined state.

 

[osmium]

It was:

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 correct answer to which is "That is off topic. In this group we only
discuss the standardized C language.Instead we see 95 responses. So much for
topicality.

 

[Chris Dollin]

The correct answer to which is "That is off topic. In this group we only
discuss the standardized C language.Instead we see 95 responses. So much for
topicality.

It was cross-posted.

 

[Elijah Cardon]

It was:

From: jmcgill <[email protected]>
Subject: Number of digits in N!
Newsgroups: comp.lang.c, comp.programming, sci.math
Date: Thu, 05 Oct 2006 08:54:34 -0700
Organization: Cox Communications
Message-ID: <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?

Given that the question has been shot up like James Caan at the tollbooth, I
would offer the following. WLOG we can do base ten. The latest version of
Stirling's formula will not only gives you a number; it will also give you
an upper bound on error. You give me an N, I'll give you an m s.t. N! is
less than 10**m . That gives us a starting point to count backwards. I
think this recasts the problem. I know that when I backtrack to zero, I
will either fall asleep or say the correct number. EC
*****************
Kenny Rogers tonight.

 

[jmcgill]

It was cross-posted.

Someone posted on comp.lang.c with a legitimate question about
formatting Pascal's Triangle in C. Newsgroup posters abused and shunned
that original questioner. I wrote a solution. I found it far to easy,
so I started looking for a way to improve my solution. In particular, I
wanted to be able to format my triangle in centered columns (as it is
usually presented) by simply pre-calculating only the *last* row. This
turned out to be beyond my number skills, because the the only method I
knew that did not involve sequentially evaluating the entire series in
advance, required the use of binomials in large factorials. These
numbers very quickly exceed the size of any standard C integer type.
But I believed I could get further, if I were able to do something else
to compute the length of that last line, so I looked for a way to
compute the number of digits in a huge number without computing the huge
number itself (obviously, I needed my memory tickled to remember the
reggae song about de log of the quotient equal to de difference of de
logs mon).


Anyway, I learned a great deal from the nubmer theory discussion that
ensued in sci.math, and I was quite surprised that my simple question
engendered such a response.

I was also surprised and disappointed that nobody else tried to advise
the original poster, and nobody ever commented on my two original solutions.


James

 

[Bart Goddard]

Sure you can: with a `ratio` object with numerator 1 and denominator 3:

Or you could use "Cantor expansion". (Google comes back with lots
of hits.)

Bart