0
\$\begingroup\$

I would like to ask you about division algorithm which I can implement in Assembler for i8080 processor. I know the easiest method is dividing by repeated subtraction but it is very slow. I found many division algorithms but many of them are very very difficult. Can someone give me advice?

\$\endgroup\$
  • \$\begingroup\$ I have ready to use routine for Z80. Seems for 8080 it will be slightly more complex because 8080 lacks some register shift instructions. \$\endgroup\$ – Anonymous Nov 13 '16 at 19:48
  • 2
    \$\begingroup\$ Keep plugging away at the alternate division algorithms until you understand them. In programming, there is no substitute for knowing what you are doing. And, just FYI, 16 bit division on an 8080 will take a long time. The process takes a lot of computation, and an 8-bit ALU needs a lot of operations. \$\endgroup\$ – WhatRoughBeast Nov 13 '16 at 19:49
  • \$\begingroup\$ The 8080 version will also be more complicated since it lacks the 16-bit arithmetic instructions of the Z80. \$\endgroup\$ – WhatRoughBeast Nov 13 '16 at 19:52
  • \$\begingroup\$ Look up COORDIC. It works well in FPGA, but I've no idea whether it maps well onto 8080 infrastructure. As WRB said, keep plugging away at alternates. \$\endgroup\$ – Neil_UK Nov 13 '16 at 20:01
  • \$\begingroup\$ Most division algorithms are exceedingly simple. Do subtract, add back if negative, some shift and repeat until done. Analogous to decimal long division. Complex FPUs do have some sophisticated algorithms, but they're not necessary. Look up some examples. Division is the slowest of the four basic arithmetic functions, essentially one add per bit of result, which could be a number of instructions. The only other thing you have to do is to start with both operands positive, so convert them and keep track of the ex-or of the signs. Only if the signs were different should you negate the result. \$\endgroup\$ – Spehro Pefhany Nov 13 '16 at 20:01
3
\$\begingroup\$

Software division is slow (or complex.) Hardware to do it usually involves more die space or time. Bipolar Integrated Technologies actually implemented a fully combinatorial FP divide in hardware ... back in the day. But such feats aren't often done.

You've already got the basic comments about division that almost anyone trying their hand would apply. But they are slower than they need to be. Even on an 8080A. (I actually still own a few of those, and their support, chips. And my closest friend still has his original Altair 8800 running, which is pretty nice.)

Not so long ago, I got involved in improving the floating point library for a commercial compiler for the MSP430 chip. I was able to dramatically improve the performance by applying what's called "non-restoring division" and by applying some novel assembly-thinking to the design. No other commercial compiler could achieve its speed, at the time. It turns out that I wrote a little documentation on the process I applied in the comments and I'll share those with you here:

;   This routine uses non-restoring division.  If you aren't familiar with it,
;   consider this idea:
;
;   Call each step of the trial subtraction T[n].  At each step we want to test
;   the result of 2 times the prior remainder minus the divisor.  If the trial
;   subtraction succeeds, we just shift the remainder one bit to the left and
;   do the subtraction again.  So at each step our successful trial subtraction
;   it is something like this: ... T[i]=2*T[i-1]-D, T[i+1]=2*T[i]-D ... and so
;   on.  But if the trial subtraction fails, the divisor needs to added back
;   to the remainder before before shifting and doing the next subtraction.
;   Instead, this is T[i+1]=2*(T[i]+D)-D.  But this is just T[i+1]=2*T[i]+D.
;   Comparing these two results, you can see that the shift of T[i] still takes
;   place, but that in this case addition of the divisor is used on the next
;   step instead of subtraction.  Non-restoring division is named that way
;   because it replaces the addition+shift+subtraction used when subtraction
;   from the remainder fails, with shift+addition.  It alternates between
;   shift+subtract and shift+add, depending on the quotient bit generated.
;
;   The division loop is not unrolled here.
;
;   This code needs to produce 24 good mantissa bits as a quotient, where the
;   leading bit is '1', and we then need to also produce one final bit for
;   rounding purposes.  (If the leading bit -- the most significant one --
;   isn't a '1', then we'd lose significance because of the fixed count of
;   generated quotient bits.)
;
;   The actual division code loop is best examined as a coroutine.  Imagine
;   the division routine something like the following diagram.  Since program
;   text is usually viewed under fixed-point fonts, it should render as a
;   readable picture.  I apologize for any difficulties in interpreting it:
;
;             start
;               |
;               v
;           ,-------,
;           |frstbit|
;           '-------'                            ,-------,
;       ,-----> |                                |       |
;       |       v                                v       |
;       |   ,-------,                        ,-------,   |
;       |   |  sub  |                        |  add  |   |
;       |   '-------'----------,  ,----------'-------'   |
;       |  c=1  |        c=0    \/    c=1        |  c=0  |
;       |       v               /\               v       |
;       |   ,-------, <--------'  '--------> ,-------,   |
;       |   |  rlc  |                        |  rla  |   |
;       |   '-------'                        '-------'   |
;       |       |                                |       |
;       |       v                                v       |
;       |   ,-------,                        ,-------,   |
;       '<--|  dec  |                        |  dec  |-->'
;      z=0  '-------'                        '-------'  z=0
;               |  z=1                      z=1  |
;               v                                v
;           ,-------,                        ,-------,
;           | round1|                        | round0|
;           '-------'                        '-------'
;               |                                |
;               v                                v
;               '-------------> end <------------'
;
;   The 'sub' code performs a trial subtraction step and the 'add' code per-
;   forms the trial addition step.  The 'rlc' code shifts in the carry in the
;   case where the quotient bit is a '1'.  The 'rla' code shifts in a '0' bit
;   for the quotient.  The 'dec' code checks for the loop end.  'frstbit'
;   represents the generation of the first quotient bit.  This is special
;   because we know something about the relationship of dividend and divisor
;   (the dividend and divisor both have their MSB=1 and are within a factor of
;   two of each other, which as soon as the first subtraction takes place is no
;   longer known) and we must ensure the leading bit is '1' and may need to
;   adjust the exponent, plus init the loop counter.  The 'round1' and 'round0'
;   parts deal with differences in interpreting the final remainder for
;   rounding, depending on what the last generated quotient bit was.

The above code isn't "unrolled." It's just a single loop. You run it for how many ever bits are required.

The gist of that code is to avoid performing an "add back" if a subtraction turns out to have resulted in a negative result. Instead, the division simply shifts gears and continues along a different path, instead, going "the other way" for a while. It just keeps track of which side of the aisle it is on and shifts over when the assumption changes. You can do this by hand, as well, and you'll see that it works.

The above (and below) examples require the idea of "normalization" to have already occurred. This just means that the leading bit of the dividend and the divisor must both be "1" and that you keep track of the number of shifts needed to get that start. Doing so guarantees that full precision results occur. But such initialization isn't required in non-restoring division. The same algorithm works even when that hasn't occurred.

I tend to perform the division as unsigned, first. (I capture the signs, of course.)

I will often use a dividend that is twice the size of the divisor where the algorithm produces a separate quotient and remainder that is the same size as the divisor. So, for example, I might have a 48-bit dividend, and 24-bit divisor, quotient, and remainder. It's barely any more code or execution time to do that than to force the dividend to be the same size. And I get more complete results. So I usually do it that way. But not always. It depends.

Here's an example of code that is unrolled in a by-8 fashion. It's a lot faster, since the counting control isn't executed nearly so often. But the trade-off is code space. But when you really need speed, it helps a lot:

;   If you aren't familiar with non-restoring division, the consider this idea:
;   Call each step of the trial subtraction T[n].  At each step we want to test
;   the result of 2 times the prior remainder minus the divisor.  If the trial
;   subtraction succeeds, we just shift the remainder one bit to the left and
;   do the subtraction again.  So at each step our successful trial subtraction
;   it is something like this: ... T[i]=2*T[i-1]-D, T[i+1]=2*T[i]-D ... and so
;   on.  But if the trial subtraction fails, the divisor needs to added back
;   to the remainder before before shifting and doing the next subtraction.
;   Instead, this is T[i+1]=2*(T[i]+D)-D.  But this is just T[i+1]=2*T[i]+D.
;   Comparing these two results, you can see that the shift of T[i] still takes
;   place, but that in this case addition of the divisor is used on the next
;   step instead of subtraction.  Non-restoring division is named that way
;   because it replaces the addition+shift+subtraction used when subtraction
;   from the remainder fails, with shift+addition.  It alternates between
;   shift+subtract and shift+add, depending on the quotient bit generated.
;
;   It is unrolled-by-8 in the sense that the code for generating each bit is
;   copied 8 times in inline fashion, to avoid a conditional loop on each bit.
;   Since a decrement and conditional jump require three cycles, doing that
;   once for 8 bits is a big win over doing it once for each bit.
;
;   This code needs to produce 24 good mantissa bits as a quotient, where the
;   leading bit is '1', and we then need to also produce one final bit for
;   rounding purposes.  (If the leading bit -- the most significant one --
;   isn't a '1', then we'd lose significance because of the fixed count of
;   generated quotient bits.)
;
;   The actual division code loop is best examined as a coroutine.  Imagine
;   the division routine something like the following diagram.  Since program
;   text is usually viewed under fixed-point fonts, it should render as a
;   readable picture.  I apologize for any difficulties in interpreting it:
;
;         start     ,-------,                                ,-------,
;           |       |       |                                |       |
;           |       |       v                                v       |
;           |       |   ,-------,                        ,-------,   |
;           v       |   |movbyte|                        |movbyte|   |
;       ,-------,   |   '-------'                        '-------'   |
;       |frstbit|   |       |                                |       |
;       '-------'   |       v                                v       |
;           |       |   ,-------,                        ,-------,   |
;           |       |   |rlc/sub|                        |rla/add|   |
;           v       |   '-------'----------,  ,----------'-------'   |
;           '------ | ----> |        c=0    \/    c=1        |  c=0  |
;                   |  c=1  v               /\               v       |
;                   |   ,-------, <--------'  '--------> ,-------,   |
;                   |   |rlc/sub|                        |rla/add|   |
;                   |   '-------'----------,  ,----------'-------'   |
;                   |  c=1  |        c=0    \/    c=1        |  c=0  |
;                   |       v               /\               v       |
;                   |   ,-------, <--------'  '--------> ,-------,   |
;                   |   |rlc/sub|                        |rla/add|   |
;                   |   '-------'----------,  ,----------'-------'   |
;                   |  c=1  |        c=0    \/    c=1        |  c=0  |
;                   |       v               /\               v       |
;                   |   ,-------, <--------'  '--------> ,-------,   |
;                   |   |rlc/sub|                        |rla/add|   |
;                   |   '-------'----------,  ,----------'-------'   |
;                   |  c=1  |        c=0    \/    c=1        |  c=0  |
;                   |       v               /\               v       |
;                   |   ,-------, <--------'  '--------> ,-------,   |
;                   |   |rlc/sub|                        |rla/add|   |
;                   |   '-------'----------,  ,----------'-------'   |
;                   |  c=1  |        c=0    \/    c=1        |  c=0  |
;                   |       v               /\               v       |
;                   |   ,-------, <--------'  '--------> ,-------,   |
;                   |   |rlc/sub|                        |rla/add|   |
;                   |   '-------'----------,  ,----------'-------'   |
;                   |  c=1  |        c=0    \/    c=1        |  c=0  |
;                   |       v               /\               v       |
;                   |   ,-------, <--------'  '--------> ,-------,   |
;                   |   |rlc/sub|                        |rla/add|   |
;                   |   '-------'----------,  ,----------'-------'   |
;                   |  c=1  |        c=0    \/    c=1        |  c=0  |
;                   |       v               /\               v       |
;                   |   ,-------, <--------'  '--------> ,-------,   |
;                   '<--|rlc/dec|                        |rla/dec|-->'
;                  z=0  '-------'                        '-------'  z=0
;                           |  z=1                      z=1  |
;                           v                                v
;                       ,-------,                        ,-------,
;                       | round1|                        | round0|
;                       '-------'                        '-------'
;                           |                                |
;                           v                                v
;                           '-------------> end <------------'

Well, that's it for now. If you have any questions about the process, ask. I've done a lot of 8080 assembly coding. But it has been several decades since, so bear with me if I seem a bit rusty.

|improve this answer|||||
\$\endgroup\$
0
\$\begingroup\$

You need to use the shift and subtract algorithm. An example can be found here; division.

In the 70's I was having a problem with division on a propritary processor that had a 16 digit BCD register. I was counting the subtractions and watching for the underflow. When I single stepped everything seemed fine. I was trying to calculate eight differnet percentages. One day, I left the thing running and went to lunch. When I came back, the first percentage was done. Doing some calculations showed I could have started a small number into a large number division back then and it would not be done now.

|improve this answer|||||
\$\endgroup\$
  • \$\begingroup\$ The shift instructions you need are RAR and RAL. \$\endgroup\$ – owg60 Nov 13 '16 at 22:41
  • \$\begingroup\$ Also RRC and RLC. You need to be able to shift the bits into the carry to test there state. \$\endgroup\$ – owg60 Nov 13 '16 at 22:55

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.