Integer Division by Constants

Prev: Integer Division

Next: Some Elementary Functions

Sections

• 10-1 Signed Division by a Known Power of 2
• 10-2 Signed Remainder from Division by a Known Power of 2
• 10-3 Signed Division and Remainder by Non-Powers of 2
• 10-4 Signed Division by Divisors $\ge 2$
• 10-5 Signed Division by Divisors $\le -2$
• 10-6 Incorporation into a Compiler
• 10-7 Miscellaneous Topics
• 10-8 Unsigned Division
• 10-9 Unsigned Division by Divisors $\ge 1$
• 10-10 Incorporation into a Compiler (Unsigned)
• 10-11 Miscellaneous Topics (Unsigned)
• 10-12 Applicability to Modulus and Floor Division
• 10-13 Similar Methods
• 10-14 Sample Magic Numbers
• 10-15 Simple Code in Python
• 10-16 Exact Division by Constants
• 10-17 Test for Zero Remainder after Division by a Constant
• 10-18 Methods Not Using Multiply High
• 10-19 Remainder by Summing Digits
• 10-20 Remainder by Multiplication and Shifting Right
• 10-21 Converting to Exact Division
• 10-22 A Timing Test
• 10-23 A Circuit for Dividing by 3

Problems

1. Show that for unsigned division by an even number, the shrxi instruction, or equivalent code, can be avoided by first (a) turning off the low-order bit of the dividend, and operation, [CavWer] or (b) dividing the dividend by 2, shift-right-1 instruction, and then dividing by half the divisor.

2. Code a function in Python similar to that of Figure 10-4 on page 240, but for computing the magic number for signed division. Consider only positive divisors.

3. Show how you would use Newton’s method to calculate the multiplicative inverse of an integer $d$ modulo $81$. Show the calculations for $d=146$.