I've been reading through the long division algorithm exposed in the Knuth book for a week and I still miss some details. There's an implementation of such algorithm in "Hacker's Delight" by Warren, however basically the author explains that it's a translation of the classic pencil and paper method and the Knuth book is the one that provides all the details. I really want to understand the analysis but for some reason that I can't quite understand it is a bit strange in the exposition.
It firstly starts by saying that
"a moment's reflection about the ordinary process of long division shows that the general problem breaks down into simpler steps, each of which is the division of an $n+1$-place dividend $u$ by an $n$ place integers $v$.
I of course agree with such intuition, but it's because I've been taught in that way, not because there's a proof. It shouldn't be hard to work out the why however since
$$ \begin{array}{l} u = \sum_{j=0}^{m+n-1} u_j b^j \\ v = \sum_{j=0}^{n-1} v_j b^j \end{array} \Rightarrow \frac{u}{v} = \frac{\sum_{j=0}^{m+n-1} u_j b^j}{v} = \frac{\sum_{j=m-1}^{m+n-1} u_j b^j}{v} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} = \frac{\sum_{j=0}^{n} u_{j+m-1} b^{j+m-1}}{v} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} = \frac{\sum_{j=0}^{n} u_{j+m-1} b^j}{v}b^{m-1} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} = \left(q_{m-1} + \frac{r_{m-1}}{v} \right)b^{m-1} + \frac{\sum_{j=0}^{m-2} u_j b^j}{v} = q_{m-1}b^{m-1} + \frac{r_{m-1}b^{m-1} + \sum_{j=0}^{m-2} u_j b^j}{v} $$ where $0 \leq r_{m-1} \leq v - 1$, using an induction argument I can show that I have always to do this (i.e. that the problem is to perform several iteration of dividing an $n+1$ digit number by an $n$ digit number. One key observation is that of course if $$ 0 \leq q_{m-1} \leq b - 1 $$ then $q_{m-1}$ represent the most significant digit of the division
Later the problem is stated as
Let $u = (u_nu_{n-1} \ldots u_1 u_0)_b$ and $v = (v_{n-1} \ldots v_1 v_0)_b$ be nonnegative integers in radix-$b$ notation, where $u/v < b$. Find an algorithm to determine $q = \left\lfloor u/v \right\rfloor$.
From this point I have a problem (which is the object of my question). After the observation made that the condition $u/v < b$ is equivalent $(u_n \ldots u_1) < (v_{n-1} \ldots v_0)$ I would also observe that $v_{n-1}$ is not necessaraly 0. It is later defined the quantity $$ \hat{q} = \min \left( \left\lfloor \frac{u_n b + u_{n-1}}{v_{n-1}} \right\rfloor,b-1\right) $$ Where is not actually stated any condition on $v_{n-1}$, which at least shouldn't be $0$. Then the author proves both theorems $A$ and $B$ which they make perfectly sense to me if $v_{n-1} \neq 0$.
One could argue that before the theorems it is said
...as long as $v_{n-1}$ is reasonably large...
However I think that this statement should be interpreted more like "we now show how much large $v_{n-1}$ has to be in order to..." So there's actually no assumption here, he wants to show that.
The question is... Shouldn't basically the condition $v_{n-1} \neq 0$ be clearly stated? I'm sure there's something subtle about the condition $u/v < b$ that I'm missing...
(I have other questions but I'll go through that later)
