I am trying to understand a particular concept in this lecture. The lecture goes on to describe that to compute a division of $\frac{a}{b}$, you have to:

  1. Compute high-precision representation of $\frac{1}{b}$ first (that is the floor of $\frac{R}{b}$ where $R$ is a large value that is easy to divide by).

  2. Multiply the high-precision representation of $\frac{1}{b}$ by $a$ then divide by $R$? (The lecture doesn't state this part).

In the process of using Newton's method to estimate $\frac{R}{b}$ (see page 3), the lecture states (in the beginning of page 4) that 'division requires multiplication of different-sized numbers at each iteration'. This leads to the a complexity of $\theta(d^\alpha)$ for some $\alpha \geq 1$, as argued in page 4.

How's that the case? In the example given on page 3, division requires multiplication of d-sized numbers on each iteration leading to a complexity of $\theta(\log{d} * d^\alpha)$. So, how exactly is the statement above, in bold, true?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.