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.

  • 2
    $\begingroup$ @Thijs I could, but that would be a more computationally expensive operation than I would like. $\endgroup$ – Peter Olson Sep 3 '11 at 0:43
  • $\begingroup$ I would expect you to need to keep track of parity with a negative base, since digits in "odd" positions (from right to left) count "positive" while digits in even positions count negative. $\endgroup$ – Arturo Magidin Sep 3 '11 at 3:56
  • $\begingroup$ @Arthur I would imagine so, too. It's confusing me how 11 (negadecimal for -9) can go into 12 (negadecimal for -8) once (or perhaps -1 times, since the first one on the top is in an even position). $\endgroup$ – Peter Olson Sep 3 '11 at 4:04
  • $\begingroup$ @Peter: Well, in the usual division algorithm, if you were dividing $-8$ by $-9$, the answer would be $-8 = 1(-9) + 1$ (since we require the remainder $r$ to satisfy $0\leq r\lt |d|$, where $d$ is the divisor). So certainly "11" should go into "12" once, with a remainder of 1. But perhaps, rather, the issue is that this "12" is not really a "12", because the 1 corresponds to an even power of the base and 2 to an odd power, where as in representing -8 the 1 corresponds to an odd power of the base, and 2 to an even power. $\endgroup$ – Arturo Magidin Sep 3 '11 at 4:26
  • 1
    $\begingroup$ I looked at your multiplications. It would seem that by some coincidence, the decimal representation of (the negadecimal product) 116233 × 11 is 862443, and the decimal representation of (the negadecimal product) 112233 × 11 is 826443. The fact that the two product differ only in two digits seems significant, and it seems quite likely that a transposition error happened somewhere in your calculations. $\endgroup$ – Niel de Beaudrap Sep 3 '11 at 12:45

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.

  • $\begingroup$ I already have algorithms that (at least seem to) successfully perform addition, subtraction, and multiplication of integers in negative bases. Since using those means I don't have to worry about weird borrowing in the subtractions, would it make things simpler? $\endgroup$ – Peter Olson Sep 3 '11 at 18:52
  • $\begingroup$ The "weird borrowing" seems very natural in the subtractions, to me; they play exactly the role of "normal borrowings" in positive-base subtractions, but simply act differently because the base is negative. It is when you must decide which multiple of the divisor that you should subtract, in the course of a division, that things become slightly peculiar. Might you post a link to a place where I can see your algorithms? $\endgroup$ – Niel de Beaudrap Sep 3 '11 at 20:52
  • $\begingroup$ I don't know if this will be easily comprehensible to you, but my algorithms are in this Javascript file. If you need a more human-readable version, I could make something. $\endgroup$ – Peter Olson Sep 3 '11 at 23:17
  • $\begingroup$ @Peter Of The Corn: From inspection, in the case of a negative base, you simply reduce subtraction to addition in the sensible way; but this is not the most efficient way to do things, because negating will give you a longer digit string half of the time and doesn't streamline anything. The "weird borrowing" is more efficient, and can work with the same code as positive-base subtraction with little modification. Of course, multiplication and addition don't need the "weird borrowing", they only need the reverse, which is the "weird carrying" which is also implicit in negative bases. $\endgroup$ – Niel de Beaudrap Sep 3 '11 at 23:50
  • $\begingroup$ 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.) $\endgroup$ – Peter Olson Sep 4 '11 at 3:39

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.