435,028 Members | 1,869 Online + Ask a Question
Need help? Post your question and get tips & solutions from a community of 435,028 IT Pros & Developers. It's quick & easy.

Number of digits in N!

 P: n/a 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 #1
109 Replies

 P: n/a "jmcgill"

 P: n/a 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 Oct 5 '06 #3

 P: n/a jmcgill

 P: n/a "jmcgill"

 P: n/a 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). Oct 5 '06 #6

 P: n/a 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 Oct 5 '06 #7

 P: n/a 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 Oct 5 '06 #8

 P: n/a Willem

 P: n/a Stuart wrote: "jmcgill" Is there a method for computing the number of digits, in a given numericbase, 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 evaluatingthe 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 Oct 5 '06 #10

 P: n/a James McGill "jmcgill" >Is there a method for computing the number of digits, in a given numericbase, 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 evaluatingthe factorial? Depends on how accurate you need the answer to be and over whatrange! 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. Oct 5 '06 #11

 P: n/a 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. Oct 5 '06 #12

 P: n/a James McGill > 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 askedto 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. Oct 5 '06 #13

 P: n/a 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 Oct 5 '06 #14

 P: n/a In article <11*********************@b28g2000cwb.googlegroups. com"Mitch"

 P: n/a "jmcgill"

 P: n/a 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 Oct 6 '06 #17

 P: n/a 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!" Oct 6 '06 #18

 P: n/a Pascal Bourguignon wrote: Willem

 P: n/a Pascal Bourguignon wrote: jmcgill

 P: n/a "Klueless" Is there a method for computing the number of digits, in a given numericbase, 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)) Oct 6 '06 #21

 P: n/a Pascal Bourguignon

 P: n/a Pascal Bourguignon

 P: n/a 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 #include #include char string; 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; } Oct 6 '06 #24

 P: n/a "James McGill" "jmcgill" >Is there a method for computing the number of digits, in a given numericbase, 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 evaluatingthe 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 Oct 6 '06 #25

 P: n/a 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 :-) Oct 6 '06 #26

 P: n/a 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 Oct 6 '06 #27

 P: n/a Proginoskes wrote: Pascal Bourguignon wrote: >Willem >jmcgill wrote:Is there a method for computing the number of digits, in agiven numeric base, of N factorial, without actually computingthe factorial?For example, 8! has 5 digits in base 10; 10! has 7 digits inbase 10. Is there a way to compute that information withoutactually 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 factorialwhen 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 #include Oct 7 '06 #28

 P: n/a 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 #include #include #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, 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; 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); } Oct 7 '06 #29

 P: n/a CBFalconer wrote: Proginoskes wrote: Pascal Bourguignon wrote: Willem

 P: n/a "Proginoskes" Proginoskes wrote: Pascal Bourguignon wrote:Willem

 P: n/a Pascal Bourguignon wrote: "Proginoskes" 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 factorialwhen it was asked to avoid it! >>>Oh, really?log 1 = 0log 2 = 0.3010299957log 3 = 0.4771212547log 4 = 0.6020599914log 5 = 0.6989700043log 6 = 0.7781512504log 7 = 0.8450980400log 8 = 0.9030899871log 9 = 0.9542425094log 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 restare 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 acourse involving logarithms (which are taught in College Algebra herein 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 Oct 8 '06 #32

 P: n/a Logan Shaw "Proginoskes" >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 = 0log 2 = 0.3010299957log 3 = 0.4771212547log 4 = 0.6020599914log 5 = 0.6989700043log 6 = 0.7781512504log 7 = 0.8450980400log 8 = 0.9030899871log 9 = 0.9542425094log 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 restare 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 acourse involving logarithms (which are taught in College Algebra herein 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,+), computinglog(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. Oct 8 '06 #33

 P: n/a 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: Oct 8 '06 #34

 P: n/a 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 Oct 8 '06 #35

 P: n/a Pascal Bourguignon wrote: Logan Shaw Pascal Bourguignon wrote: >>Since there is an isomorphism between (R+*,*) and (R,+), computinglog(f(x)) or f(x) is the same thing. >I think Proginoskes' point was that if you understood logarithms, youwould have thought to apply them by taking the sum of logarithmsrather than the logarithm of products. It is true that they aremathematically 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 Oct 9 '06 #36

 P: n/a Logan Shaw 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. Oct 9 '06 #37

 P: n/a Pascal Bourguignon wrote: Logan Shaw >>>Of course, but this sum (before rounding) is 10! (log10(n!)actually, but it's the same) You have computed the factorialwhen it was asked to avoid it! >>>Oh, really?log 1 = 0log 2 = 0.3010299957log 3 = 0.4771212547log 4 = 0.6020599914log 5 = 0.6989700043log 6 = 0.7781512504log 7 = 0.8450980400log 8 = 0.9030899871log 9 = 0.9542425094log 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 restare 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 acourse involving logarithms (which are taught in College Algebra herein 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 Oct 9 '06 #38

 P: n/a Proginoskes wrote: >...The question wasn't to compute the result in a computationallyefficient 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 Oct 9 '06 #39

 P: n/a "Proginoskes"

 P: n/a "Pascal Bourguignon" Which I did. Again, the number 3,628,800 does not appear anywhere in mycalculations. Therefore, I calculated the number 7 "without computingthe 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. Oct 9 '06 #42

 P: n/a "Jon Slaughter" "Proginoskes" >Which I did. Again, the number 3,628,800 does not appear anywhere in mycalculations. Therefore, I calculated the number 7 "without computingthe factorial". Of course you did! "6.559763033" and "3,628,800" and "3628800" arerepresentations for the same number, "factorial of ten". The first isa written representation of the number on the logarithmic scale, whilethe others are different representations of the number on linearscales. 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 Oct 9 '06 #44

 P: n/a Andrey Tarasevich

 P: n/a Pascal Bourguignon 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./. Oct 9 '06 #46

 P: n/a Jon Slaughter wrote: "Pascal Bourguignon"

 P: n/a Phil Carmody "Proginoskes" 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. Oct 9 '06 #48

 P: n/a Pascal Bourguignon

 P: n/a Proginoskes wrote: Pascal Bourguignon wrote: jmcgill 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. Oct 9 '06 #50

109 Replies

This discussion thread is closed

Replies have been disabled for this discussion. 