So far, the easiest algorithm I can think of is to subtract 10000 repeatedly, then subtract 1000 repeatedly, then 100, then 10, etc. But what's the best way?

Last updated on Oct-18-2019 Download

So far, the easiest algorithm I can think of is to subtract 10000 repeatedly, then subtract 1000 repeatedly, then 100, then 10, etc. But what's the best way?

by on 2010-04-04 (#59639)

I had a program for the 6809 that did that, but it didn't do 10000 and it was not 6502 so sorry man

I am curios to this, too, though XD

I am curios to this, too, though XD

by on 2010-04-04 (#59645)

Depends on your definition of "best". I've found your approach the simplest as well. Just set up a table of the 16-bit values and loop through.

Here's the version written for clarity and simplicity (that means little attempt at optimization, as that wasn't a stated goal):

**Code:**

Here's a variation that's a little more compact and faster, as it merges the compare and subtract; it's still not meant for speed, since there are far faster algorithms:

**Code:**

Both routines have been decently tested with edge-case values.

Here's the version written for clarity and simplicity (that means little attempt at optimization, as that wasn't a stated goal):

binary: .res 2 ; 16-bit unsigned input value

decimal: .res 5 ; output decimal digits, one per byte, natural order

; Converts 16-bit binary to 5-digit decimal.

bin_to_dec:

ldx #0

@digit:

ldy #0

; Just compare first time through loop

jmp @compare

@increment:

iny

; Subtract weight from binary

sec

lda binary

sbc lsb,x

sta binary

lda binary+1

sbc msb,x

sta binary+1

@compare:

; Compare binary to digit weight

sec

lda binary

sbc lsb,x

lda binary+1

sbc msb,x

; Increment digit if binary >= weight

bcs @increment

sty decimal,x

inx

cpx #5

bne @digit

rts

lsb: .byte <10000,<1000,<100,<10,<1

msb: .byte >10000,>1000,>100,>10,>1

decimal: .res 5 ; output decimal digits, one per byte, natural order

; Converts 16-bit binary to 5-digit decimal.

bin_to_dec:

ldx #0

@digit:

ldy #0

; Just compare first time through loop

jmp @compare

@increment:

iny

; Subtract weight from binary

sec

lda binary

sbc lsb,x

sta binary

lda binary+1

sbc msb,x

sta binary+1

@compare:

; Compare binary to digit weight

sec

lda binary

sbc lsb,x

lda binary+1

sbc msb,x

; Increment digit if binary >= weight

bcs @increment

sty decimal,x

inx

cpx #5

bne @digit

rts

lsb: .byte <10000,<1000,<100,<10,<1

msb: .byte >10000,>1000,>100,>10,>1

Here's a variation that's a little more compact and faster, as it merges the compare and subtract; it's still not meant for speed, since there are far faster algorithms:

bin_to_dec:

ldx #0

@digit:

lda #0

sta decimal,x

jmp @subtract

@increment:

inc decimal,x

; Commit new value

sta binary+1

sty binary

@subtract:

; Subtract digit weight from binary, but don't commit

sec

lda binary

sbc lsb,x

tay

lda binary+1

sbc msb,x

; Loop if subtraction didn't wrap binary around

bcs @increment

inx

cpx #5

bne @digit

rts

lsb: .byte <10000,<1000,<100,<10,<1

msb: .byte >10000,>1000,>100,>10,>1

ldx #0

@digit:

lda #0

sta decimal,x

jmp @subtract

@increment:

inc decimal,x

; Commit new value

sta binary+1

sty binary

@subtract:

; Subtract digit weight from binary, but don't commit

sec

lda binary

sbc lsb,x

tay

lda binary+1

sbc msb,x

; Loop if subtraction didn't wrap binary around

bcs @increment

inx

cpx #5

bne @digit

rts

lsb: .byte <10000,<1000,<100,<10,<1

msb: .byte >10000,>1000,>100,>10,>1

Both routines have been decently tested with edge-case values.

by on 2010-04-05 (#59657)

It's a bit faster to subtract off 40000, 20000, 10000, 8000, 4000, 2000, 1000, 800, 400, 200, 100, 80, 40, 20, 10 to form each bit. It ends up looking a lot like a division routine. On the wiki, see Programming guide > Programming Libraries > Binary to decimal

by on 2010-04-05 (#59696)

Ah, well, if it's Binary to Decimal you're looking for:

http://the_bott.webs.com/BinToDec.asm

This method I came up with takes about 263 cycles to convert a 16-bit binary number to decimal format, putting each decimal digit in a separate byte. I've got separate methods for 8 bits, 16 bits, and 24 bits. The 24 bit conversion only takes around 460 cycles or something like that.

Another good thing about this method is it takes the exact same amount of time every time, since there is no looping. So there's no "Well this could take 42 cycles or 10,000" type of thing.

Oh, and I was thinking maybe this method should also be posted on the wiki? It takes up a bit more space but I haven't seen a faster method (aside from pre-converting all possible values and putting them in a table, but I'm talking about a realistic/practical approach).

http://the_bott.webs.com/BinToDec.asm

This method I came up with takes about 263 cycles to convert a 16-bit binary number to decimal format, putting each decimal digit in a separate byte. I've got separate methods for 8 bits, 16 bits, and 24 bits. The 24 bit conversion only takes around 460 cycles or something like that.

Another good thing about this method is it takes the exact same amount of time every time, since there is no looping. So there's no "Well this could take 42 cycles or 10,000" type of thing.

Oh, and I was thinking maybe this method should also be posted on the wiki? It takes up a bit more space but I haven't seen a faster method (aside from pre-converting all possible values and putting them in a table, but I'm talking about a realistic/practical approach).

by on 2010-04-05 (#59697)

The method I use in Concentration Room takes about 84 cycles for an 8-bit number, and it doesn't use huge lookup tables.

by on 2010-04-05 (#59699)

Oh, well that's really good then. Mine takes 118, which I still think is good, but it's not as good as 84 obviously. And the fact that it takes more space makes your method preferable in that case. But actually, the 8-bit bin-to-dec routine doesn't use very large look-up tables. It uses the same tables that the other 16 and 24 bit routines use, but only a fraction of them. Once you get into the 16 and 24 bit tables though, those are what take up a lot of space.

Thanks for putting it up! It's just good to have multiple methods up, just so people can choose one to fit the need for speed or space.

Also, not to be nitpicky, but I notice the link says "HexToDecimal.8". That's the name of the 8-bit routine, and the names of the other routines are HexToDecimal.16, and HexToDecimal.24. So the link text is just a little misleading, it should say something like "Celius' HexToDecimal routines" or something. It's not that important though. Thanks again!

Thanks for putting it up! It's just good to have multiple methods up, just so people can choose one to fit the need for speed or space.

Also, not to be nitpicky, but I notice the link says "HexToDecimal.8". That's the name of the 8-bit routine, and the names of the other routines are HexToDecimal.16, and HexToDecimal.24. So the link text is just a little misleading, it should say something like "Celius' HexToDecimal routines" or something. It's not that important though. Thanks again!

by on 2010-04-05 (#59701)

Celius, it's interesting how yours are branchless in order to be constant-time.

If you want fastest, we beat that to death a few years ago, with one that at worst does 8-bit in 56 clocks, 16-bit in 208 clocks, and 24-bit in 430 clocks.

If you want fastest, we beat that to death a few years ago, with one that at worst does 8-bit in 56 clocks, 16-bit in 208 clocks, and 24-bit in 430 clocks.

by on 2010-04-06 (#59713)

Wow, those are some pretty impressive numbers! Well, okay, I officially surrender; mine is not the fastest!

But hey, my numbers are relatively close (okay, for the 8-bit not really, for 16-bit sort of, and for 24-bit yes). I like my method anyways, and I guess it could be improved by adding some branches for certain ranges of values, like if the hex value is less than $8000, I only need to process 3 of the hex digits and not 4. This could save a fair bit of time (though it would add cycles if all code was executed with no branches). Having a constant time isn't really necessary for BinToDec routines, usually because people perform them during game logic and not somewhere with time-sensitive code. But I understand how my method works, and I often have trouble following other methods. That's mainly why I'll continue using mine, simply because using code you don't understand is never a good idea.

But hey, my numbers are relatively close (okay, for the 8-bit not really, for 16-bit sort of, and for 24-bit yes). I like my method anyways, and I guess it could be improved by adding some branches for certain ranges of values, like if the hex value is less than $8000, I only need to process 3 of the hex digits and not 4. This could save a fair bit of time (though it would add cycles if all code was executed with no branches). Having a constant time isn't really necessary for BinToDec routines, usually because people perform them during game logic and not somewhere with time-sensitive code. But I understand how my method works, and I often have trouble following other methods. That's mainly why I'll continue using mine, simply because using code you don't understand is never a good idea.

by on 2010-04-06 (#59716)

Celius wrote:

That's mainly why I'll continue using mine, simply because using code you don't understand is never a good idea.

I disagree; as long as you understand how to by on 2010-04-06 (#59718)

+1 @ blargg

Nothing at all wrong with using a black box as long as you use it properly.

I think the problem here is that the code provided was more of an example and not really a usable block of code and/or it's being used improperly.

Nothing at all wrong with using a black box as long as you use it properly.

I think the problem here is that the code provided was more of an example and not really a usable block of code and/or it's being used improperly.

by on 2010-04-06 (#59720)

I'm fine with people using black boxes as long as they understand how to properly interface with them, but personally, I don't use them. At least not in assembly, where it's harder to modularize code.

by on 2010-04-06 (#59729)

tokumaru wrote:

I don't use [black boxes]. At least not in assembly, where it's harder to modularize code.

Sound code appears to have become fairly modularized. As I understand it, an NES sound engine presents four methods (start_sound_effect, start_song, update_sound, and stop_song), two of which are now defined by the NSF spec.

by on 2010-04-06 (#59730)

I guess when I think about it I use black boxes all the time in stuff like Visual Basic or languages that come with predefined classes and whatnot. In those instances, it's good to not have to re-invent the text box or multiplication routines. I guess it's okay, but there's something that bugs me about saying you don't ever need to understand how code works, you just need to understand how to use it. I'd think encouraging understanding of code makes people better programmers, and encouraging people to just drag and drop routines made by other people together without understanding how they work doesn't allow that to happen. I'm sure that's beside the point though. But with something like the NES, these predefined routines can't just pull local variables out of the mysterious void that is RAM; you have to specify what RAM the routines are going to use, and therefore, you should understand how the code works at least to a small degree.

by on 2010-04-06 (#59731)

To be honest, I use a few pieces of codes I don't understand, the first that comes to mind is the code computing a square root, that I found on 6502.org, I don't understand it at all but it works fine for me (I use it to compute the distance between an enemy and the player on the screen).

I also use a RNG code and sorting algorithm made by other people, I think I understand them at least partially.

The only binary -> BCD conversion method I understand is the substract 10^x method so the day I need it I will probably do that method even if it's slower. The day you need to convert dozen of numbers each frame you'll have to worry about the speed of the routine, but even in an RPG this isn't going to be the case.

If you want to be real fast tough, you can use the method they did in Rad Racer : One LUT for each numbers which ends up in a total ~30 cycles for a 8-bit number, at the cost of crazy ROM space.

I also use a RNG code and sorting algorithm made by other people, I think I understand them at least partially.

The only binary -> BCD conversion method I understand is the substract 10^x method so the day I need it I will probably do that method even if it's slower. The day you need to convert dozen of numbers each frame you'll have to worry about the speed of the routine, but even in an RPG this isn't going to be the case.

If you want to be real fast tough, you can use the method they did in Rad Racer : One LUT for each numbers which ends up in a total ~30 cycles for a 8-bit number, at the cost of crazy ROM space.

by on 2010-04-06 (#59732)

The simplest routines just need to specify how they accept and return values, and what registers they preserve. More complex ones need to specify any memory they use for temporary and persistent variables. That covers most routines. It's not hard at all to make modular libraries. When I realized this years ago, that assembly could be modularized just like C code, my assembly code became much cleaner and easy to work with. As with a high-level language, it helps to work out a small set of techniques, rather than doing obscure, unique things for each routine.

by on 2010-04-06 (#59735)

Bregalad wrote:

(I use [a square root function as a black box] to compute the distance between an enemy and the player on the screen).

PROTIP: A lot of the time, you can get away with comparing the square of the distance between the two to the square of the sum of their radii, no roots involved.

If we standardize local variables to be $0000-$000F, that might make modularization a bit easier.

by on 2010-04-06 (#59768)

Local volatile variables (ones whose values need not be preserved across routine calls)? Sure.

by on 2010-04-06 (#59769)

Hopefully not changed by IRQ code