linguistic:paraphrasing, linguistic:voice_change
Performance

On each iteration, the most time-consuming task is to select β i {\displaystyle \beta _{i}}. We know that there are b {\displaystyle b} possible values, so we can find β i {\displaystyle \beta _{i}} using O (log (b)) {\displaystyle O(\log(b))} comparisons. Each comparison will require evaluating d i − m β i {\displaystyle d_{i}-m\beta _{i}}. Let k {\displaystyle k} be the number of digits in the dividend n {\displaystyle n} and l {\displaystyle l} be the number of digits in the divisor m {\displaystyle m}. The number of digits in d i ≤ l + 1 {\displaystyle d_{i}\leq l+1}. The multiplication of m β i {\displaystyle m\beta _{i}} is therefore O (l) {\displaystyle O(l)}, and likewise the subtraction of d i − m β i {\displaystyle d_{i}-m\beta _{i}}. Thus it takes O (l log (b)) {\displaystyle O(l\log(b))} to select β i {\displaystyle \beta _{i}}. The remainder of the algorithm are addition and the digit-shifting of q i {\displaystyle q_{i}} and r i {\displaystyle r_{i}} to the left one digit, and so takes time O (k) {\displaystyle O(k)} and O (l) {\displaystyle O(l)} in base b {\displaystyle b}, so each iteration takes O (l log (b) + k + l) {\displaystyle O(l\log(b)+k+l)}, or just O (l log (b) + k) {\displaystyle O(l\log(b)+k)}. For all k − l + 1 {\displaystyle k-l+1} digits, the algorithm takes time O ((k − l + 1) (l log (b) + k)) {\displaystyle O((k-l+1)(l\log(b)+k))}, or O (k l log (b) + k 2) {\displaystyle O(kl\log(b)+k^{2})} in base b {\displaystyle b}.