[A83] Re: Divide by 12


[Prev][Next][Index][Thread]

[A83] Re: Divide by 12



> > Here is some code for dividing an unsigned 16-bit integer
> > by 12. The simplest algorithm to compute n / 12 that I am
> > aware of is:
> > 
> >   q = (n >> 1) + (n >> 3)
> >   q = q + (q >> 4)
> >   q = q + (q >> 8)
> >   q = q >> 3
> >   r = n - q * 12
> >   q = q + ((r + 4) >> 4)
> 
> The computation of ((r + 4) >> 4) computes a correction factor
> that is either 0 or 1, based on the remainder one gets after
> subtracting the product of preliminary quotient and divisor
> >from the dividend. So one might want to replace this last step 
> with
> 
>    q = q + (r >= 12)
> 
> This leads to the following variant of the unsigned divide-by-12
> code. Note that with a few more instructions we could return the
> remainder as well. In the computation above "r" is a preliminary
> remainder and may be too big by 12. When correcting the quotient
> we could also fixup the remainder and return it in DE.
> 
> -- Norbert
> 
> 

I've found the following program. (BTW, this divides by
three, shifting A twice to the right beforehand fixes that.)

  { A >= 0 }
  q, r := 0, A + 1
; do r >= 4 --> x, y := r mod 4, r div 4
              ; q, r := q + y, x + y
  od
; r := r - 1
  { q = A div 3 /\ r = A mod 3 }


(BTW, the /\ should be a logical AND)

Most of you probably don't know GCL, but in the above
case it should be pretty intuitive. The multi-assigns can
be split (in this case at least) into q := 0 \ r := A + 1,
for instance. The loop is just you're normal Basic While
loop. The semicolons are the same as in Pascal.

My attempt to code this in assembly didn't work out, so
if anyone wants to use this, you'll have to write your
own code, sorry.

Rob van Wijk

-- 
+++ GMX - Mail, Messaging & more  http://www.gmx.net +++
Bitte lächeln! Fotogalerie online mit GMX ohne eigene Homepage!




Follow-Ups: References: