5

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?

Improve this question
9
  • 1
    Simply no. They just need to take into account that digits are shifted by 4 instead of 2 and carry ripples at 10 instead of 2. – Raffzahn Aug 16 '19 at 14:26
  • 1
    Yes. Affter all, the basic algorithm is the same no matter to what base your system is organizes. Of course on byte orientated machiens it helps if when 8 base 2 digits go into one memory element - or two base 10 or base 16 (like IBM /360s FP). Base 3 or 5 or 8 would be less handy. – Raffzahn Aug 16 '19 at 14:33
  • 1
    FWIW, the 65816 has the status flag fix for ADC/SBC without needing to spend an additional cycle, so I don't think the cost of the fix is fundamental to the 65xx architecture either. – fadden Aug 16 '19 at 14:38
  • 1
    @MauryMarkowitz Maybe it would help to make title and in-text-question the same. – Raffzahn Aug 16 '19 at 15:39
  • 2
    @ErikEidt Just set the decimal flag (SED) and all arithmetic (ADC, SBC) will be base 10. See this thruout tutorial. – Raffzahn Aug 16 '19 at 15:59
7

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.

Improve this answer
4
  • 1
    adjusting can be faster on BCD. It requires shifting only when adjusting an odd number of digits. Even shifts are simple byte copies. In binary it will also vary between 0 and 7 shifts (or if smart from 0 to 4 shifts). – Patrick Schlüter May 29 '20 at 6:42
  • 1
    When doing FP most time is spend in looping and shifting code, arithmetic instructions account only for a small fraction. Yes, that's why paradoxically additions were sometimes more expensive than additions in floating point arithmetic (at least before the advent of barrel shifters). – Patrick Schlüter May 29 '20 at 6:45
  • @PatrickSchlüter Ws that supposed to be "additions more expensive than multiplications"? – Vatine May 29 '20 at 7:30
  • 1
    Yes, of course. – Patrick Schlüter May 29 '20 at 17:27
4

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.

Improve this answer
7
  • Sound fair. Except, one doesn't care for rounding errors at all, but guaranteed precision - and here does BCD have the advantage that precision doesn't vary but is always continous. – Raffzahn Aug 18 '19 at 16:14
  • @Raffzahn: Sorry, that makes no sense. The opposite of "vary" is "constant", so do you mean "constant" instead of "continuous"? And in binary the precision is also constant - with respect to the representation. The problems only start when you try to express binary in decimal, but you have the same kinds of problems when you try to express decimal in binary. If you have no reason to prefer one representation over the other (as with currency), it makes no difference. – dirkt Aug 18 '19 at 18:38
  • Erm, no, it's continuous, as binary precision jumps. And yes, it's related to using a different base. After all, all real world all in and output is decimal. BTW, language is not binary, but more so, vary vs continuous is about relation :)) It's never a good idea to interpret more than there is. – Raffzahn Aug 18 '19 at 18:50
  • "you don't really care if your rounding errors stem from a binary or a decimal representation" - which is precisely what led to this question. Atari BASIC used BCD and was PAINFULLY slow. Their reasoning was to avoid rounding errors. Yes, those are annoying, but not as annoying as slow performance. So the question ultimately came down to was this decision dooming the system to be slow, and thus a horrible distributed cost, or was it simply a bad implementation and thus a potentially useful technique in a general sense? – Maury Markowitz Aug 19 '19 at 11:39
  • @MauryMarkowitz: "to avoid rounding errors" simplifies things too much. You always have rounding errors in floating point: There are uncountably many infinite real numbers, but only finitely many representations of floating point numbers. No matter which base you choose. The reason to use BCD is if your application uses fixed point arithmetic in a certain base, like monetary values do. Then, and only then, you don't want the rounding errors that stem from conversion between bases, and you don't have rounding errors if you properly specify the decimals. – dirkt Aug 19 '19 at 13:20
1

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.

Improve this answer
4
  • 1
    You're aware that this is only true for division and further depends on the algorithm used? And in contrast the outer loop (consisting of way more operations than the sub itselb) for binary is always 8, while for decimal it just takes two iterations. – Raffzahn Aug 16 '19 at 22:15
  • 1
    You can reduce the number of additions per digit for multiplication, if you first pre-calculate eight multiples of one operand and store them somewhere. That's a space cost relative to binary, which is likely to be significant on a 6502 based machine. Also, I accounted for the different number of digits per byte in my calculation of running speed. – Chromatix Aug 16 '19 at 22:22
  • "Also, I accounted for the different number of digits per byte in my calculation of running speed." Not really, as it's only about needed subs, not the generic looping, which does eat up way more instructions (and clock ticks). Focusing on a single case and there focusing on one rather minor part, doesn't paint an over all performance picture. But further claiming this singular slowest case as average by " Assuming each sub-operation [...] has the same cost" takes the biscuit. – Raffzahn Aug 17 '19 at 8:24
  • Most useful chrome! – Maury Markowitz Aug 17 '19 at 12:45
0

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.

Improve this answer
1
  • 1
    Not really. As this is about FP. The most important criteria for FP is not the largest possible number, but guaranteed precision. Decimal precision. While binary FP may offer higher precision due better memory usage, it doesn't pay below double (56 bit mantissa). Here, finally, binary FP offers 15 valid digits instead of the 14 digits BCD based FP has. – Raffzahn Aug 16 '19 at 20:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.