Binary division Kenyan algorithm 18F family

Discussion in 'Embedded Systems and Microcontrollers' started by atferrari, May 1, 2007.

  1. atferrari

    Thread Starter AAC Fanatic!

    Jan 6, 2004
    2,653
    768
    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; my code, writen for the 18F family, is in the TXT archive. (Just replace "TXT" with "ASM" to use it in MPLAB.

    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.
     
Loading...