 # Computers Make Me Stupid. And Greedy.

[updated 3/22/2022]

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)))))`

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.604`
`7482272297Knuth:  2567.60464`
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:
`CL-USER> ``(loop for n from 1 to 1000 sum (log n 10d0))2567.6046442221304d0`
Oh, well. Knuth is right and my LISP has trouble computing the log of a bignum. So much for this shot at geek fame.

COMPUTABLE-REALS is a Lisp library for arbitrary precision real numbers.
`CL-USER>`
` (ql:quickload :computable-reals)CL-USER> (cr:log-r (loop for n from 1 to 1000                   for f = 1 then (* n f)                   finally (return f))                   10)+2567.60464422213284877142...`
Note agreement between the three methods to 2567.60464422213. Then they diverge. But Maxima gets the right rounded result.