468,463 Members | 2,018 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,463 developers. It's quick & easy.

Number of digits in N!

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?
Oct 5 '06
109 6767

"Jon Slaughter" <Jo***********@Hotmail.comwrote in message
news:12*************@corp.supernews.com...
>
"Pascal Bourguignon" <pj*@informatimago.comwrote in message
news:87************@thalassa.informatimago.com...
>"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.

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 don't think the topological content of the problem relevant and would
think that homeo- is properly homo- . That's a very faggy thing to say, so
I'll anounce that I'm shutting off my computer to go out and look for a girl
who looks like Dean Neuman's daughters. EC
Oct 14 '06 #101
Chris wrote:
) Willem wrote:
)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:

In that case you can also represent any given logarithm in a finite number
of bits. I didn't end my sentence above with 'then' for nothing you know.
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
Oct 14 '06 #102
Willem wrote:
Logan wrote:
) Any given integer can be represented in a finite number of bits.
....
Well, you can't even represent 1/3 in a finite number of bits, then.
1/3 is not an integer.
Oct 14 '06 #103
jmcgill said:
Willem wrote:
>Logan wrote:
) Any given integer can be represented in a finite number of bits.
...
>Well, you can't even represent 1/3 in a finite number of bits, then.

1/3 is not an integer.
It's actually an int, with the value 0 - integer division, remember! :-)

--
Richard Heathfield
"Usenet is a strange place" - dmr 29/7/1999
http://www.cpax.org.uk
email: rjh at above domain (but drop the www, obviously)
Oct 14 '06 #104
Willem wrote:
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. For example, in ASCII, it's "1/3". That's 24 bits.

:)

--
Clark S. Cox III
cl*******@gmail.com
Oct 14 '06 #105
Clark S. Cox III wrote:
Willem wrote:
>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. For example, in ASCII, it's "1/3". That's 24 bits.

:)
#include <stdio.h>
int main(void) {
char a[] = "1/3";
printf("%d\n", (int)sizeof a);
return 0;
}
...says 4 which is 32 bits, right?

--
Joe Wright
"Everything should be made as simple as possible, but not simpler."
--- Albert Einstein ---
Oct 14 '06 #106

On Sat, 14 Oct 2006, Joe Wright wrote:
Clark S. Cox III wrote:
>Willem wrote:
>>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. For example, in ASCII, it's "1/3". That's 24 bits.

#include <stdio.h>
int main(void) {
char a[] = "1/3";
printf("%d\n", (int)sizeof a);
return 0;
}
..says 4 which is 32 bits, right?
(Oh boy, crossposts to c.l.c that assume CHAR_BIT==8! ;)
I think your compiler needs some helpful hints. Try

#include <stdio.h>
int main(void) {
char a[3] = "1/3";
printf("%d\n", (int)sizeof a);
return 0;
}

/* ;-) */

-Arthur
Oct 15 '06 #107
Logan Shaw 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).
Reading this subthread, I get the strong impression that many people have
never heard of the notion of computable reals. Search the web for "exact
real arithmetic" or "computable real arithmetic" and you'll find many
libraries that will let you compute (sum_{i=1}^{N} log i) without roundoff
just as easily as GMP lets you compute (prod_{i=1}^{N} i) without wraparound.

-- Ben
Oct 15 '06 #108
Ben wrote:
) Reading this subthread, I get the strong impression that many people have
) never heard of the notion of computable reals. Search the web for "exact
) real arithmetic" or "computable real arithmetic" and you'll find many
) libraries that will let you compute (sum_{i=1}^{N} log i) without roundoff
) just as easily as GMP lets you compute (prod_{i=1}^{N} i) without wraparound.

Well then, just for the sake of argument, and keeping the OP in mind:

How exactly would such a library compute log10(7)+log10(8) ?
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
Oct 15 '06 #109

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?
I just found a formula in a book that might produce a very good
algorithm:

log(n!) = sum([n/p^k]*log(p))

where the sum runs over all p^k <= n and [ ] is the floor function.
This does require you to know all primes up to n though but this could
be in a lookup table.

so log(6!) = log(2)*([6/2] + [6/2^2]) + log(3)*[6/3] + log(5)*[6/5]

Ofcourse this sum isn't much different than sum(log(k),k=2..6) = log(2)
+ log(3) + log(4) + log(5) + log(6) for small n but might be pretty
good for large n since these primes are not very dense in the integers.

Anyways, I thought I'd throw it out there as its quite an interesting
formula.

Jon

Oct 19 '06 #110

This discussion thread is closed

Replies have been disabled for this discussion.

Similar topics

12 posts views Thread by jose luis fernandez diaz | last post: by
1 post views Thread by Shreyas Kulkarni | last post: by
10 posts views Thread by guidosh | last post: by
6 posts views Thread by Jovo Mirkovic | last post: by
27 posts views Thread by Luke Wu | last post: by
23 posts views Thread by neha_chhatre | last post: by
20 posts views Thread by jacob navia | last post: by
reply views Thread by NPC403 | last post: by
By using this site, you agree to our Privacy Policy and Terms of Use.