3

You can find the explanation of Algorithm 4.3.1D, as it appears in the book Art of The Computer Programming Vol. 2 (pages 272-273) by D. Knuth in the appendix of this question.

It appears that, in the step D.6, qhat is expected to be off by one at most.

Lets assume base is 2^32 (i.e we are working with unsigned 32 bit digits). Let u = [238157824, 2354839552, 2143027200, 0] and v = [3321757696, 2254962688]. Expected output of this division is 4081766756 Link

Both u and v is already normalized as described in D.1(v[1] > b / 2 and u is zero padded).

First iteration of the loop D.3 through D.7 is no-op because qhat = floor((0 * b + 2143027200) / (2254962688)) = 0 in the first iteration.

In the second iteration of the loop, qhat = floor((2143027200 * b + 2354839552) / (2254962688)) = 4081766758 Link.

We don't need to calculate steps D.4 and D.5 to see why this is a problem. Since qhat will be decreased by one in D.6, result of the algorithm will come out as 4081766758 - 1 = 4081766757, however, result should be 4081766756 Link.

Am I right to think that there is a bug in the algorithm, or is there a fallacy in my reasoning?

Appendix

enter image description here enter image description here

ShreevatsaR
  • 38,402
  • 17
  • 102
  • 126
yasar
  • 13,158
  • 28
  • 95
  • 160
  • Sorry, the following does not help with answering the question, but just a note: as mentioned on page 2 of Volume 1, in the TAOCP books algorithms are given letter names and referred to by that letter locally within that section, but otherwise their "proper" name includes the section name. So in this case you mean "Algorithm 4.3.1D" (pages 272-273 of Volume 2) (Chapter 4 Arithmetic, Section 4.3 Multiple-Precision Arithmetic, Section 4.3.1 The Classical Algorithms). – ShreevatsaR Mar 02 '20 at 00:33
  • About *"It appears that, in the step __D.6__, `qhat` is expected to be off by one at most"* -- note the paragraph just before the algorithm is given, which says "This algorithm uses a slightly improved choice of q̂ in step D3, which guarantees that q = q̂ or q̂ − 1" – ShreevatsaR Mar 02 '20 at 01:18
  • You seem to be missing the last part of D3, which involves "and repeat this test if r̂ < b" (that will ensure that q̂ is decreased two times till it attains its correct value q). I'll take some time to write this up as an answer (may not finish, so feel free to self-answer if I don't get to it in a few hours). – ShreevatsaR Mar 02 '20 at 01:45
  • Well frankly I don't think I'll have time to write an answer. But the short version is that there's a loop in D3 which you've executed 0 times instead of the correct number of times. – ShreevatsaR Mar 02 '20 at 02:21
  • (+1 for a well-stated question BTW. I don't know why someone has voted to close this as "Needs details or clarity"!) – ShreevatsaR Mar 02 '20 at 02:35

1 Answers1

2

There is no bug; you're ignoring the loop inside Step D3:

D3

In your example, as a result of this test, the value of q̂, which was initially set to 4081766758, is decreased two times, first to 4081766757 and then to 4081766756, before proceeding to Step D4.

(Sorry I did not have the time to make a more detailed / “proper” answer.)

ShreevatsaR
  • 38,402
  • 17
  • 102
  • 126
  • Thanks for the answer. For some reason, I overlook that part. Feel free to edit and expand the answer if you find time later. – yasar Mar 02 '20 at 11:44
  • He wasn't ignoring it, the original version had a typo where instead of \qhat >= b it was simply \qhat = b. You have copied from a different source. – archgoon May 22 '23 at 02:48
  • @archgoon Good eye / nice catch. But I meant that the "and repeat this test if r̂ < b" part was being ignored. As for q̂ = b vs q̂ ≥ b: does it make a difference? Looks like q̂ is only decreased by 1 at a time. – ShreevatsaR May 22 '23 at 03:04
  • Ah sorry, I was dealing with a different issue, and I noticed that your version was different. Unfortunately, fixing the `=` to `>=` doesn't resolve the issue unfortunately. Specifically, I'm dealing with the first step of dividing `990/50`. `5` goes into the top two digits `19` times, (and `5` is normalized so `d` from D.1 is `1`). `19` gets decremented to `18` (which is correct) but `qhat` is still technically too large. I've been reading over this section several times, and I can't figure out what I have misunderstood. – archgoon May 22 '23 at 03:26
  • 1
    @archgoon That's what the first step (D1, Normalize) is for — in this case given `990/50`, you first introduce the new digit position `0` to the left to turn it into `0990/50`, then start with: `5` goes into the top two digits `1` time, and so on. – ShreevatsaR May 22 '23 at 12:18
  • Ah thank you, that's the part I was missing; feeling dumb, thanks. :) – archgoon May 22 '23 at 22:16
  • 1
    @archgoon In case it helps you feel better, I spent quite a bit of time yesterday reading the text on the preceding pages and trying to figure it out, and it only occurred to me this morning when I woke up. :-) I think it's a recognized "problem" with Knuth's writing style, where he seems to be writing breezily in a conversational way, but actually every word is carefully chosen and significant and the reader can't afford to miss anything. (This makes TAOCP hard to skim; one never knows where to start reading.) – ShreevatsaR May 23 '23 at 03:54