Re: implementing software unsigned divide

[ka@sorry.no.email (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