Hacker's Delight

9-2. Multiword Division

As in the case of multiword multiplication, multiword division may be done by, basically, the traditional grade-school method. The details, however, are surprisingly complicated. Figure 9-1 is Knuth’s Algorithm D [Knu2 sec. 4.3.1], coded in C. The underlying form of division it uses is (Actually, the quotient of these underlying division operations is at most 17 bits long.)

Figure 9-1. Multiword integer division, unsigned , .

int divmnu(unsigned short q[], unsigned short r[], const unsigned short u[], const unsigned short v[], int m, int n) { const unsigned b = 65536; // Number base (16 bits). unsigned short *un, *vn; ...