[chbot] Very OT - Fast division on hardware without a hardware divider....

[Charles Manning]

On Wednesday 26 October 2011 16:08:22 hamster wrote:
> I found something that might be of interest to members of this group who
> use low end micro-controllers or are fiddling with FPGAs)
>
> The pdf at http://www.hackersdelight.org/divcMore.pdf contains many ways
> to perform speedy division using bitshifts...
>
> unsigned divu7(unsigned n) {
>    unsigned q, r;
>    q = (n >> 1) + (n >> 4);
>    q = q + (q >> 6);
>    q = q + (q>>12) + (q>>24);
>    q = q >> 2;
>    r = n - q*7;
>    return q + (r > 6);
> }
>
> As an aside, if anybody can make a better way to divide integers than "SRT
> Division" you could get very rich very quick - I didn't realise it takes
> 30+ clock cycles for a 64 bit divide...
>
> Mike

This looks slightly reminiscent of how integer division is done on ARMs with 
no divide instruction (eg ARM7s).

The division is achieved by doing some shifting + multiplication. I have never 
tried to understand how it works... it just does!

-- Charles