+Karl G Posted January 29, 2022 Share Posted January 29, 2022 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). Quote Link to comment Share on other sites More sharing options...

+Andrew Davie Posted January 29, 2022 Share Posted January 29, 2022 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. 1 Quote Link to comment Share on other sites More sharing options...

+Karl G Posted January 29, 2022 Author Share Posted January 29, 2022 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. Quote Link to comment Share on other sites More sharing options...

+Karl G Posted January 30, 2022 Author Share Posted January 30, 2022 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? 1 Quote Link to comment Share on other sites More sharing options...

Thomas Jentzsch Posted January 30, 2022 Share Posted January 30, 2022 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. 1 Quote Link to comment Share on other sites More sharing options...

+Karl G Posted January 30, 2022 Author Share Posted January 30, 2022 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. Quote Link to comment Share on other sites More sharing options...

Thomas Jentzsch Posted January 31, 2022 Share Posted January 31, 2022 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. 1 Quote Link to comment Share on other sites More sharing options...

## Recommended Posts

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