In comments, WimC pointed to working 6502 code that divides an 8-bit unsigned integer by 3, with quotient rounded towards zero as required by C and C++. This code computes x / 3 as (4/3 * x) / 4, where the factor 4/3 is approximated as 1 + 1/4 + 1/16 + 1/64, which is an underestimate:
res = (arg + (arg / 4) + (arg / 16) + (arg / 64)) / 4
Clearly this computation requires 9 bits throughout, which is awkward with 8-bit processors. But we can re-arrange the computation as
res = (((((arg) / 4) + arg) / 4 + arg) / 4 + arg) / 4
and further expand this into
res = ((((((((arg) / 2) / 2 + arg) / 2) / 2 + arg) / 2) / 2 + arg) / 2) / 2
The advantage of this is that many 8-bit processors allowed for the efficient computation of (a + b) / 2, in that the addition would result in a 9-bit result, the lower 8 bit of which were stored in the accumulator while the most significant bit was stored in the carry flag. A subsequent rotate-right-through-carry instruction could then perform a 9-bit right rotation, effecting the division of the 9-bit sum by two. In the case of the 6502, the instruction for this is ROR
.
So far we have glossed over the fact that our chosen approximation to 4/3 is an underestimate and that integer division truncates. This suggests that our computed quotient will frequently be too low, and a quick test verifies this. We can try to counteract this by adding a correction constant. I do not know of any particular algorithm to derive such corrections, I usually search for these by trial and error. In this case, we get the correct quotient for all 256 possible dividends by computing:
res = ((((((((arg + 85) / 2) / 2 + arg) / 2) / 2 + arg) / 2) / 2 + arg) / 2) / 2
One immediately notices that the linked 6502 code uses a different correction constant. This is due to two factors: (1) The addition instruction used is not a plain addition but an ADC
(add with carry) which incorporates the carry set by a preceding LSR
(logical shift right). This tends to make the result of the addition larger than in the pseudocode above. (2) To minimize cycle count, the code adds the correction after the first division by two. Instead of starting off with CLC
/ ADC #43
/ ROR
/ LSR
, it only needs three instructions: LSR
/ ADC #21
/ LSR
, with the value of the carry flag well defined after the initial LSR
.
Best I recall the Z80 instruction set, the algorithm presented for the 6502 could be translated one to one for the Z80: LSR
becomes SRL
, ROR
turns into RRA
, and ADC
remains ADC
.
Below are tested 8086 implementations of the variants mentioned above. On an 8086 one would want to use AAM 3
to divide a byte-size operand in AL
by 3, so this serves merely as a reference that may be more familiar to a modern audience.
__asm mov al, byte ptr [arg];
__asm mov cl, al;
__asm shr al, 1;
__asm adc al, 21;
__asm shr al, 1;
__asm adc al, cl;
__asm rcr al, 1;
__asm shr al, 1;
__asm adc al, cl;
__asm rcr al, 1;
__asm shr al, 1;
__asm adc al, cl;
__asm rcr al, 1;
__asm shr al, 1;
__asm mov byte ptr[res], al;
__asm mov al, byte ptr [arg];
__asm mov cl, al;
__asm clc;
__asm adc al, 43;
__asm rcr al, 1;
__asm shr al, 1;
__asm adc al, cl;
__asm rcr al, 1;
__asm shr al, 1;
__asm adc al, cl;
__asm rcr al, 1;
__asm shr al, 1;
__asm adc al, cl;
__asm rcr al, 1;
__asm shr al, 1;
__asm mov byte ptr[res], al;
__asm mov al, byte ptr [arg];
__asm mov cl, al;
__asm add al, 85;
__asm rcr al, 1;
__asm shr al, 1;
__asm add al, cl;
__asm rcr al, 1;
__asm shr al, 1;
__asm add al, cl;
__asm rcr al, 1;
__asm shr al, 1;
__asm add al, cl;
__asm rcr al, 1;
__asm shr al, 1;
__asm mov byte ptr[res], al;