implementing software unsigned divide

implementing software unsigned divide

[Stephen Leake]

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

Re: implementing software unsigned divide

[Jacob Sparre Andersen]

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

Re: implementing software unsigned divide

[Tarjei T. Jensen]

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,

Re: implementing software unsigned divide

[Ted Dennison]

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

Re: implementing software unsigned divide

[Tucker Taft]

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)

Re: implementing software unsigned divide

[Stephen Leake]

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

Re: implementing software unsigned divide

[Tucker Taft]

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)

Re: implementing software unsigned divide

[Stephen Leake]

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

Re: implementing software unsigned divide

[Kenneth Almquist]

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