atferrari
Full Member level 4
- Joined
- Jun 29, 2004
- Messages
- 237
- Helped
- 7
- Reputation
- 14
- Reaction score
- 3
- Trophy points
- 1,298
- Location
- Buenos Aires - Argentina
- Activity points
- 1,996
Revisiting the binary division algorithm I found somewhere in the PIClist, an unusual one described by a Swedish gentleman, who calls it, humorously, "Kenyan, Himalayan or...".
For fun, I implemented a 32/16-bits unsigned division with loops not-unrolled.
The PDF attached, describes the algorithm followed by two examples and my code.
Comments:
a) 18F's conditional branch instructions do simplify things a lot, vis a vis the previous 16F family. I spent definitely short time in writing the code, once the flow diagrama was ascertained.
b) While the algorithm requires "getting a value equal to, or the closest below the dividend", the code goes, in fact, to the next value immediately above the dividend. Why? Because that way, we know for sure it is time to start with the succesive substractions.
c) This code, as is, takes some 700 cycles for the worst case. It is obviously not deterministic since the times the divisor is doubled, depends directly of the dividend and divisor values. I find no reason to use it other than for fun.
d) Sure there is a way to improve it.
I enjoyed this.
For fun, I implemented a 32/16-bits unsigned division with loops not-unrolled.
The PDF attached, describes the algorithm followed by two examples and my code.
Comments:
a) 18F's conditional branch instructions do simplify things a lot, vis a vis the previous 16F family. I spent definitely short time in writing the code, once the flow diagrama was ascertained.
b) While the algorithm requires "getting a value equal to, or the closest below the dividend", the code goes, in fact, to the next value immediately above the dividend. Why? Because that way, we know for sure it is time to start with the succesive substractions.
c) This code, as is, takes some 700 cycles for the worst case. It is obviously not deterministic since the times the divisor is doubled, depends directly of the dividend and divisor values. I find no reason to use it other than for fun.
d) Sure there is a way to improve it.
I enjoyed this.