Some Elementary Functions

Prev: Integer Division by Constants

Next: Unusual Bases for Number Systems

Sections

• 11-1 Integer Square Root
• 11-2 Integer Cube Root
• 11-3 Integer Exponentiation
• 11-4 Integer Logarithm

Problems

1. Is the correct integer fourth root of an integer $x$ obtained by computing the integer square root of the integer square root of $x$?

2. Code the 64-bit version of the cube root routine that is mentioned at the end of Section 11-2. Use the long long C data type. Do you see an alternative method for handling the overflow of b that probably results in a faster routine?

3. How many multiplications does it take to compute $x^{23}$ modulo $2^W$, where $W$ is the computer’s word size?

4. Describe in simple terms the functions (a) $2^{ilog2(x)}$ and (b) $2^{ilog2(x-1)+1}$ for $x$ an integer greater than 0.