After reading the thread on binary to decimal I tried implementing the reverse algorithm trying to avoid lookup tables and/or multiply by 10 routines. This is what I came up with.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

Can't say I've really thought it through, but my first thought is that it's a
shame to do all that correction in the code when the 6502 is already set up
to do it in the hardware.

You could do you're divisions by two in a more "conventional" manner by
shifting the decimal out the left by doubling it (similar to the way it's done
in the hex to decimal routine you just posted in the hex to decimal thread)
(which, incidently, is the double-dabble use of decimal mode I refered
to in another thread) and subtracting the BCD equivalent of the binary (in
BCD of course)


However it would introduce the problem of restoring (just as with a more
conventional shift and subtract division) so I don't know if it would end up
saving you anything.

But it might be something to investigate.
(and if you're really adventurous you could try doing a nonrestoring
version )

I'd never heard of the BIN>BCD algorithm being called 'Double-Dabble' before. It might be a term that never made it across the pond. A quick troll of the internet turned up this:

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

Thankyou for the explanation, BitWise. 110011101B is 413, not 421, but the method does work. The only error was in doubling 25 and adding 1 and getting 52 instead of 51.

I copied the text from some a university lecture notes. Just goes to show the quality of education material these days.

_________________
Andrew Jacobs
6502 & PIC Stuff - http://www.obelisk.me.uk/
Cross-Platform 6502/65C02/65816 Macro Assembler - http://www.obelisk.me.uk/dev65/
Open Source Projects - https://github.com/andrew-jacobs

Gee whiz

Sorry guys.

Guess I should have explained.

I didn't realize the term "double dabble" was so obscure. It was, like, the first
thing they taught us after they explained binary. I just kind of assumed any
one who knew binary would be familiar with (the term) "double dabble"

Do I need to explain nonrestoring division?

I'm not sure if you're serious about this, or if you're being condescending. The term 'double dabble' is utterly unheard of where I live. I apologize, but, well, that's just the way it is.

As far as non-restoring division is concerned, to bring things back on topic, does this refer to division that doesn't require an error-corrective "add" at the end of the division loop? If not, then you might want to provide links to some information. It might prove educational to some here.

"
I'm not sure if you're serious about this, or if you're being condescending.
"

No, I didn't mean to be condescending. More like trying to get my bearings.
I would have thought that "double dabble" would be better known than
"nonrestoring division" but I don't (didn't) think of either of them as
particularly obscure.

For division by shifting and subtracting, you align the most significant bits
of the remainder (dividend) and the divisor by shifting the remainder
left and then you subtracting the divisor from it. If the result is negative you,
"restore" the remainder by adding the divisor back in and shifting again
and then do your subtraction. You keep the remainder positive and
reduce it towards zero

For nonrestoring you keep the negative remainder and continue to shift,
reducing it towards zero by adding the divisor if the remainder is negative
and subtracting the divisor if the remainder is positive. If the remainder is
negative when you're done with your shifting, you have to fix things up.

Having said that, I was half joking when I suggested nonrestoring in BCD.
I'm sure it can be done, and it would probably be an interesting exercise,
but I suspect and/or assume it would be more trouble than it would be
worth (how ever I don't know that)

I didn't find anything on line that looked very good but here's a couple links

http://cs.uns.edu.ar/~jechaiz/arquitect ... oring.html

http://www.computer-engineering.org/alg ... ision.html


"Programing the 6502" by Rodnay Zaks Has some code in it. I haven't
tryed it. (and I've heard that some of the code from that book is no good)
I'll dig it out and post it here.

Remember that the doubling and adding 1 in the double/dabble method must be done in the target base, which in this case is ten. You can't just do ASL to double, or INC to add 1. This makes the method take just a couple of bytes more memory and anywhere from 1.24 to 3.00 times as long to execute as what I posted at http://www.6502.org/source/integers/hex2dec.htm The speed of this one depends on how many zeroes and ones it finds, being faster at the zeroes. These speed comparison numbers are for converting a single-byte input, with a range of 00-FF.

My 6502 and 65816 division routines are at http://www.6502.org/source/integers/umm ... modfix.htm

The reversal of Garth's algorithm is clearly:



Just as simple and straightforward (and efficient) as the transformation in the other direction!

The idea in words:

The BCD representations of 1,2,4,8,16,32,64,128 are kept in the tables. When transforming to BCD the table entries corresponding to the individual bits are added together. When transforming from BCD to binary these entries are subtracted from the input value instead.

For comparison I would write Garth's algorithm as follows: