# Computers Make Me Stupid. And Greedy.

In Fundamental Algorithms, exercise 4 in section 1.2.5 asks:

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

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 log

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

LISP: 2567.6047482272297

Knuth: 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:

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 log

Given the fact that log10 1000! = 2567.60464..., determine exactly how many decimal digits there are in the number 1000!. What is themost significant digit? What is theleast 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:

The answer is:

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

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.

2568 digits, most=4, least=0

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 log

_{10}1000! = 2567.60464, then 1000! = 10^{2567.60464}. This means 1000! = 10^{(2567 + 0.60464)}= 10^{2567}10^{0.60464}. Well, 10^{0.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

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

(log (loop for n from 1 to 1000 for f = 1 then (* f n)

finally (return f))

10d0)

LISP: 2567.6047482272297

Knuth: 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 log

_{10}1000! this way:Oh, well. Knuth is right and my LISP has trouble computing the log of a bignum. So much for this shot at geek fame.

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

2567.6046488768784d0

blog comments powered by Disqus