Characteristics (2/3) - Efficient Algorithms
Example: Exponentiation (xk)
E.g. 2713 (base 10) k = 13
= 27*27*27*27*27*27*27*27*27*27*27*27*27
= 110111101 (base 2) n = int(ld k) = 3
= (110118)1 * (110114)1 * (110112)0 * (110111)1
Worst case: 2n multiplications = O(n) = O(ld k)
instead of k - 1 = O(k) - here: only 5 instead of 12
Example: Conversion to decimal representation
Divides bit vector modulo largest power of 10 fitting
into a machine word, then uses machine word math
operations to break remainder down further
Example: Bit counting (number of set bits)