• C

Assembly Language Question - Dividing 64bit long by 32bit long

I know this is not the Assembler area, but there doesn't appear to be one.  I am working with a Motorola 68000 processor, and am looking for an algorithm for dividing a 64bit long (which would be held in 2 32 bit registers), by a 32 bit long.  Or, if I get no answer for that, I would accept an answer for a 32 bit long divided by a 32 bit long.  The assembler divu comand will divide a 32 bit long by a 16 bit long, and produce a 32 bit result where the high 16 bit word is the remainder, and the low 16 bit word is the quotient.
AlexVAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

imladrisCommented:
The straightforward (brute force) solution involves remembering that division is repeated subtraction (just like mulitplication is repeated addition). If the register containing the high order bits is reg1 and the low order ones are in reg0, the divisor is in div and the result goes in r the pseudo code would be:

set r to 0
while reg1!=0 or reg0>div
   if reg0 > div
      subtract div from reg0
      add 1 to r
   else
      subtract div from reg0
      subtract 1 from reg1
      add 1 to r

answer is in r, remainder in reg0
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
imladrisCommented:
One additional guard needed:

set r to 0
while reg1!=0 or reg0>div
   if reg0 > div
      subtract div from reg0
      add 1 to r
   else if reg1>0
      subtract div from reg0
      subtract 1 from reg1
      add 1 to r

answer is in r, remainder in reg0


0
imladrisCommented:
Note that in the general case you cannot guarantee that your result will fit into 32 bits. For instance, if you divide a 60 bit quantity by two, your result will be a 59 bit quantity. This could be managed with the repeated subtraction algorithm by setting aside two registers for the result and noting and acting on overflows on the increment by incrementing the high order register as well.

You can get better performance from a  bitwise long division. In pseudo code that would be:

dividend - n
divisor  - s
quotient - q
intermediate - i

i=0
q=0
while bits left to process
{  shift i left 1
   or top bit of n into i at bit 0
   shift n left 1
      (i.e. we're shifting n into i one bit at a time)
   shift q left 1
   if (i > s)
   {   i=i-s
       q=q+1
   }
}

at the end i will contain the remainder.
If n is 64 bits, you would have to manage a 64 bit q as well.
0
AlexVAuthor Commented:
Thanks, I will have a go at coding this now.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C

From novice to tech pro — start learning today.