This thread is related to a previous thread on binary division here: http://forum.allaboutcircuits.com/threads/divide-a-binary-number.121934/
Rather than continuing off topic, I decided to start a new thread to compare a "standard" multiprecison method for division with one based on the Kenyan multiplication algorithm but developed independently.
For the standard method I chose Peter Hemsley's from Piclist (http://www.piclist.com/techref/microchip/math/div/32by16ph.htm). I have used it many times and simply adapted it to 24-bit X 16-bit for this experiment.
For the Kenyan method, I simply followed the algorithm developed by G. Reichborn-Kjennerud and presented here: http://www.piclist.com/techref/method/math/muldiv.htm The code is written for 24-bit X 24-bit. I will refer to it as the R-K algorithm -- not to be confused with any other person living or dead.
Both methods were simulated on MPLab 8.92 using MPLab SIM at 4 MHz. The pseudo-Kenyan method uses the instruction set from an enhanced mid-range PIC 16F1829, namely the subwfb instruction. My code is still pretty crude, and I do intend to post it once it is cleaned up. The common subwf(b) method destroys the number being subtracted from (minuend) and my current code uses a shadow register to reconstruct those registers when needed. I don't like doing that, if it can be avoided. It can be done other ways, but the added loop time for doing that may be self-defeating. For example, this destroys the minuend, which ends up with the result:
This preserves the minuend, but takes more time:
Cutting to the chase, here are my timing results:
The Hemsley method uses rotations and has a relatively fixed time. The alternative method depends on the number of subtractions needed. It can be quite short when a number is divided by itself or long when the divisor is 1. My code does not check (yet) for a zero divisor.
Although no question is presented here, I would like to hear from others who have efficient multi-precision methods or who have also tried the Reichborn-Kjennerud algorithm themselves.
Regards, John
Rather than continuing off topic, I decided to start a new thread to compare a "standard" multiprecison method for division with one based on the Kenyan multiplication algorithm but developed independently.
For the standard method I chose Peter Hemsley's from Piclist (http://www.piclist.com/techref/microchip/math/div/32by16ph.htm). I have used it many times and simply adapted it to 24-bit X 16-bit for this experiment.
For the Kenyan method, I simply followed the algorithm developed by G. Reichborn-Kjennerud and presented here: http://www.piclist.com/techref/method/math/muldiv.htm The code is written for 24-bit X 24-bit. I will refer to it as the R-K algorithm -- not to be confused with any other person living or dead.
Both methods were simulated on MPLab 8.92 using MPLab SIM at 4 MHz. The pseudo-Kenyan method uses the instruction set from an enhanced mid-range PIC 16F1829, namely the subwfb instruction. My code is still pretty crude, and I do intend to post it once it is cleaned up. The common subwf(b) method destroys the number being subtracted from (minuend) and my current code uses a shadow register to reconstruct those registers when needed. I don't like doing that, if it can be avoided. It can be done other ways, but the added loop time for doing that may be self-defeating. For example, this destroys the minuend, which ends up with the result:
Code:
movf T2L,w ;
subwf T1L,f ;
movf T2H,w ;
subwfb T1H,f ;
nop
Code:
movf T2L,w ;
subwf T1L,w
movwf T3L ;
movf T2H,w ;
subwfb T1H,w ;
movwf T3H
nop
The Hemsley method uses rotations and has a relatively fixed time. The alternative method depends on the number of subtractions needed. It can be quite short when a number is divided by itself or long when the divisor is 1. My code does not check (yet) for a zero divisor.
Although no question is presented here, I would like to hear from others who have efficient multi-precision methods or who have also tried the Reichborn-Kjennerud algorithm themselves.
Regards, John