K
Klueless
For a different base B, other than 10, use
1+Floor(Log(Gamma(N+1))/Log(B))
1+Floor(Log(Gamma(N+1))/Log(B))
P
Phil Carmody
Pascal Bourguignon said:
Wrong.
Phil
P
Phil Carmody
Pascal Bourguignon said:
Wrong.
Phil
D
dcorbit
jmcgill said:
/*
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;
}
S
Stuart
James McGill said:
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
J
jmcgill
Stuart said:
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
L
luiroto
10^3! = 2568
10^4! = 35660
10^5! = 456574
10^6! = 5565709
10^7! = 65657060
Ludovicus
C
CBFalconer
Proginoskes said:
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:
< <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/>
J
John Smith
jmcgill said:
/* 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);
}
P
Proginoskes
CBFalconer said:
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
P
Pascal Bourguignon
Proginoskes said:
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.
L
Logan Shaw
Pascal said:
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
P
Pascal Bourguignon
Logan Shaw said:
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.
C
CBFalconer
Pascal said:
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:
< <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/>
L
luiroto
1000! = 2568
10000! = 35660
100000! = 456574
1000000! = 5565709
10000000! = 65657060
L
Logan Shaw
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
P
Pascal Bourguignon
Logan Shaw said:
If the problem asked to avoid constructing the message in the first
place, yes.
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.
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.
P
Proginoskes
Pascal said:
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 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.
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
A
Andrey Tarasevich
Proginoskes said:
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.
J
Jon Slaughter
Andrey Tarasevich said:
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.