8-bit Division

[+Karl G]

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).

[+Andrew Davie]

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.

[+Karl G]

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
	adc XIncrement
	sta CurrentX
    lda ErrorAccumulator+1
    bmi ____skip_increment_y
    lda CurrentY
	clc
	adc YIncrement
	sta CurrentY
    sec
    lda ErrorAccumulator
    sbc ErrorDecrement
    sta ErrorAccumulator
    lda ErrorAccumulator+1
    sbc ErrorDecrement+1
    sta ErrorAccumulator+1
____skip_increment_y
    lda ErrorAccumulator
    clc
    adc ErrorIncrement
    sta ErrorAccumulator
    lda ErrorAccumulator+1
    adc ErrorIncrement+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
	adc Fraction
    bcc ____skip_increment_y
    lda CurrentY
	clc
	adc YIncrement
	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.

[+Karl G]

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?

[Thomas Jentzsch]

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.

[+Karl G]

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.

[Thomas Jentzsch]

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.