1.4 Using the shift operations

So far we have been discussing things in generalities but when we make some assumptions about the machine then the above algorithms can be improved or simplified. For example, in the first algorithm for division, when M = bⁿ and there is a ``left shift'' operation on the symbol that amounts to multiplication by b, it is quicker to multiply iteratively by b to get something close enough to the required d. In this case division by d in the last step is also replaced by an appropriate ``right shift''.

On the other hand no such simplification is possible in the second algorithm for division, but (as is often true about ``real'' machines) if $\tt div$ is a significantly slower operation than the others, then it may be worthwhile to perform the extra steps.

Since most of our operations are on binary computers (so that M = 2ⁿ), we have special procedures to multiply and divide by powers of 2. We now describe these procedures based on some new fundamental operations.

left shift

The operation of multiplication by a power of 2

$$\tt lshift$$ : W×{0,..., n - 1}$$\to$$W×W

where (a, k) $\mapsto$ (c, d ) which satisfies

2^{k .} a = c ^. M + d

right shift

The operation of division by a power of 2

$$\tt rshift$$ : W×{0,..., n - 1}$$\to$$W×W

where (a, k) $\mapsto$ (c, d ) which satisfies

a ^. M/2^k = c ^. M + d

zero

The operation of finding out whether something is non-zero; this is also the ``bit-wise and'' operation

$$\tt zero$$ : W$$\to$${0, 1}

where a $\mapsto$ 0 if a is zero and 1 if it is non-zero.

bitwise negation

The difference from M - 1; this is also the operation of bitwise negation

$$\tt bneg$$ : W$$\to$$W

where a $\mapsto$ M - a - 1.

integer log to the base 2

The operation of finding the integer part of the logarithm to base 2

$$\tt log2$$ : W$$\to$${0,..., n - 1}

where a $\mapsto$ k which satisfies 2^k $\leq$ a < 2^k. This also counts the number of right shifts possible without carry.

left shift count

The number of left shifts possible without carry.

$$\tt gol2$$ : W$$\to$${0,..., n - 1}

where a $\mapsto$ k which satisfies M/2 $\leq$ 2^ka < M.

We can use these operations to produce some special algorithms. We note that we have already used the $\tt zero$ operation without mention!

Given a small integer k and an integer (u₁ ^... u_q), we can construct (v₀ ^... v_q) satisfying (v₀ ^... v_q) = 2^{k ...} (u₀ ^... v_q) as follows. We compute $\tt lshift$ (u_i, k) = (s_{i - 1}, t_i), $\tt add$ (s_i, t_i, 0) = (v_i, 0) and v₀ = s₀. Similarly, we can easily compute division by 2^k. We can also find the precise power of 2 that divides any integer (u₁ ^... u_q) (also called the 2-adic value of this integer). Clearly all these operations are of order linear in q. We can further extend this procedure quite easily to integers (k₁ ^... k_r) of size r with only r extra steps (to divide k by M).

Finally, we can also use the given basic operations to implement comparisons between integers which are linear in the size of the integers concerned.

We summarise our investigations in the following table

Operation	Time taken
Addition/Subtraction	Linear
Multiplication/Division by small integers	Linear
Multiplication/Division	Quadratic
Multiplication/Division by powers of 2	Linear
Comparison	Linear
2-adic value	Linear

Beyond this point we will not refer to the basic operations like $\tt add$ any more and make use of the higher level operations on integers mentioned above. If we do find a need for some specialised higher level operations to be implemented faster we should come back here and add to this section rather than complicate later sections!