+/*
+* About the multiplication and division algorithms:
+*
+* I searched unsucessfully for fast built-in operations like the `b_0'
+* and `c_0' Knuth describes in Section 4.3.1 of ``The Art of Computer
+* Programming'' (replace `place' by `Blk'):
+*
+* ``b_0[:] multiplication of a one-place integer by another one-place
+* integer, giving a two-place answer;
+*
+* ``c_0[:] division of a two-place integer by a one-place integer,
+* provided that the quotient is a one-place integer, and yielding
+* also a one-place remainder.''
+*
+* I also missed his note that ``[b]y adjusting the word size, if
+* necessary, nearly all computers will have these three operations
+* available'', so I gave up on trying to use algorithms similar to his.
+* A future version of the library might include such algorithms; I
+* would welcome contributions from others for this.
+*
+* I eventually decided to use bit-shifting algorithms. To multiply `a'
+* and `b', we zero out the result. Then, for each `1' bit in `a', we
+* shift `b' left the appropriate amount and add it to the result.
+* Similarly, to divide `a' by `b', we shift `b' left varying amounts,
+* repeatedly trying to subtract it from `a'. When we succeed, we note
+* the fact by setting a bit in the quotient. While these algorithms
+* have the same O(n^2) time complexity as Knuth's, the ``constant factor''
+* is likely to be larger.
+*
+* Because I used these algorithms, which require single-block addition
+* and subtraction rather than single-block multiplication and division,
+* the innermost loops of all four routines are very similar. Study one
+* of them and all will become clear.
+*/
+
+/*
+* This is a little inline function used by both the multiplication
+* routine and the division routine.
+*
+* `getShiftedBlock' returns the `x'th block of `num << y'.
+* `y' may be anything from 0 to N - 1, and `x' may be anything from
+* 0 to `num.len'.
+*
+* Two things contribute to this block:
+*
+* (1) The `N - y' low bits of `num.blk[x]', shifted `y' bits left.
+*
+* (2) The `y' high bits of `num.blk[x-1]', shifted `N - y' bits right.
+*
+* But we must be careful if `x == 0' or `x == num.len', in
+* which case we should use 0 instead of (2) or (1), respectively.
+*
+* If `y == 0', then (2) contributes 0, as it should. However,
+* in some computer environments, for a reason I cannot understand,
+* `a >> b' means `a >> (b % N)'. This means `num.blk[x-1] >> (N - y)'
+* will return `num.blk[x-1]' instead of the desired 0 when `y == 0';
+* the test `y == 0' handles this case specially.
+*/
+inline BigUnsigned::Blk getShiftedBlock(const BigUnsigned &num,
+ BigUnsigned::Index x, unsigned int y) {
+ BigUnsigned::Blk part1 = (x == 0 || y == 0) ? 0 : (num.blk[x - 1] >> (BigUnsigned::N - y));
+ BigUnsigned::Blk part2 = (x == num.len) ? 0 : (num.blk[x] << y);
+ return part1 | part2;
+}
+