Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!uunet!mcsun!ukc!tcdcs!maths.tcd.ie!chughes
From: chughes@maths.tcd.ie (Conrad Hughes)
Newsgroups: comp.sys.acorn
Subject: Re: integer division
Message-ID: <1991Jun11.141031.6669@maths.tcd.ie>
Date: 11 Jun 91 14:10:31 GMT
References: <1991Jun10.112536.15897@rusmv1.rus.uni-stuttgart.de>
Organization: Dept. of Maths, Trinity College, Dublin, Ireland.
Lines: 43

In <1991Jun10.112536.15897@rusmv1.rus.uni-stuttgart.de>
zrzm0370@rusmv1.rus.uni-stuttgart.de (Joerg Scheurich) writes
about division..

>382     Cycles in 100 Bytes, with usage of 4 32-Bit-registers
>and 4 Byte memory.

>With unrolling the loop,
>the faster  and longer 32-Bit/32-Bit-division-routine requires 
>182     Cycles in 692 Bytes, with usage of 4 32-Bit-registers.

This divides a 64bit number by a 32bit one, with 32bit result, in 97
instructions/388 bytes/97 clock cycles..

Entry: A=MSW of 64bit no., B=LSW of 64bit no., C=32bit no.
	C _must_ be negative (if it's positive, RSB C,C,#0),
	A _must_ be positive (if not, RSBS B,B,#0:RSC A,A,#0)
ADDS B,B,B
ADCS A,C,A,LSL#1:SUBCC A,A,C:ADCS B,B,B [repeat these three 32 times]
Exit: A=Remainder of division, B=result, C unchanged.
	..if you don't need the remainder, get rid of the last
	SUBCC A,A,C.
	The result will be unsigned, and flags will (obviously)
	reflect the last addition.
Adjust as you will to get 32/32 division (Initialise A to 0, or AB
= numerator shifted some way) or any other variety you like..
Rolling up the loop it could get slightly complicated since every
instruction requires flag information from the previous one ;-)
Something like SUB count,count,#1:TEQ count,#0:BNE loop with count
initialised to #32 might do the trick, but it'll slow it down to at
least 288 cycles (so what if it only uses 32 bytes?? ;-}), which is
pretty unacceptable unless you're on an ARM3..

This is off the top of my head and I'm nowhere near the Arc, so if
it doesn't work (it should - I've typed it in enough times now..)
flame me..

Conrad
-- 
Will you sell me one of those if I shave my head
Get me out of town is what Fireball said
Never trust a man in a blue trench coat
Never drive a car when you're dead                      Tom Waits