Computers Make Me Stupid. And Greedy.

In Fundamental Algorithms, exercise 4 in section 1.2.5 asks:

Given the fact that log10 1000! = 2567.60464..., determine exactly how many decimal digits there are in the number 1000!. What is the most significant digit? What is the least significant digit?

It takes less time to write a bit of LISP code to answer this question than it does to actually think about it:

   (let ((s (write-to-string
            (loop
               for n from 1 to 1000
               for f = 1 then (* n f)
               finally (return f)))))
     (format t "~d digits, most=~d, least=~d~%" (length s)
             (aref s 0) (aref s (1- (length s)))))

The answer is:

   2568 digits, most=4, least=0

Knuth rated this problem as a “13”, where a “10” should take around one minute and “20” should take around 15 minutes, so this problem should take about 5 minutes.

It’s easy to see from the provided information that the number of digits is 2568, since the number of digits in a decimal number is int(log10(n)) + 1. It’s also easy to see that the least significant digit has to be zero, since 1000! = 999! * 1000 and multiplying by a power of 10 adds one or more zeros to the end of a number. But the most significant digit took me a bit more thought. If log10 1000! = 2567.60464, then 1000! = 102567.60464. This means 1000! = 10(2567 + 0.60464) = 102567100.60464. Well, 100.60464=4.0238338... so the leading digit is 4. In fact, the leading digits are 402387.

If all I were interested in was the answer then the computer enabled me to get it without having to think about anything.

As for greed, my LISP says that

     (log (loop for n from 1 to 1000 for f = 1 then (* f n)
             finally (return f))
          10d0)

is 2567.6047482272297d0. But note that this differs from the value given by Knuth.

LISP:   2567.6047482272297
Knuth:  2567.604
64

Could it be that Knuth was wrong? If so, and this hasn’t been brought to his attention, then I could get a check from him. In the preface to the Second Edition, he wrote:

By now I hope that all errors have disappeared from this book; but I will gladly pay $2.00 reward to the first finder of each remaining error, whether it is technical, typographical, or historical.

These checks are collector’s items; few, if any, recipients cash them. But, alas, it was not to be. Floating-point calculations are notoriously hard to get right. So I fired up Maxima to get a second opinion:

(%i1) bfloat(log(1000!)/log(10));
(%o1)                        2.567604644222133b3

Maxima agrees with Knuth. One final check. Using the identity log(a*b) = log(a) + log(b), let’s have LISP compute log10 1000! this way:

     (loop for n from 1 to 1000 sum (log n 10d0))
     2567.6046488768784d0

Oh, well. Knuth is right and my LISP has trouble computing the log of a bignum. So much for this shot at geek fame.
blog comments powered by Disqus