Binary division Kenyan algorithm 18F family - Electronic Circuits Projects Diagrams Free

atferrari · 1st May 2007, 10:07 PM

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.

gramo · 2nd May 2007, 01:26 PM

You could always just use Swordfish, no need to re-invent the wheel

Code:

Device = 18F452
Clock = 20

Include "convert.bas"
Include "usart.bas"

Dim 
    Var1 As LongInt,
    Var2 As Float,
    Var3 As Word,
    Var4 As Byte,
    Var5 As LongInt
    
    SetBaudrate(br19200)

    Var1 = 1000000
    Var2 = 15000.555
    Var3 = 33214
    Var4 = 155


    Var5 = (Var1 + (Var2 * Var3)) - Var4
    USART.Write(DecToStr(Var5))

Its math library goes a lot further too;

Quote:

function abs (pValue as type) as byte
function trunk (pValue as float) as float
function round (pValue as float) as float
function ceil (pValue as float) as float
function floor (pValue as float) as float
function fmod (x,y as float) as float
function modf (pValue as float, byref pIntegral as float) as float
function sqrt (pValue as float) as float
function cos (pValue as float) as float
function sin (pValue as float) as float
function tan (pValue as float) as float
function acos (pValue as float) as float
function asin (pValue as float) as float
function atan (pValue as float) as float
function exp (pValue as float) as float
function log (pValue as float) as float
function log10 (pValue as float) as float
function Pow ([pBase as type,] pExp as byte) as longword
function atan2 (y,x as float) as float
function cosh (x as float) as float
function sinh (x as float) as float
function tanh (x as float) as float
function frexp (x as float, byref exp as shortint) as float
function ldexp (value as float, exp as shortint) as float

But if its the challange your chasing then by all means keep going with it

Mike, K8LH · 3rd May 2007, 01:15 PM

I suspect most people are aware of the built-in math functions available in most high level languages.

While it's nice to make people aware of alternatives, your authoritative suggestions that BASIC is "the best way" or "the only way" are becoming obsessive and offensive (to me).

It seems you're suggesting that writing assemby code is a waste of time because it's so much easier to do it in BASIC. Someone might just as easily suggest that BASIC programmers are lazy and simply don't want to put the time and effort into becoming good assembly language programmers. Neither suggestion is correct or fair but I'm sure you see how easily these suggestions might be offensive to those who prefer one language over another. Every programming language has its advantages and disadvantages.

I apologize if my comments seem terse. Perhaps you could tone down your BASIC Evangelist persona and try not to discourage programmers using another language?

Kind regards, Mike

gramo · 3rd May 2007, 01:19 PM

Quote:

Originally Posted by Mike, K8LH

I suspect most people are aware of the built-in math functions available in most high level languages.

While it's nice to make people aware of alternatives, your authoritative suggestions that BASIC is "the best way" or "the only way" are becoming obsessive and offensive (to me).

It seems you're suggesting that writing assemby code is a waste of time because it's so much easier to do it in BASIC. Someone might just as easily suggest that BASIC programmers are lazy and simply don't want to put the time and effort into becoming good assembly language programmers. Neither suggestion is correct or fair but I'm sure you see how easily these suggestions might be offensive to those who prefer one language over another. Every programming language has its advantages and disadvantages.

I apologize if my comments seem terse. Perhaps you could tone down your BASIC Evangelist persona and try not to discourage programmers using another language?

Kind regards, Mike

Quote:

Originally Posted by gramo

But if its the challange your chasing then by all means keep going with it

Just offerring an alternative, I have no idea who atferrari is, never met him before, and perhaps the post could help him or others /shrug

gramo · 3rd May 2007, 01:27 PM

Quote:

Originally Posted by Mike, K8LH

While it's nice to make people aware of alternatives, your authoritative suggestions that BASIC is "the best way" or "the only way" are becoming obsessive and offensive (to me)

I have never made such suggestions. I have been down the assembler path (~1.5 years of it), and have not looked back since using Proton and Swordfish.

I am more than happy to offer higher language alternatives and wiring diagrams, to expose people to the real power behind structured modular programming, it’s the one thing I wish I was introduced too earlier

atferrari · 3rd May 2007, 03:13 PM

Hola,

You seem decided to insist. You are showing something involving a UART!, to reply my comment on how I simply implemented an unusual algorithm in Assembly for the 18F. I can not really understand that!

In our country we call it "peeing out of the can".

BTW, my case is the oposite: I transisted the BASIC path before restarting with Assembly for the PIC.

gramo · 3rd May 2007, 08:26 PM

Quote:

Originally Posted by atferrari

Hola,

You seem decided to insist. You are showing something involving a UART!, to reply my comment on how I simply implemented an unusual algorithm in Assembly for the 18F. I can not really understand that!

Just giving an example of math algorithm with a different language, one that has full support for 16/32 bit math and operations. The UART was just a simple expression of how to convert any type of variable to a string as well.

“peeing in the can”

lol, well call it what you want, I probably helped someone out there who is delving into 32bit math operations with micro controllers

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Latest
Algorithm to convert 64 bit Binary to BCD	ljcox	Micro Controllers	6	21st November 2004 03:33 AM
division algorithm	finst	Micro Controllers	3	19th December 2003 11:39 PM

3rd May 2007, 01:15 PM	(permalink)
Mike, K8LH	I suspect most people are aware of the built-in math functions available in most high level languages. While it's nice to make people aware of alternatives, your authoritative suggestions that BASIC is "the best way" or "the only way" are becoming obsessive and offensive (to me). It seems you're suggesting that writing assemby code is a waste of time because it's so much easier to do it in BASIC. Someone might just as easily suggest that BASIC programmers are lazy and simply don't want to put the time and effort into becoming good assembly language programmers. Neither suggestion is correct or fair but I'm sure you see how easily these suggestions might be offensive to those who prefer one language over another. Every programming language has its advantages and disadvantages. I apologize if my comments seem terse. Perhaps you could tone down your BASIC Evangelist persona and try not to discourage programmers using another language? Kind regards, Mike

3rd May 2007, 03:13 PM	(permalink)
atferrari	Told you already, Gramo Hola, You seem decided to insist. You are showing something involving a UART!, to reply my comment on how I simply implemented an unusual algorithm in Assembly for the 18F. I can not really understand that! In our country we call it "peeing out of the can". BTW, my case is the oposite: I transisted the BASIC path before restarting with Assembly for the PIC. __________________ Agustín Tomás In theory, there is no difference between theory and practice. In practice, however, there is.