Algorithm S

From Knuth’s The Art of Computer Programming, Volume 2: Seminumerical Algorithms 3^rd edition, pg. 267.

Given nonnegative integers $n$ place integers $(u_{n-1} \dots u_1u_0)_b \geq (v_{n-1}\dots v_1v_0)_b,$ this algorithm gives their difference $(w_{n - 1} \dots w_1 w_0)_b.$

1. (Initialize) Set $j = 0, k = 0.$
2. (Subtract Digits) Let $w_j = (u_j - v_j + k)\mod b,$ and $k = \lfloor(u_j - v_j + k) / b\rfloor.$
   • In other words, $k \in \{-1, 0\},$ depending on whether a borrow occurs, i.e. $u_j - v_j + k \lt 0.$
3. (Loop on $j$)
   • Increment $j.$
   • If $j \lt n,$ goto step 2.
   • Otherwise, terminate. Ensure that $k = 0,$ if $k = -1$ then the starting conditions for the algorithm were not met, and the results could be wrong.