6502: is BCD *fundamentally* the same performance as non-BCD?

Question

Furthering my reading of MS BASIC and Woz's FP code and comparing the two leads to another question specific to the 6502...

From what I can see looking over the 6502 instruction guides, it appears that the cycle times for a given instruction like ADC will vary depending on the addressing mode, but not on the decimal mode.

I know that to properly handle the V and N flags there's a few additional instructions that are needed if you want to address that issue. The 65C02 addresses these at the cost of a single cycle.

(tweaked) But beyond that, is the fundamental performance of BCD and non-BCD math the same? Do the algorithms for higher-level functionality, like multiplication, have to change in basic form?

Answer 1

But beyond that, is there any fundamental difference in performance?

On a fundamental base: No.

In code looping and adjusting needs to take into account that digits are shifted by 4 instead of 1 and carry ripples at 10 instead of 2.

Speed will be about the same.

Ofc, it helps to have a BCD mode to do so. But not as much as one may assume. When doing FP most time is spend in looping and shifting code, arithmetic instructions account only for a small fraction.

For over all speed it's way more important that the chosen number format can be handled efficient within the basic memory element. On byte orientated machines it helps if when 8 base 2 digits - or two base 10 (or base 16 like IBM /360s FP) - go into a byte. Base 4 would also work as well, but 8 or 32 would be less handy.

Answer 2

Let's write some actual code for fixed point arithmetic and see how it goes.

1) Addition and Subtraction is obviously fundamentally the same.

2) Multiplication. There are quite a few ways to do multiplication. A reasonably performant and still straightforward algorithm uses shifts and adds. Pseudo code to calculate z = x * y:

z := 0
while x != 0:
  x := x / 2
  if odd (old x) then:
    z := z + y
  y := y * 2

Unoptimized implementation for 2 bytes arguments and a 4 byte result with binary arithmetic, using crasm:

        cpu 6502

vx      = $10
vy      = $20   
vz      = $30

*       = $300

        code

        lda #$46
        sta vx+0
        lda #$59
        sta vx+1
        lda #$92
        sta vy+0
        lda #$63
        sta vy+1

        cld
        lda #$00        ; z := 0
        sta vz+0
        sta vz+1
        sta vz+2
        sta vz+3
        sta vy+2
        sta vy+3

.3      lda vx+0        ; while x != 0
        ora vx+1
        beq .1
        lsr vx+1        ; x := x / 2
        ror vx+0
        bcc .2          ; if odd (old x)
        clc
        lda vz+0        ; z := z + y
        adc vy+0
        sta vz+0
        lda vz+1
        adc vy+1
        sta vz+1
        lda vz+2
        adc vy+2
        sta vz+2
        lda vz+3
        adc vy+3
        sta vz+3
.2      asl vy+0        ; y := y * 2
        rol vy+1
        rol vy+2
        rol vy+3
        jmp .3
.1      brk

        code

This calculates

$5946 * $6392 = 22854 * 25490 = 582548460 = $22b8fbec

and using sim65 one can verify that it works.

For BCD arithmetic, we have to re-write division and multiplication by two. The latter is easy, just add the number to itself:

.2      clc             ; y := y * 2
        lda vy+0
        adc vy+0
        sta vy+0
        lda vy+1
        adc vy+1
        sta vy+1
        lda vy+2
        adc vy+2
        sta vy+2
        lda vy+3
        adc vy+3
        sta vy+3

The former is a bit difficult, I ended up doing the decimal adjust manually. Other variants would have been to replace x / 2 with x / 10 * 5, or to keep the shifts for x without adjustments, and use an alternative for every 4th bit in y * 2 (which would require loop unrolling).

        lsr vx+1        ; x := x / 2
        ror vx+0
        php
        sec
        lda vx+1
        bit const08
        beq .4
        sbc #$03
.4      sta vx+1
        lda vx+0
        bpl .5
        sbc #$30
.5      bit const08
        beq .6
        sbc #$03
.6      sta vx+0        
        plp

Again using sim65, one can verify that

5946 * 6392 = 38006832

These are the only parts that have to be changed, so structurally it's exactly the same. The observation here is that having an automatic decimal adjustment for division by two would have really helped (possibly there's a better way to do that.)

Of course I picked a variant where the similarities are very pronounced, but Chromatix claim that you have to do it a particular way as he describes it is wrong, and therefore the conclusions he draws are also wrong.

It is true, however, that the BCD variant will always be more complex, but not asymptotically so.

3a) Division with restore. Using the above method for BCD division by two, again the binary and BCD variants of the straightforward algorithm should be structurally the same. I didn't write code for that.

3b) Division without restore. I am not sure if this will work in BCD as well, but it might.

So, BCD algorithms do indeed have fundamentally (asymptotically) the same performance.

Adding exponents for BCD floating point, and doing the necessary shifts and normalization are not difficult, though note that the main application for BCD is fixed point (monetary values), so BCD floating point, BCD transcendental functions etc. are not as useful: In natural science, you don't really care if your rounding errors stem from a binary or a decimal representation.

Answer 3

Yes, there are differences in the algorithms used for BCD compared with binary arithmetic. The code for BCD is more complex, so larger and probably slower, if implemented with roughly equivalent skill and tradeoff between size and speed. That's even assuming there is not also a basic difference in execution speed, which there also is on the 65C02 (and on most non-65xx family CPUs, which tend to use a separate "BCD adjust" post-processing instruction rather than a mode flag).

The most basic difference is that with binary arithmetic, you only need to decide whether to perform a sub-operation or not, and then move on to the next binary place either way. With BCD, you need to perform the sub-operation between zero and nine times (inclusive), and then move on to the next digit which occupies the upper half of the byte, so a reasonable strategy is to repeat the inner loop specialised for that high digit instead of just looping over the bits.

Hence the average number of sub-operations in binary is 0.5 per bit, or 4 per byte - but in BCD it is 4.5 per digit, or 9 per byte. Assuming each sub-operation (addition for multiplication, compare-subtract for division and square-root) has the same cost, BCD will therefore be less than half the speed.

It is possible to reduce the number and complexity of these operations somewhat, for both binary and BCD modes, but this requires additional memory which is often not available in 6502-based machines. A modern design can of course make use of a large RAM or ROM set up as a lookup table, possibly through a banking arrangement.

Answer 4

Yes, there is a performance difference if you need to compute with numbers much more than a few digits or bits in size.

For instance, you can add 2 numbers in the range of 1 to a billion using 4 adds (3 with carry) in binary, but you will need 5 adds (4 with carry) using BCD, for the same range of integer data inputs and results.