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.