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

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

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:

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.

Given the fact that log10 1000! = 2567.60464..., determine exactly how many decimal digits there are in the number 1000!. What is themost significantdigit? What is theleast significantdigit?

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.604`

`7482272297`

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