2
$\begingroup$

I am looking at Fast Recursive Division by Burnikel and Ziegler.

I understand $DivTwoDigitsByOne( ... )$ and $DivThreeHalvesByTwo( ... )$ as they break the numbers down.

So, for example, $12345678/1234$ would be $DivTwoDigitsByOne( 12, 34, 56, 78, 12, 34 )$

And the same for DivThreeHalvesByTwo( ... )

The part I don't get is the $RecursiveDivision( ... )$ part, (page 12), how is the big number broken into 2 numbers.

If I have a very large number $1234567812345678 / 12345678$, how do I break it down into 2 halves?

DivTwoDigitsByOne( 12, 34, 56, 78, 12, 34 )

and

DivTwoDigitsByOne( 12, 34, 56, 78, 56, 78 )

I would I then join the 2 quotients/remainder to form one?

Can someone explain the splitting of the numbers in the $RecursiveDivision( ... )$ case.

$\endgroup$

1 Answer 1

3
$\begingroup$

RecursiveDivision is a simple generalization of DivTwoDigitsByOne. The partitioning works in the same way: you divide each input array into "half-arrays" of $n/2$ digits. Note that in the recursive version, the original DivTwoDigitsByOne is not actually used anymore, the goal is to split into input suitable for a (generalized) DivThreeHalvesByTwo.

Take note the preconditions. First, $B$ must be normalized, so if $B$ has $n$ base-$\beta$ digits, ${\beta^n / 2} \le B < \beta^n$. Second, the quotient $Q = A/B$ must fit in $n$ digits, so $A/B < \beta^n$. Your example of $1234567812345678/12345678$ does not meet either of these requirements: $12345678$ is 8 decimal digits ($\beta = 10$), but it is less than $10^8/2$. The resulting quotient ($100000001$) is also greater than $10^8$.

It follows from the preconditions that $A$ can be represented using at most $2n$ digits, so it can be split into exactly 4 groups of $n/2$ digits, which the algorithm does.

Try $1234567812345678/87654321$, with quotient of $14084506$ instead, which does satisfy the preconditions. $n = 8$ and $\beta = 10$, so the decomposition looks like

  • $A1 = 1234, A2 = 5678, A3 = 1324, A4 = 5678$
  • $B1 = 8765, B2 = 4321$

Walking through the algorithm...

  1. The algorithm calls DivThreeLongHalvesByTwo($A1$, $A2$, $A3$, $B1$, $B2$, $n/2$), This computes $123456781234/87654321$ giving us a quotient of $Q1 = 1408$ and remainder $R = 39497266$. $R$ decomposes into $R1 = 3949$ and $R2 = 7266$.

  2. The algorithm calls DivThreeLongHalvesByTwo($R1$, $R2$, $A4$, $B1$, $B2$, $n/2$). This computes $394972665678/87654321$, giving us a quotient of $Q2 = 4506$ and remainder $S = 2295252$.

  3. The algorithm then returns a quotient of $[Q1, Q2] = 14084506$ and remainder of $S = 2295252$, which is the correct result.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .