0
$\begingroup$

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?

$\endgroup$

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.