StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>My copy of Knuth (The Art of Computer Programming) is at work, so I can't check it until Monday, but that would be my first source. It has a whole section on arithmetic.</p> <hr> <p>edit: your post about "16/16 division and 32/16 division which both take 18 cycles." -- dsPICs have a conditional subtract operation in assembly. Consider using this as your computational primitive.</p> <p>Also note that if X = XH * 2<sup>32</sup> + XL and D = DH * 2<sup>16</sup> + DL, then if you are looking for </p> <p>(Q,R) = X/D where X = Q * D + R</p> <p>where Q = QH * 2<sup>16</sup> + QL, R = RH * 2<sup>16</sup> + RL, then</p> <p>XH * 2<sup>32</sup> + XL = DH * QH * 2<sup>32</sup> + (DL * QH + DH * QL) * 2<sup>16</sup> + (DL * QL) + RH * 2<sup>16</sup> + RL</p> <p>This suggests (by looking at terms that are the high 32 bits) to use the following procedure, akin to long division:</p> <ol> <li>(QH, R0) = XH / (DH+1) -> XH = QH * (DH+1) + R0 [32/16 divide]</li> <li>R1 = X - (QH * 2<sup>16</sup>) * D [requires a 16*32 multiply, a shift-left by 16, and a 64-bit subtract]</li> <li>calculate R1' = R1 - D * 2<sup>16</sup></li> <li>while R1' >= 0, adjust QH upwards by 1, set R1 = R1', and goto step 3</li> <li>(QL, R2) = (R1 >> 16) / (DH+1) -> R1 = QL * (DH+1) + R2 [32/16 divide]</li> <li>R3 = R1 - (QL * D) [requires a 16*32 multiply and a 48-bit subtract]</li> <li>calculate R3' = R3 - D</li> <li>while R3' >= 0, adjust QL upwards by 1, set R3 = R3', and goto step 7</li> </ol> <p>Your 32-bit quotient is the pair (QH,QL), and 32-bit remainder is R3.</p> <p>(This assumes that the quotient is not larger than 32-bit, which you need to know ahead of time, and can easily check ahead of time.)</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload