32 divide
9 messages in this thread
Help! What's the best way to do a 32 bit signed divide on the 68000?
Using just DIVS is no good on overflow conditions. Any sample code
on how to get a "32 bit / 16 bit = 32 bit" would be VERY helpful!
– Thanks, GregM
Hmm… perhaps I am missing omething, but an overflow only hppes if the
source operand is larger than the destination operand. Since we are talking
integer operations here, the answer, in the case of an overflow, is 0, with
the remainder being contained in the destination.
-larry
The following code does NOT work:
move.l #1000000,d0 one million
move.l #10,d1 divided by 10
divs d1,d0 is a million!
rts
.. because the result of the division is > 2^16
Richard, I looked up in some code I wrote a while ago. To divide a 32 bit
number by another number giving a 32 bit result, I avoided the issue by
passing the values to a routine which could handle ANY size numbers
(subject to memory limitations).
The fact that I took this route makes me think that the problem is rather
difficult. Try looking up Knuth's book on Semi-numerical algorithms. He
gives an algorithm for multiple-precision division.
Do you really need to do this? Can you not avoid the problem?
One other thought – you can do the division on a bit-by-bit basis, though
this will be slow.
Regards,
Shraddhan – via Whap! from Hertfordshire in the UK
Richard,
After posting my rather unhelpful message, I had a longer think about the
problem of 32 bit / 16 bit signed division and have come up with the
following routine which seems to work. I haven't tested it thoroughly, and
if you want to use it, it's up to you to check it properly first.
I hope this is what you wanted.
test move.l #-10000000,d0
move.l #30,d1
bsr.s divide
rts
;; The following routine divides the signed 32-bit value in D0 by ;; the
signed 16-bit value in D1, returning the signed 32-bit ;; result in D0 and
the remainder in D1. ;; No other registers are affected
divide movem.l d2/d3/d4,-(a7)
moveq #0,d2 D2 holds the sign of the result
btst #31,d0
beq.s 2$
neg.l d0
moveq #1,d2 2$ btst #31,d1
beq.s 4$
neg.l d1
eor.b #1,d2 ;; Now do an unsigned divide 4$ move.l d0,d3
move.w #0,d3
swap d3
divu d1,d3 D3 = quotient / 2^16
move.w d3,d4
swap d4 high word of quotient
move.w d0,d3
divu d1,d3 divide D1 into (D0 – (D0/D1)*2^16)
move.w d3,d4
move.w #0,d3 get remainder…
swap d3
move.w d3,d1 … to D1
move.l d4,d0 ;; Adjust the sign
tst.b d2
beq.s 10$
neg.l d0 10$ movem.l (a7)+,d2/d3/d4
rts
Regards,
Shraddhan – via Whap! from Hertfordshire in the UK
Shraddhan,
Sorry for the length of time between your post and my reply, but
thanks! I haven't had time to test out your code, but it looks good.
Are there any good 68000 programming tricks books in print?
Again, thanks!
Greg Marquez
Richard,
I think you'll find my code to be OK, but I haven't tested it as
thoroughly as I would do if I were using it myself.
As for any good 680×0 books, I've given up looking. There's so much junk
out there that my legs can't stand the strain any more in bookshops 😉
Maybe I can express that better – the books I have come across haven't
contained the kind of information for which I would pay out the asking
price, and besides, I've got a serious problem with shelf space here.
Also, the snag is that the problems we try to solve are more specific than
would be suitable for a general book. If I understood your problem
correctly, you wanted to divide a 32 bit number by a 16 bit number and have
a 32 bit result. I think that this problem is rather specialised – an
author would be more inclined to show how do divide by a 32 bit number, not
a 16 bit number, and give you the remainder too. So you would have to
simplify the author's code if you wanted to maximise its speed.
I must say though that I have often wished I had a cookbook of algorithms
I could dip into and lift out code I could use directly.
Regards,
Shraddhan – via Whap! from Hertfordshire in the UK
The WB2 utility.library has some 32 bit multiply/divide routines:
SDivMod32(), SMult32(). These work on the 68000, but also detect faster
processors, and use DIVSL, etc. You could use these, or maybe get some
ideas from how they are coded?
Steve the G. [BEDFORDSHIRE, UK]
Steve, thanks for the tip! Unfortunately my Amiga is dead. I'm saving
up for an A1200, though. . . 😉
Greg M
Richard,
I just checked my last message and there are a few layout problems:
There are three lines which I labelled 2$, 4$ and 10$ and which have been
merged onto the preceding lines.
A lot of the comment lines starting with a double semicolon have also been
merged onto the preceding lines.
Regards,
Shraddhan – via Whap! from Hertfordshire in the UK