# Computers Make Me Stupid. And Greedy.

In Fundamental Algorithms, exercise 4 in section 1.2.5 asks:

(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

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

(%i1) bfloat(log(1000!)/log(10));

(%o1) 2.567604644222133b3

Maxima agrees with Knuth. One final check. Using the identity

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

It takes less time to write a bit of LISP code to answer this question than it does to actually think about it:Given the fact that log10 1000! = 2567.60464..., determine exactly how many decimal digits there are in the number 1000!. What is the

most significantdigit? What is theleast significantdigit?

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

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

(%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:(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