# A rather curious division machine

You work as a caretaker in a museum of computing technologies, as one of the people who preserve, store, and archive historical computing-related artifacts.

One day, while making your rounds in an old storage room, you come across a machine you've never seen before. You take it out to inspect it.

It has dials arranged in a division statement, with four dials in the dividend and two in the divisor to the left of the dividend. All the dials are currently set to zero, as so:

              [0] [0] [0]  r.[0]
/---------------
[0] [0]/ [0] [0] [0] [0]


The bottom six dials are turnable, and there's a lever to the right that presumably makes the top four dials calculate.

You set the last dial to "4" and the last dial in the divisor to "2", so they read "0004" / "02". Surely enough, when you pull the lever, on top of the line appears the answer you expect: 2.

              [0] [0] [2]  r.[0]
/---------------
[0] [2]/ [0] [0] [0] [4]


Then you set the dividend to 24 and pull the lever again. On top of the line appears: 12.

              [0] [1] [2]  r.[0]
/---------------
[0] [2]/ [0] [0] [2] [4]


Now you try setting the dividend to 13 and the divisor to 169. As you expect, the answer is 13:

              [0] [1] [3]  r.[0]
/---------------
[1] [3]/ [0] [1] [6] [9]


But then you try evaluating 187 / 13 and the answer is 15 with a remainder of "-8".

              [0] [1] [5]  r.[-8]
/---------------
[1] [3]/ [0] [1] [8] [7]


Somehow, the calculator got its quotient wrong, and returned one too many. Perplexed, you try and divide 288 by 21 and get an even stranger result:

              [0] [1] 7/2  r.[9/2]
/---------------
[2] [1]/ [0] [2] [8] [8]


To your surprise, the calculator has returned a fraction for a digit (and not only that, the remainder is also fractional)! Isn't the whole point of the remainder to deal with the fractional result? you think. Next you try dividing 9028 by 32:

              [3] [-2 [2]  r.[4]
/---------------
[3] [2]/ [9] [0] [2] [8]


And now one of the digits is negative! The answer is indeed 282 if you carry the digits, but for some reason this calculator just flat out refused to borrow one from the three.

You begin to suspect that the calculator isn't just faulty, it runs on a different algorithm entirely. But what is that algorithm?

• I have a feeling that it's easy enough that a math major will get this one right away. – Joe Z. Apr 6 '15 at 10:49

The machine performs polynomial division. The numbers are coefficients of the polynomials. For instance, the last example means (9x³+0x²+2x+8)=(3x+2)(3x²-2x+2)+4

The algorithm is as follows.

Perform long division as normal, but at every step, divide exactly the leftmost digits of the divisor and dividend only. For example, when dividing 288 by 21, after the 1 in the answer the 7 in 78 is divided by the 2 in 21, yielding:

              [0] [1] 7/2
/---------------
(2) [1]/ [0] [2] [8] [8]
[2] [1]
-------
[7] [8]
[7] 7/2
-------
9/2


For the 9028/32 case, a negative digit is obtained because of the subtraction step:

              [3] [-2 [2]
/---------------
(3) [2]/ [9] [0] [2] [8]
[9] [6]
-------
[-6 [2]
[-6 [-4
-------
[6] [8]
[6] [4]
-------
[4]

• I posted this at literally the same second as crazyiman, and admittedly failed to see that last connection! – Xyuzhg Apr 6 '15 at 11:33
• Guess you figured it out earlier, typing my answer out took way less time. – Raziman T V Apr 6 '15 at 12:02
• You figured out the correct algorithm, but crazyiman figured out why the algorithm is that way. Good show, though. – Joe Z. Apr 6 '15 at 16:05