* implementing software unsigned divide @ 2001-05-07 21:42 Stephen Leake 2001-05-08 6:04 ` Jacob Sparre Andersen ` (3 more replies) 0 siblings, 4 replies; 9+ messages in thread From: Stephen Leake @ 2001-05-07 21:42 UTC (permalink / raw) I'm porting GNAT to a 16 bit microprocessor that does not provide a hardware instruction for unsigned divide (it has multiply and signed divide, both 16 and 32 bit). Can anyone provide a reference to a book that discusses how to do this, and/or an algorithm that does it? I've looked in Knuth, and did an initial web search, and haven't found anything. -- -- Stephe ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: implementing software unsigned divide 2001-05-07 21:42 implementing software unsigned divide Stephen Leake @ 2001-05-08 6:04 ` Jacob Sparre Andersen 2001-05-08 7:44 ` Tarjei T. Jensen ` (2 subsequent siblings) 3 siblings, 0 replies; 9+ messages in thread From: Jacob Sparre Andersen @ 2001-05-08 6:04 UTC (permalink / raw) Stephen: > I'm porting GNAT to a 16 bit microprocessor that does not provide a > hardware instruction for unsigned divide (it has multiply and signed > divide, both 16 and 32 bit). Can anyone provide a reference to a book > that discusses how to do this, and/or an algorithm that does it? I've > looked in Knuth, and did an initial web search, and haven't found > anything. I have heard that there exists a free (Open Source) library for doing calculations with very long integers. I suppose that you could find something useful there. A "cheap" solution could be to limit unsigned integers to the range 0 .. 2**31-1, but I am not sure this is allowed by the LRM. Jacob -- "... det er ul�kkert, at man selektivt vil t�mme ulande/�steuropa for velkvalificerede mennesker." Christian Mikkelsen ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: implementing software unsigned divide 2001-05-07 21:42 implementing software unsigned divide Stephen Leake 2001-05-08 6:04 ` Jacob Sparre Andersen @ 2001-05-08 7:44 ` Tarjei T. Jensen 2001-05-08 13:18 ` Ted Dennison 2001-05-08 15:24 ` Tucker Taft 3 siblings, 0 replies; 9+ messages in thread From: Tarjei T. Jensen @ 2001-05-08 7:44 UTC (permalink / raw) Stephen Leake wrote in message ... >I'm porting GNAT to a 16 bit microprocessor that does not provide a >hardware instruction for unsigned divide (it has multiply and signed >divide, both 16 and 32 bit). Can anyone provide a reference to a book >that discusses how to do this, and/or an algorithm that does it? I've >looked in Knuth, and did an initial web search, and haven't found >anything. Why not do it the way you did at school? There is nothing special about binary numbers. You can have a look at old books on assembly programming. Some of them implemented extended arithmetic. Some even did floating point. The worst that could happen is that you have to scale from a 8 bit to a 16 bit machine. Greetings, ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: implementing software unsigned divide 2001-05-07 21:42 implementing software unsigned divide Stephen Leake 2001-05-08 6:04 ` Jacob Sparre Andersen 2001-05-08 7:44 ` Tarjei T. Jensen @ 2001-05-08 13:18 ` Ted Dennison 2001-05-08 15:24 ` Tucker Taft 3 siblings, 0 replies; 9+ messages in thread From: Ted Dennison @ 2001-05-08 13:18 UTC (permalink / raw) In article <uae4oomya.fsf@gsfc.nasa.gov>, Stephen Leake says... > >I'm porting GNAT to a 16 bit microprocessor that does not provide a >hardware instruction for unsigned divide (it has multiply and signed >divide, both 16 and 32 bit). Can anyone provide a reference to a book >that discusses how to do this, and/or an algorithm that does it? I've >looked in Knuth, and did an initial web search, and haven't found >anything. Do you need it for 16 or 32 bit or both? --- T.E.D. homepage - http://www.telepath.com/dennison/Ted/TED.html home email - mailto:dennison@telepath.com ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: implementing software unsigned divide 2001-05-07 21:42 implementing software unsigned divide Stephen Leake ` (2 preceding siblings ...) 2001-05-08 13:18 ` Ted Dennison @ 2001-05-08 15:24 ` Tucker Taft 2001-05-08 21:20 ` Stephen Leake 3 siblings, 1 reply; 9+ messages in thread From: Tucker Taft @ 2001-05-08 15:24 UTC (permalink / raw) Stephen Leake wrote: > > I'm porting GNAT to a 16 bit microprocessor that does not provide a > hardware instruction for unsigned divide (it has multiply and signed > divide, both 16 and 32 bit). Can anyone provide a reference to a book > that discusses how to do this, and/or an algorithm that does it? I've > looked in Knuth, and did an initial web search, and haven't found > anything. This is generally pretty straightforward using the signed hardware instructions, and some appropriate amount of fixups before and/or after the actual divide. I suggest you try some specific examples by hand where one or both of the values have the high bit on. It is pretty easy to figure out what sort of fixup, if any, is necessary. I have done this myself in the past, but unfortunately I didn't write down the algorithms in a place that I can locate at the moment. > > -- > -- Stephe -- -Tucker Taft stt@avercom.net http://www.averstar.com/~stt/ Chief Technology Officer, AverCom Corporation (A Titan Company) Burlington, MA USA (AverCom was formerly the Commercial Division of AverStar: http://www.averstar.com/services/ebusiness_applications.html) ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: implementing software unsigned divide 2001-05-08 15:24 ` Tucker Taft @ 2001-05-08 21:20 ` Stephen Leake 2001-05-09 18:00 ` Tucker Taft 0 siblings, 1 reply; 9+ messages in thread From: Stephen Leake @ 2001-05-08 21:20 UTC (permalink / raw) Tucker Taft <stt@averstar.com> writes: > Stephen Leake wrote: > > > > I'm porting GNAT to a 16 bit microprocessor that does not provide a > > hardware instruction for unsigned divide (it has multiply and signed > > divide, both 16 and 32 bit). Can anyone provide a reference to a book > > that discusses how to do this, and/or an algorithm that does it? I've > > looked in Knuth, and did an initial web search, and haven't found > > anything. > > This is generally pretty straightforward using the > signed hardware instructions, and some appropriate > amount of fixups before and/or after the actual divide. > I suggest you try some specific examples by hand where one or > both of the values have the high bit on. It is pretty > easy to figure out what sort of fixup, if any, is > necessary. I thought of that, but the first example I came up with seemed insoluble (lets assume 16 bit): signed -1 / 2 => 0, but unsigned 16#FFFF# / 2 => 16#7FFF# Maybe if I use the remainder, I can do something. I'll look at it some more. I'll also try the library, see if they have a "microprocessor design" section or some such. > I have done this myself in the past, but unfortunately I didn't > write down the algorithms in a place that I can locate at the > moment. > > > > > -- > > -- Stephe > > -- > -Tucker Taft stt@avercom.net http://www.averstar.com/~stt/ > Chief Technology Officer, AverCom Corporation (A Titan Company) > Burlington, MA USA (AverCom was formerly the Commercial Division of AverStar: > http://www.averstar.com/services/ebusiness_applications.html) -- -- Stephe ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: implementing software unsigned divide 2001-05-08 21:20 ` Stephen Leake @ 2001-05-09 18:00 ` Tucker Taft 2001-05-10 15:54 ` Stephen Leake 2001-05-13 23:17 ` Kenneth Almquist 0 siblings, 2 replies; 9+ messages in thread From: Tucker Taft @ 2001-05-09 18:00 UTC (permalink / raw) Does your chip happen to have 32-bits/16-bits => 16-bit quotient and 16-bit remainder? For that case, clearly you just zero out the high order part rather than sign-extending to handle an unsigned dividend. If it has 32/32 => 32, of course you can handle 16-bit unsigned trivially. A more general solution, I believe, is to (logical) shift both the dividend and divisor right 1 bit, do the divide, and then adjust the quotient up or down by 1 to get the remainder to be >= 0 and less than the divisor. (Obviously you need to first check for the special case when the divisor is <= 1!) -- -Tucker Taft stt@avercom.net http://www.averstar.com/~stt/ Chief Technology Officer, AverCom Corporation (A Titan Company) Burlington, MA USA (AverCom was formerly the Commercial Division of AverStar: http://www.averstar.com/services/ebusiness_applications.html) ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: implementing software unsigned divide 2001-05-09 18:00 ` Tucker Taft @ 2001-05-10 15:54 ` Stephen Leake 2001-05-13 23:17 ` Kenneth Almquist 1 sibling, 0 replies; 9+ messages in thread From: Stephen Leake @ 2001-05-10 15:54 UTC (permalink / raw) Tucker Taft <stt@averstar.com> writes: > Does your chip happen to have 32-bits/16-bits => 16-bit > quotient and 16-bit remainder? No. > For that case, clearly you just zero out the high order part rather > than sign-extending to handle an unsigned dividend. If it has 32/32 > => 32, of course you can handle 16-bit unsigned trivially. Yes, I got that part :). I also realized (after your message yesterday) that if neither operand has the high bit set, the signed divide will give the correct answer. > A more general solution, I believe, is to (logical) shift both the > dividend and divisor right 1 bit, do the divide, and then adjust the > quotient up or down by 1 to get the remainder to be >= 0 and less > than the divisor. (Obviously you need to first check for the special > case when the divisor is <= 1!) Ah, that sounds promising. Thanks! -- -- Stephe ^ permalink raw reply [flat|nested] 9+ messages in thread
* Re: implementing software unsigned divide 2001-05-09 18:00 ` Tucker Taft 2001-05-10 15:54 ` Stephen Leake @ 2001-05-13 23:17 ` Kenneth Almquist 1 sibling, 0 replies; 9+ messages in thread From: Kenneth Almquist @ 2001-05-13 23:17 UTC (permalink / raw) Tucker Taft <stt@averstar.com> wrote: > A more general solution, I believe, is to (logical) shift both the > dividend and divisor right 1 bit, do the divide, and then adjust the > quotient up or down by 1 to get the remainder to be >= 0 and less > than the divisor. (Obviously you need to first check for the special > case when the divisor is <= 1!) The adjustment may be more than one. For example, 2**31 / 3 = 715_827_882 ((2**31)/2) / (3/2) = 2**30 / 1 = 1_073_741_824 The logical shift does work for the case where only the dividend has the high order bit set: function To_Signed is new Unchecked_Conversion(Unsigned_32, Long_Integer); function To_Unsigned is new Unchecked_Conversion(Long_Integer, Unsigned_32); function "/"(Left, Right : Unsigned_32) return Unsigned_32 is begin if To_Signed(Left or Right) >= 0 then -- Neither operand has the high order bit set, so we can -- use signed division. return To_Unsigned(To_Signed(Left) / To_Signed(Right)); elsif To_Signed(Right) < 0 then -- The high order bit of right is set, so that left must be -- less than 2 * right. Therefore, the result is either -- zero or one. return Boolean'pos(Left >= Right); else -- left has high order bit set, right does not. declare Guess : Unsigned_32 := To_Unsigned(To_Signed(Left / 2) / To_Signed(Right)) * 2; begin -- Guess is either be the correct answer or one less than the -- correct answer. In what follows, "/" is mathematically -- exact division, "floor(x)" is the largest integer no larger -- than x, and "floor2(x)" is the largest integral multiple of 2 -- no larger than x. Our goal is to compute floor(left / right). -- guess = floor(floor(left/2) / right) * 2 -- = floor((left/2) / right) * 2 -- = floor2(left / right) -- floor(left / right) - floor2(left / right) = 0 or 1. -- Therefore, guess may be one too small, and we check for that -- by multiplying. if Left - Guess * Right >= Right then Guess := Guess + 1; end if; return Guess; end; end if; end "/"; Depending on how expensive multiplication is on the processor in question, it might be faster to code the computation of the first bit of the quotient by hand, and use the signed divide instruction to get the remaining bits. The basic idea is: else -- left has high order bit set, right does not. declare Left_Shifted : Unsigned_32; Shift : Natural; begin if Right = 0 then raise Constraint_Error; -- division by zero end if; Shift := 0; Left_Shifted := Left / 2; while Left_Shifted >= Right loop Left_Shifted := Left_Shifted / 2; Shift := Shift + 1; end loop; return Shift_Left(1, Shift) + To_Unsigned(To_Signed(Left - Shift_Left(Right, Shift)) / To_Signed(Right)); end; end if; The while loop can execute up to 31 times in this code, so you probably don't want to use this code as is. You could, for example, start out by comparing right to 2**16 or comparing left/2**16 to right. Kenneth Almquist ^ permalink raw reply [flat|nested] 9+ messages in thread
end of thread, other threads:[~2001-05-13 23:17 UTC | newest] Thread overview: 9+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2001-05-07 21:42 implementing software unsigned divide Stephen Leake 2001-05-08 6:04 ` Jacob Sparre Andersen 2001-05-08 7:44 ` Tarjei T. Jensen 2001-05-08 13:18 ` Ted Dennison 2001-05-08 15:24 ` Tucker Taft 2001-05-08 21:20 ` Stephen Leake 2001-05-09 18:00 ` Tucker Taft 2001-05-10 15:54 ` Stephen Leake 2001-05-13 23:17 ` Kenneth Almquist
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox