Z80 Divide by 10

[dwight elvey]

> From: spc at conman.org
>
> It was thus said that the Great dwight elvey once stated:
>>
>>
>>
>>
>>> Date: Sat, 26 Jan 2008 17:21:56 -0500
>>> From: spc at conman.org
>>> To: cctalk at classiccmp.org
>>> Subject: Re: Z80 Divide by 10
>>>
>>> It was thus said that the Great dwight elvey once stated:
>>>>
>>>> 230 clock cycles and no conditionals
>>>> Dwight
>>>
>>> I came across this bit of code from http://www.hackersdelight.org/ to
>>> divide by 10:
>>>
>>> unsigned int div10(unsigned int n)
>>> {
>>> unsigned int q;
>>> unsigned int r;
>>>
>>> q = (n>> 1) + (n>> 2);
>>> q = q + (q>> 4);
>>> q = q + (q>> 8);
>>> q = q + (q>> 16);
>>> q = q>> 3;
>>> r = n - ((q << 3) + (q << 1));
>>> return (q + ((r + 6)>> 4);
>>> }
>>>
>>> On the Z80, the (q>> 8) is trivial to handle, and you can probably skip
>>> the (q>> 16) statement all-to-gether (since you're only handling 16 bits
>>> anyway, this reduces to 0 so the statement there can be skipped). My Z80
>>> skills are pretty weak (and I don't have any references at hand right now)
>>> but this looks pretty straight forward to translate.
>>>
>> Hi
>> I coded this up in Forth and it does good at the divide.
>> The values q and r are not much good, meaning one still
>> has to calculate the remainder, similar to the last part of my
>> code.
>> The operation>> is really tough on a Z80 for 16 bit operations.
>> One needs to do thing through the a register and use rra instructions
>> or use the rr r instruction with a clearing of the carry before each
>> single bit shift. Not having a parameterized shift like the 386 has
>> makes it difficult.
>> I doubt one could beat the 230 cycles I had since each shift cost
>> 12 cycles. This is 34 to 38 shifts depending on optimization or 408
>> cycles minimum without the 7 16 bit adds. This is already more
>> than the 230 cycles.
>
> Where do you get 34 shifts from? I can see that being reduced down to
> about 12 shifts:

Hi
 I hadn't done any byte swapping optimization and counted each
register shift to be a shift, so each 16 bit shift cost 2 register shifts.
 Right shift is expensive on the Z80. It could be a little better if
we had a shift that didn't include carry like the left shift.
 I think my routine may be extended a few bytes by changing the
tweak value. It has greater effect for small values but could get one
or two numbers increased if optimized.
 Such tweaks are there to make up for the way we truncate instead
of rounding. It means the value is always too small after a large number
of operation.
 The larger numbers are effected more by the number of times we
do the shifts. Since the algorithm was designed for the maximum
range, we might do better by removing one of the steps and
changing the tweak value a little. This may improve you code
some. Mine is already reduces to the minimum because the
tweak value only effect the low end the most.
 Where and when in the calculation one does the tweaks my
improve things as well. The rounding effect my be greatest
at one step over some other step.
 I think us bit twittlers are enjoying the exercise. It is surely
bringing back all the math I though I'd lost.
Dwight

_________________________________________________________________
Need to know the score, the latest news, or you need your Hotmail®-get your "fix".
http://www.msnmobilefix.com/Default.aspx