01.md

Section 3.1

Number representation

An $l$ digit base $b$ number is annotated as:

$$N = \pm(d_{l-1} ...d_1d_0)_b$$

For example, let's look at decimal number 5305. It has 4 digits, so l is 4. The base is 10, so b is 10, and the number is represented as:

$$ 5305_{dec} = +(5_{3}3_{2}0_{1}5_{0})_{10} $$

Let's look at a base 16 number 95A (the value is 2394 in decimal). It has 3 digits, so l is 3; base is 16, so b is 16, and the number is represented as:

$$ 95A_{hex} = +(9_{2}5_{1}A_{0})_{16} $$

Calculating the value

The value of N is calculated as:

$$ \pm \sum_{i=0}^{l-1} d_i * b^i $$

This means, iterate from $i=0$ to $l-1$, and sum up the value of $d_i b^i$.

Note that when we calculate the value, it essentially means convert the value to decimal. Let's look at the decimal example to see the output matches the value itself 5305

$$ 5305_{dec} = +(5_{3}3_{2}0_{1}5_{0})_{10} $$

$$ = \sum_{i=0}^{3} d_i * 10^i $$

$$ = 5 * 10^3 + 3 * 10^2 + 0 * 10^1 + 5 * 10^0 = 5000 + 300 + 0 + 5 = 5305 $$

Let's look at the base 16 (hexadeicmal example). The value is 95A:

$$ 95A_{hex} = +(9_{2}5_{1}A_{0})_{16} $$

$$ = \sum_{i=0}^2 d_i * 16^i $$

$$ = 9 * 16^2 + 5 * 16^1 + 10 * 16^0 $$

$$ = 9 * 256 + 5 * 16 + 10 * 1 $$

$$ = 2304 + 80 + 10 $$

$$ = 2394 $$

Let's use the actual example in Figure 3.1, where N = 1234567890 with base b = 1000. First, the N here is a decimal number, I want to obtain the value in decimal 1000, unfortunately I couldn't find a way to do it, so I just had to guess the representation based on the number on the figure. Note that the least significant number is stored on the first node.

$$ 001_{3}234_{2}567_{1}890_{0} $$

Let's verify it by doing the calculation

$$ = 1 * 1000^3 + 234 * 1000^2 + 567 * 1000^1 + 890 * 1000^0 $$

$$ = 1234567890 $$

Multiplication algorithm 3.3

check this out

Karatsuba algorithm

I found a good explanation here. There are explanations and notation on the general case of the algorithm, but I want to use a simple example to illustrate it. Suppose we are calculating 15 * 16.

$$ 15 = 10 * 1 + 5 = 10 * a + b $$

$$ 16 = 10 * 1 + 6 = 10 * c + d $$

The naive way to calculate the multiplication goes like this:

$$ (10 * a + b) * (10 * c + d) = 100 * ac + 10 * (ad + bc) + bd $$

Notice that there are four multiplication taking place.

The karatsuba algorithm observed that $ad + bc$ can be calculated as

$$ ad + bc = (a + b) * (c + d) - ac - bd $$

So the overall calculation becomes

$$ 100 * ac + 10 * ((a + b) * (c + d) - ac - bd) + bd $$

Since ac and bd are calculated and reused, the total multiplication being performed is now three (Note that the multiplication by 100 and 10 are not actual multiplication, but rather bit shifting, aka free multiplication as they are cheap to perform).

What I have shown above is essentially the base case of the recursion which seem to be glossed over in other full blown explanation of the algorithm.

Section 3.2.4

Trial quotient

Remember in long division, we are breaking the numbers into blocks and do a division.

For example, when when we divide 4852 by 47. The first block is 48 divide 47, with the result value 1 and remainder 1.

Then we do 15 divide 47, with result 0, and remainder 15. Then we do 152 divide 47, with result 3 and remainder 11. The final quotient is 103. See Figure 3.3 (b) for the visual.

Figure 3.2 is describing the step at each block.

For $48$ divides $47$, $u$ is $48$, and $v$ is $47$; for $15$ divides $47$, $u$ is $15$, $v$ is $47$.

The notation ($u_n...u_1u_0$ and $v_{n-1}...v_1v_0$) shown on the next page (page 91) is the expanded version of the number.

For example, we look at the first step ($48$ divides $47$). $48$ is expanded into $u_2u_1u_0$ where $u_2$ is 0, $u_1$ is 4, and $u_0$ is 8. $47$ is expanded into $v_1v_0$ where $v_1$ is $4$, and $v_0$ is $7$. Note that dividend ($48$) has to be one digit more than the divisor ($47$) for the notation to make sense, and to make $48$ one digit more, we pad it with a leading $0$, so it becomes $048$ without changing the actual value. In this case, $n$ is $2$.

Similarly, in the second step, we have $15$ divides $47$; $15$ is padded to be $015$, and so divisor is $u_2u_1u_0$ where $u_2$ is $0$, $u_1$ is $1$ and $u_0$ is $5$, dividend is $v_1v_0$ where $v_1$ is $4$ and $v_0$ is $7$. $n$ is $1$.

We can now try to understand the trial quotient formula:

$$ q_t = min(floordiv(\frac{u_n * b + u_{n-1}}{v_{n-1}} ), b - 1) $$

When applied to the first block ($t$ is $0$), where we did $048$ divide $47$, $u_n$ is $0$, $u_{n-1}$ is $4$, $b$ is $10$ (because we are dealing with decimal number), $v_{n-1}$ is $4$.

$$ q_0 = min(floordiv(\frac{0 * 10 + 8}{4}), 10 - 1) = min(2, 9) = 2 $$

(Skipping the two lemmas...)

Theorem 3.3 (Trial Quotient Theorem) states that the quotient is either $q_t$, $q_t-1$ or $q_t-2$, which translates to the number $2$, $1$, and $0$. And we can verify that $1$ is the actual quotient at this block, among one of the three candidates.

Let's look at the final block ($t = 2$), where we would do $152$ divides $47$. Recall that the formula applies to a single block. $47$ has two digits, described as $v_1v_0$. So $n-1$ has value $1$, and so $n$ has value $2$. $152$ has three digits, so it doesn't need to be padded, and is denoted $u_2u_1u_0$ where $u_2$ is $1$, $u_1$ is $5$, and $u_0$ is $2$. plugging in all the values, $u_n = 1$, $b = 10$, $u_{n-1} = 5$, $v_{n-1} = 4$:

$$ q_2 = min(floordiv(\frac{1 * 10 + 5}{4}), 10 - 1) = min(3, 9) = 3 $$

Applying the theorem, that the quotient should be either $3$, $2$ or $1$. The answer is 3 when we do the math by hand, so the theorem holds.

Note that theorem states a prerequisite, the leading digit of the divisor has to be greater than $ floordiv(b / 2) $. In our 4852 dividess 47 example, divisor is 4, and we see that the statement $4 >= floordiv(10 / 2)$, which is false ($ 4 >= 5$) is actually false! So it's just a coincidence the above example worked out. I only wanted to use it to illustrate how you would plug the value and analyze the theorem. See below for a workaround.

Normalization

We know that we can normalize a division by multiplying the dividend and divisor by some value simultaneously ($4 / 7$ is the same as $(4 *3) / (7 * 3)$), so the solution is to multiply the divisor by $floordiv(\frac{b}{v_{n-1} + 1})$ which in our case this evaluates to $floordiv(\frac{10}{5} = 2$, so our division is now $4852 * 2 / 47 * 2 = 9704 / 94$, and we can see that the pre-requisite is now stating $9 >= floordiv(10 / 2)$, which is true. And we can apply the theorem confidently. Note that the final quotient will be the same after the multiplication (the term is normalization), but the remainder will be two times as big, so we have to divide it back (unnormalization). And given the remainder is small enough, such division is easy to perform, compared to the long division. The book gave a detailed walkthrough of a similar example in $Example\ 3.2.$