IGNORED

# 8-bit Division

## Recommended Posts

I have found routines that allow for division of one 8-bit number by another, giving the integer and the remainder. I was wondering though if anyone knew a way to do division of two 8-bit numbers where the divisor is greater than the dividend, and the answer would effectively be a fraction of 256 that is closest to the answer. So, for example if I were dividing 8 by 56, a calculator would give ~ 0.143, and I would want the result to be 37 (as 37/256 would be the closest to the actual answer).

I've not been able to find a generalized function that does this, and was wondering if such a thing exists (and also wondering how bad the cycle count would be).

##### Share on other sites

I'd extend the 8-bit divide to a 16-bit divide by 8-bit.  That is, shift the numerator from the form 0x00nn to 0xnn00 and then use the high byte as the result. You may like to add 0x80 to the 16-bit result first for rounding.

But division is generally a terrible idea on the 6502 and are you sure there's not a better way to do things?

As to cycles, I'd say a couple of hundred at best.

However rather than saying "here's the solution, how do I do it efficiently?" in general I'd prefer to see "here's the problem I'm trying to solve".

I wrote all the following and then thought better of it... too slow....

Dividing is multiplying by the reciprocal.  So you could use that to work with a 16-bit reciprocal table and do an 8x16 multiply to get an accurate result. Here's a walkthrough... which I do not recommend, but leaving here for posterity...

Have a table of 256 reciprocal values.  Then it's an 8-bit multiply and you use the high byte of the result, I think.  e.g., lookup reciprocal of 56 which is 256/56 = 4 (from the table). Actually 4.57 but we'r dealing in ints, and so 4 * 8 (numerator) = 32 your answer.  For better precision move to an 8x16 bit multiply. Then, your table is still 256 entries (now words).  So, now we have 0x492 in the table, and 0x492 * 8 = 0x2490. Take the high 8 bits giving 0x24 = 36.  Or, if you round, then 0x2490+0x80 = 0x2510, and high bits -> 0x25 which is 37.

So in summary - take your divisor (56) indexed into a word table (16 bit values) of reciprocals of numbers from 0-256 represented as a \$XY format in hex, which is 0x.0y (that is, a virtual decimal point between two 8-bit values) integer part and fractional part. For 56, we get 0x4. 0x92 (0x492). Do a standard multiply 8 bit x 16 bit of your numerator (8) * this value.  So, 8 * 0x492.  This gives us a 16-bit result.  Add 1/2 for rounding, so we have 0x2490 + 0x80 --> 0x2510.  Now use the top 8-bits as your answer.  0x25 = 37.

That's generalised. Cost is basically an 8x16 multiply which isn't super-efficient either, I admit.

I'm sure others will offer much better ideas/advice. I'm just getting the ball rolling here.

##### Share on other sites

Okay; fair enough. I'm messing with line drawing and Bresenham's line algorithm. I was wondering if I could eliminate the 16-bit math needed for every point on the line. If I had the slope as a 8-bit fraction, I could save a number of cycles for each point drawn (at the expense of a small amount of accuracy). For a certain length of line, computing this number upfront will save cycles if enough points are plotted. The question is how long would the line have to be for it to be a net savings, and to know that I'd have to be able to approximate the cycles consumed by the ill-advised division.

So, for example, here is my translation of Bresenham's line algorithm to 6502 assembler:

```DrawLineXFirst
jsr InitLine
DrawLineLoop
jsr DrawPoint
lda CurrentX
clc
sta CurrentX
lda ErrorAccumulator+1
bmi ____skip_increment_y
lda CurrentY
clc
sta CurrentY
sec
lda ErrorAccumulator
sbc ErrorDecrement
sta ErrorAccumulator
lda ErrorAccumulator+1
sbc ErrorDecrement+1
sta ErrorAccumulator+1
____skip_increment_y
lda ErrorAccumulator
clc
sta ErrorAccumulator
lda ErrorAccumulator+1
sta ErrorAccumulator+1
lda CurrentX
cmp X1
bne DrawLineLoop
jsr DrawPoint
rts
; End DrawLineXFirst```

Here would be an equivalent version using the Fraction variable for y adjustment instead:

```DrawLineXFirstFraction
jsr InitLine
DrawLineLoop
jsr DrawPoint
lda FractionAccumulator
clc
bcc ____skip_increment_y
lda CurrentY
clc
sta CurrentY
____skip_increment_y
lda CurrentX
cmp X1
bne DrawLineLoop
jsr DrawPoint
rts
; End DrawLineXFirstFraction```

Many cycles are saved per iteration in the second version.

##### Share on other sites

I'm realizing now that I don't really have to do division at all to do this - I can just use the ratio as is. I can add the dividend into a accumulator variable on each iteration, and when it's greater or equal to the divisor, increment Y (or X for the complementary function), and subtract the divisor from the accumulator variable. I think this will still save cycles from a standard Bresenham algorithm, but of course I need to test my idea.

Edit: The more I think of it though, the more it sounds like I'm still doing pretty much the same thing as the standard algorithm. The standard algorithm has you double the X and Y deltas for this purpose, though, and I'm not entirely sure why.

@Thomas Jentzsch - since you have done a Bresenham's line algorithm recently, do you have thoughts on optimizations?

##### Share on other sites

5 hours ago, Karl G said:

@Thomas Jentzsch - since you have done a Bresenham's line algorithm recently, do you have thoughts on optimizations?

You should have a look at the c=hacking net magazine (e.g issue 16). There are some great articles from Stephen Judd which I used for my Elite demo. I based my Qix line demo on this. Everything it 8 bit though, not sure why you need 16 bit.

##### Share on other sites

1 hour ago, Thomas Jentzsch said:

You should have a look at the c=hacking net magazine (e.g issue 16). There are some great articles from Stephen Judd which I used for my Elite demo. I based my Qix line demo on this. Everything it 8 bit though, not sure why you need 16 bit.

Thanks! I will check it out. I was basing the need for 16-bit on the algorithm presented in the Bresenham's line algorithm Wikipedia page:

```plotLine(x0, y0, x1, y1)
dx = x1 - x0
dy = y1 - y0
D = 2*dy - dx
y = y0

for x from x0 to x1
plot(x,y)
if D > 0
y = y + 1
D = D - 2*dx
end if
D = D + 2*dy```

If dx or dy can be greater than 128, then it ends up going past 8-bit. I was looking for a way to rewrite it to avoid the need for 16 bits to save cycles.

##### Share on other sites

Halve the D value:

```D = dy - dx/2
...
D = D - dx
...
D = D + dy```

The initial D value has a slight rounding error then. But this only causes that a few on the edge pixels might change. Which will not be noticed.

## Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

×   Pasted as rich text.   Paste as plain text instead

Only 75 emoji are allowed.