Algorithms D, P, and S

§ Overview

(3 Jan 2025) Algorithms S and P are special to me, from when I was in MATH-470.

Algorithm subtraction and division algorithms for bigints, i.e. larger than what the processor can handle.

§ Algorithm P

Commonly known as the Fisher-Yates shuffle.

for (auto i = vec.size(); i-- > 0;){
    auto j = random_integer(i); // Random integer from 0 <= j <= i
    std::swap(vec[i], vec[j]);
}

§ 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.

§ Algorithm D

From pg. 272.

Given nonnegative integers $u = (u_{m+n-1} \dots u_1u_0)_b$ and $v = (v_{n-1}\dots v_1v_0)_b,$ where $u_{n-1} \neq 0$ and $n \gt 1,$ we can form the radix-$b$ quotient $\lfloor u/v \rfloor = (q_mq_{m-1}\dots q_0)_b$ and the remainder $u\mkern-1ex\mod v = (r_{n-1}\dots r_1r_0)_b.$

1. (Normalization)
   • Let $d = \lfloor (b - 1) / b_{n - 1} \rfloor.$
     • Depending on the representation/system, it may be preferable to choose $d$ to be a power of $2.$
     • In any case, an acceptable $d$ would satisfy $v_{n - 1} \geq \lfloor b/2 \rfloor$.
   • Then, set $(u_{m + n}u_{m + n - 1} \dots u_1 u_0)_b$ equal to $d$ times $(u_{m + n - 1} \dots u_1 u_0)_b.$
     • If $d = 1,$ set $u_{m + n} = 0.$
   • Similiarly, set $(v_{n - 1} \dots u_1 u_0)_b$ equal to $d$ times $(v_{n - 1} \dots v_1 v_0)_b.$
2. (Initialize $j$)
   • Let $j = m.$
   • The loop over $j$, i.e. steps 2 to 7, will essentially do a division of $(u_{j + n}\dots u_{j+1}u_j)_b$ by $(v_{n-1}\dots v_1v_0)_b$ to get a single digit of the quotient.
3. (Calculate $\hat{q}$)
   • Set $\hat{q} = \lfloor (u_{j+n}b + u_{j + n - 1}) / v_{n - 1} \rfloor,$ and let $\hat{r} = (u_{j + n}b + u_{j + n - 1}\mod v_{n-1}$ be the remainder.
   • Test if $\hat{q} = b$ or $\hat{q}v_{n-2} \gt b\hat{r} + u_{j + n - 2}.$
     • If yes, then decrement $\hat{q}$ and add $v_{n-1}$ to $\hat{r}.$ If $\hat{r} \lt b,$ repeat.
     • Otherwise, continue.
4. (Mulsub)
   • Replace $(u_{j + n}u_{j + n - 1}\dots u_{j})_b$ with $(u_{j + n} u_{j + n - 1} \dots u_j)_b - \hat{q}(v_{n - 1} \dots v_1 v_2)_b.$
   • The digits $(u_{j + n}, u_{j + n - 1}, \dots, u_j)$ should be kept positive.
     • If the result is actually negative, then $(u_{j + n} u_{j + n - 1} \dots u_j)_b$ should be left as the true value plus $b^{n + 1},$ namely the $b$'s complement of the true value, and the borrow to the left should be remembered.
5. (Test Remainder)
   • Set $q_j = \hat{q}.$
   • If the result of step 4 was negative, goto 6, otherwise goto 7.
6. (Add Back)
   • Decrement $q_j$ and add $(0v_{n - 1}\dots v_1 v_0)_b$ to $(u_{j + n} u_{j + n - 1} \dots u_{j + 1} u_j)_b.$
   • Note that a carry will occur to the left of $u_{j + n},$ but it should be ignored because it cancels with the borrow in step 4.
7. (Loop on $j$)
   • Decrement $j.$ Goto 3 if $j \geq 0.$
8. (Unnormalize)
   • Now $(q_m\dots q_1q_0)_b$ is the quotient.
   • The remainder can be obtained by dividing $(u_{n - 1} \dots u_1 u_0)_b$ by $d.$