5
$\begingroup$

What algorithm can I use to divide numbers in a negative base?

To divide numbers in positive bases, I am accustomed to using short division:

       1  1  0  4  9  3  2  r18 23 |2  5  4  1  3  4  5  4          2  1 11 21  7  6 

That is, 23 goes into 25 once, leaving over 2. 23 goes into 24 once, leaving over 1. 23 goes into 11 zero times, leaving over 11. 23 goes into 113 four times, leaving over 21, and so on until you reach the end with a remainder of 18.

This same algorithm yields incorrect results when performed in a negative base. In a negative base, the same digits being divided should somehow yield this solution:

      1 1 1 5 5 6 9  r 193 23 |2 5 4 1 3 4 5 4 

I cannot figure out what method could get me to this solution. How can I use short division in a negative base?

EDIT: I updated my examples because of the errors in them pointed out in the comments.

  • 0
    @Niel I just tried a few things too, so I updated my question with a different example. I hope this one is correct.2011-09-03

1 Answers 1

2

Long division works because it counts the number of times you must subtract the divisor from the dividend, in order to exhaust the dividend. So first you have to be careful to do subtraction correctly.

Consider the following subtraction in neg-decimal: 13 − 24. First thing that you see is that the ones place of 13 is too small: we need to borrow. But also keep in mind that to borrow, you have to increase the value of the next higher place value!

$\begin{align*}\begin{array}{lll} & \!\!\not{\!1}^{\,2} & \!\!\not{\!3}^{\,13} \\ - & 2 & 4 \\ \hline & & 9 \end{array}\end{align*}$ We lucked out: not only were we able to take care of the units place, but "borrowing" allowed us to carry out the subtraction easily in the negative-tens place as well. And thus, 13 − 24 = 9.

Let's try your example division. What I am presenting does not represent an algorithm, because throughout I am making little observations about how to proceed which might not be easy to make automatically. But the result should be correct. The first few steps are simple enough:

First steps of long division

You might think that the next digit is zero. It's a trap! I can't tell you what a computer should do here; but notice that if you were to try to subtract 23 from 11, you'd have to borrow to do the difference in the ones place anyhow. So why don't we try that?

The first tricky step of the long division

Hunh. Go figure. Well, things are going to get a bit messy from here on out, so why don't we pull out our multiplication table for 23 in nega-decimal?

$\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} \hline \textbf{aah!!} & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline 23 & \;\;23\;\; & \;\;46\;\; & \;\;69\;\; & \;\;72\;\; & \;\;95\;\; & 1918 & 1921 & 1944 & 1967 \\\hline \end{array}$

Oooh...kay. Well, it will save us time, anyway. Here's how the rest of the division goes:

The full long division

Notice how on the lines with 83 and 84, we don't satisfy ourselves with subtracting 72; by borrowing an extra 10 for the units place, we can get as high as subtracting 95. Now, let's verify!

$\begin{align*} 25413454_{-10} \;&=\; -15392646_{10} \\ 23_{-10} \;&=\; -17_{10} \\ 1115550_{-10} \;&=\; 90450_{10} \\ \\ \\ \bigl(-15392646 - 4) \div (-17) \;&=\; 90450\;. \end{align*}$

So, it's correct! But how would you make an algorithm out of it? I'm not sure... yet.

  • 0
    I'm sorry I doubted your weird borrowing. :) I misunderstood your answer and thought that that was the difficulty in the divison. I looked at it again, and it makes sense (adding 1 to borrow made me smile). I'll implement it. (BTW, I'm impressed that you were able to read through all my kludge.)2011-09-04