Can anyone tell me if this simple division routine should work or not? I'm just trying to have a simple 8-bit division. i.e. devide one 8bit number by another 8bit number and come up with an 8bit result.

Never mind... I found that it does work!

Thanks anyway.

By the way, there are also a couple of division routines on the wiki at:

http://6502org.wikidot.com/software-math-intdiv

Division routines are a fairly common request here on the forum, so I am planning to add more routines to the article, but it's been awhile since I've updated it.

Your routine is fine for simple uses, though. Its main disadvantage is that the time it takes varies so widely, e.g. 240/3 loops many times, but 21/7 only loops a few times. However, that's often not that big of a deal for 8-bit division.

I used a table based Multiplication routine... Very fast as there is no looping involved, but I couldn't find anything equivilent for division. Is there such a thing?

Sort of, use a table of reciprocals and multiply.

But it's more usual to use a small table of approximate reciprocals
and refine the values using Newton-Raphson iteration - if you have
fast enough multiplication and you want enough bits to make
the additional rigamarole worth while (if you're only doing
8 bits/8bits there's probably better ways especially if you're using
Newton-Raphson to refine your reciprocals, if you're doing
64bits/64bits it might be worth it)

For some values you can only have approximate reciprocals.
like the binary analog of (decimal) 1/3 being .333...
(in binary, .010101...)
So you run into the complication of how accurate is accurate enough
and how do you get the remainder if you need it and where was the
decimal point?
3 x .333... = .999... presumably you'd like to get 1 so now
you have to decide how when and where to round.

And then there's logarithms ..

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Wow, it is shocking to see how so few people remember "rationals." Don't divide until you need to, basically.

The PC/GEOS (aka GeoWorks Ensemble) operating system used rationals for its GUI and was one of the first OSes on the entire planet to make use of scalable font technology, all without an FPU, and with adequate performance on an 8086 processor.

Rationals are just fractions, in case you were wondering. For example, the approximation of pi, 355/113, is a rational, as is 31415/10000. Each rational would be stored in memory as two, adjacent integers of appropriate size.

I have recently acquired a couple of BBC Micro-related books off of eBay, and one of them (at least) had multiplication and division routines; at the moment, I'm working off the top of my head, so the following is in "pseudo-code" rather than assembler, but should be pretty much in line with what I read:

To perform: (dividend / divisor) => [quotient, remainder]; divisor != 0


As I _am_ working off memory here, I may well be off with the above algorithm, but it would be about right; also, the way the algorithm is coded, it is not just the "opposite" of the equivalent multiply routine (i.e. shift-and-add), but would be easy to implement in 6502 assembler.

HTH,

--Martin

_________________
Martin Penny

.sig in beta - full release to follow.

I knew I'd forget something - if the algorithm has an extra line added to it, it should then work (and, yes, it assumes unsigned integers; and "shift_count" is the size of the dividend).

[...]
loop:
quotient := (quotient << 1);
dividend := (dividend << 1); \ Shifts MSB out
[...]

--Martin

_________________
Martin Penny

.sig in beta - full release to follow.

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

Just checking: this is an approximate log, yes? Any idea roughly how accurate the resulting multiplication and division will be?

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?

I think the only way to do division using a multiplication table is with the use of a binary search method.
Using this 16x16 multiplication table, let's see how this would work

4000:01 02 03 04 05 06 07 08 09 0A 0B 0C 0D 0E 0F 10
4010:02 04 06 08 0A 0C 0E 10 12 14 16 18 1A 1C 1E 20
4020:03 06 09 0C 0F 12 15 18 1B 1E 21 24 27 2A 2D 30
4030:04 08 0C 10 14 18 1C 20 24 28 2C 30 34 38 3C 40
4040:05 0A 0F 14 19 1E 23 28 2D 32 37 3C 41 46 4B 50
4050:06 0C 12 18 1E 24 2A 30 36 3C 42 48 4E 54 5A 60
4060:07 0E 15 1C 23 2A 31 38 3F 46 4D 54 5B 62 69 70
4070:08 10 18 20 28 30 38 40 48 50 58 60 68 70 78 80
4080:09 12 1B 24 2D 36 3F 48 51 5A 63 6C 75 7E 87 90
4090:0A 14 1E 28 32 3C 46 50 5A 64 6E 78 82 8C 96 A0
40A0:0B 16 21 2C 37 42 4D 58 63 6E 79 84 8F 9A A5 B0
40B0:0C 18 24 30 3C 48 54 60 6C 78 84 90 9C A8 B4 C0
40C0:0D 1A 27 34 41 4E 5B 68 75 82 8F 9C A9 B6 C3 D0
40D0:0E 1C 2A 38 46 54 62 70 7E 8C 9A A8 B6 C4 D2 E0
40E0:0F 1E 2D 3C 4B 5A 69 78 87 96 A5 B4 C3 D2 E1 F0
40F0:10 20 30 40 50 60 70 80 90 A0 B0 C0 D0 E0 F0 00


I think most know how to do a binary search. You have a max-length and min-length which are the number of entries for each value. The max would then be 15 ($F) and the min starts out at 0. We add the two lengths and divide by 2 with a simple LSR. We also have to check that the difference between MIN and MAX is <= 1 to signal the end of a search.

Say for instance we want to find 12/5. The 5 being the divisor is the fifth row we start our search (starts at $4040)
We start with (MIN=0 + MAX=15)/2 = 15/2 = 7. We then put 7 into the x-reg and add to $4040,x. We see that the 7th value of the 5th line = 40 ($28). Compare the value 12 with 40 makes it less-than and also NOT-EQUAL, so we will store MAX as 7 and keep MIN as 0. If it is greater-than, we would make MIN=7 and keep MAX as 15. If they are equal then we stop.

Now get the half way point of the 2 ranges again with a simple LSR. Also check that the difference between MIN and MAX is <= 1.

(MIN=0 + MAX=7)/2 = 7/2 = 3. The 3rd value of $4040,x is 20 ($14). Our original value is still less-than this value, so halve the MIN/MAX values again.

(MIN=0 + MAX=3)/2 = 1. The 1st value of $4040,x is 10 ($0A). Our original value of 12 is now greater-than this value, now we make MIN=1.

(MIN=1 + MAX=3)/2 = 2. The 2nd value of $4040,x is 15 ($0F). Our original value of 12 is now less-than this value, and we make MAX =2.

(MIN=1 + MAX=2)/2 = 1. Our program should now have caught the MIN/MAX difference of <= 1. and we have also determined that our original value and last value found do not match. Which means we have a value between the number at MIN and the number at MAX. All that is left is to subtract the value at MIN from the original to get our remainder. And since our look-up table is using an index of 0-15 (0-$F), but our division factors deal with 1-16 (1-$10), we have to increment MIN by 1 to get the actual divisor.

12 (original value) - 10 (x=MIN=1; value at $4040,x) = 2 (remainder)
MIN + 1 = divisor

RESULT: 12/5 = quotient = 2 and remainder = 2

This only took 3 times thru the loop to find the result, which one will find that is pretty much standard times through the loop for division of any two 8-bit numbers.

BTW: since this search method takes longer for smaller factors, we can do a simple quick check to decide which routine would be faster. The cut-off line seems to be with 4-5 times through the loop. So if we look at the 4th or 5th column of the divisor and compare the value there with the dividend. If less-than we use the routine in the very first post of this thread. If greater-than then this binary-search method will be faster.

As an example, a division of 46/5 using the first-post method will take 9 times through the loop. This binary-search method will still only take 3-4 loops. This doesn't seem like much time savings being twice as fast, but this is just a small table. Imagine the time saving on 16-bit, 24-bit or 32-bit values.

I guess the next problem to solve is, is the speed and size of these tables worth the price of memory?

_________________
http://WilsonMinesCo.com/ lots of 6502 resources
The "second front page" is http://wilsonminesco.com/links.html .
What's an additional VIA among friends, anyhow?