6502: is BCD *fundamentally* the same performance as non-BCD?4sv#39eco
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?
-
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 11 hours ago
-
So in theory the performance and overall organization is the same? I ask because I notice the sense of my subject is opposite the body... – Maury Markowitz 11 hours ago
-
1FWIW, 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 11 hours ago
-
1@MauryMarkowitz Maybe it would help to make title and in-text-question the same. – Raffzahn 10 hours ago
-
1@ErikEidt Just set the decimal flag (SED) and all arithmetic (ADC, SBC) will be base 10. See this thruout tutorial. – Raffzahn 9 hours ago
3 Answers
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.
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.
-
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 3 hours ago
-
1You 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 3 hours ago
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.
-
1Not 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 5 hours ago